Arvutada ja genereerida faktoriaalid, permutatsioonid ja kombinatsioonid Pythonis

Äri

Pythoni matemaatiliste funktsioonide standardmoodulit math saab kasutada faktoriaalide arvutamiseks. SciPy's on ka funktsioonid permutatsioonide \kombinatsioonide koguarvu arvutamiseks.

Moodulit itertools saab kasutada ka nimekirjadest (massiividest) jne. permutatsioonide ja kombinatsioonide genereerimiseks ning nende loendamiseks.

Siin selgitatakse järgmist koos näidiskoodiga.

  • faktoriaal:math.factorial()
  • Arvutage permutatsioonide koguarv.
    • math.factorial()
    • scipy.special.perm()
  • Loovad ja loendavad loetelust permutatsioone:itertools.permutations()
  • Arvutage kombinatsioonide koguarv
    • math.factorial()
    • scipy.special.comb()
    • Kuidas mitte kasutada math.factorial()
  • Loovad ja loendavad kombinatsioone nimekirjadest:itertools.combinations()
  • Arvutage dubleerivate kombinatsioonide koguarv.
  • Loovad ja loendavad nimekirjast duplikaatkombinatsioone:itertools.combinations_with_replacement()

Permutatsioonide kasutamise näitena selgitatakse ka järgmist.

  • Anagrammide loomine stringidest

Kui soovite genereerida mitme loendi elementide kombinatsiooni ühe loendi asemel, kasutage itertools.product() moodulis itertools.

faktoriaal: math.factorial()

Matemaatikamoodul pakub funktsiooni factorial(), mis tagastab faktoriaali.

import math

print(math.factorial(5))
# 120

print(math.factorial(0))
# 1

Mitte täisarvulised, negatiivsed väärtused toovad kaasa ValueError'i.

# print(math.factorial(1.5))
# ValueError: factorial() only accepts integral values

# print(math.factorial(-1))
# ValueError: factorial() not defined for negative values

Arvutage permutatsioonide koguarv.

math.factorial()

Permutatsioonid on nende juhtumite arv, kus r on valitud n erinevast ja paigutatud ritta.

Permutatsioonide koguarv p saadakse järgmise võrrandi abil, kasutades faktoriaale.

p = n! / (n - r)!

Seda saab arvutada järgmiselt, kasutades funktsiooni math.factorial(), mis tagastab faktoriaali. Terviktüübi tagastamiseks kasutatakse operaatorit ⌘, mis teostab täisarvu jagamist.

def permutations_count(n, r):
    return math.factorial(n) // math.factorial(n - r)

print(permutations_count(4, 2))
# 12

print(permutations_count(4, 4))
# 24

scipy.special.perm()

SciPy pakub funktsiooni scipy.special.perm(), mis tagastab permutatsioonide koguarvu. Vajalik on eraldi SciPy installeerimine. Saadaval alates versioonist 0.14.0.

from scipy.special import perm

print(perm(4, 2))
# 12.0

print(perm(4, 2, exact=True))
# 12

print(perm(4, 4, exact=True))
# 24

exact=False
Kolmas argument on vaikimisi määratud nagu eespool ja tagastab ujukomaarvu. Pange tähele, et kui soovite seda saada täisarvuna, peate selle seadistama järgmiselt.
exact=True

Pange tähele, et ainult “import scipy” ei lae scipy.special moodulit.

Sooritage perm() kui “from scipy.special import perm” nagu ülaltoodud näites, või käivitage scipy.special.perm() kui “import scipy.special”.

Loovad ja loendavad loetelust permutatsioone: itertools.permutations()

Nimekirjadest (massiividest) saab genereerida ja loetleda mitte ainult koguarvu, vaid ka permutatsioone jne.

Kasutage mooduli itertools funktsiooni permutations().

Esimeseks argumendiks on iterable (loendi või kogumi tüüp) ja teiseks argumendiks valitavate tükkide arv, mis tagastab selle permutatsiooni iteraatori.

import itertools

l = ['a', 'b', 'c', 'd']

p = itertools.permutations(l, 2)

print(type(p))
# <class 'itertools.permutations'>

Kõigi nende loendamiseks võite kasutada for-tsüklit.

for v in itertools.permutations(l, 2):
    print(v)
# ('a', 'b')
# ('a', 'c')
# ('a', 'd')
# ('b', 'a')
# ('b', 'c')
# ('b', 'd')
# ('c', 'a')
# ('c', 'b')
# ('c', 'd')
# ('d', 'a')
# ('d', 'b')
# ('d', 'c')

Kuna tegemist on lõpliku iteraatoriga, saab selle teisendada list() abil ka loenditüübiks.

Kui nimekirjas olevate elementide arv saadakse len() abil, saab kinnitada, et see vastab faktoriaali põhjal arvutatud permutatsioonide koguarvule.

p_list = list(itertools.permutations(l, 2))

print(p_list)
# [('a', 'b'), ('a', 'c'), ('a', 'd'), ('b', 'a'), ('b', 'c'), ('b', 'd'), ('c', 'a'), ('c', 'b'), ('c', 'd'), ('d', 'a'), ('d', 'b'), ('d', 'c')]

print(len(p_list))
# 12

Kui teine argument jäetakse ära, tagastatakse kõigi elementide valimiseks vajalik permutatsioon.

for v in itertools.permutations(l):
    print(v)
# ('a', 'b', 'c', 'd')
# ('a', 'b', 'd', 'c')
# ('a', 'c', 'b', 'd')
# ('a', 'c', 'd', 'b')
# ('a', 'd', 'b', 'c')
# ('a', 'd', 'c', 'b')
# ('b', 'a', 'c', 'd')
# ('b', 'a', 'd', 'c')
# ('b', 'c', 'a', 'd')
# ('b', 'c', 'd', 'a')
# ('b', 'd', 'a', 'c')
# ('b', 'd', 'c', 'a')
# ('c', 'a', 'b', 'd')
# ('c', 'a', 'd', 'b')
# ('c', 'b', 'a', 'd')
# ('c', 'b', 'd', 'a')
# ('c', 'd', 'a', 'b')
# ('c', 'd', 'b', 'a')
# ('d', 'a', 'b', 'c')
# ('d', 'a', 'c', 'b')
# ('d', 'b', 'a', 'c')
# ('d', 'b', 'c', 'a')
# ('d', 'c', 'a', 'b')
# ('d', 'c', 'b', 'a')

print(len(list(itertools.permutations(l))))
# 24

Itertools.permutations() funktsioonis käsitletakse elemente positsiooni, mitte väärtuse alusel. Dubleerivaid väärtusi ei võeta arvesse.

l = ['a', 'a']

for v in itertools.permutations(l, 2):
    print(v)
# ('a', 'a')
# ('a', 'a')

Sama kehtib ka järgmiste allpool kirjeldatud funktsioonide kohta.

  • itertools.combinations()
  • itertools.combinations_with_replacement()

Arvutage kombinatsioonide koguarv

math.factorial()

Kombinatsioonide arv on r tükki, mida saab valida n erinevast tükist. Järjekorda ei võeta arvesse nagu permutatsioonides.

Kombinatsioonide koguarv c saadakse järgmise võrrandi abil.

c = n! / (r! * (n - r)!)

Seda saab arvutada järgmiselt, kasutades funktsiooni math.factorial(), mis tagastab faktoriaali. Terviktüübi tagastamiseks kasutatakse operaatorit ⌘, mis teostab täisarvu jagamist.

def combinations_count(n, r):
    return math.factorial(n) // (math.factorial(n - r) * math.factorial(r))

print(combinations_count(4, 2))
# 6

scipy.special.comb()

SciPy pakub funktsiooni scipy.special.comb(), mis tagastab permutatsioonide koguarvu. Vajalik on eraldi SciPy installeerimine. Saadaval alates versioonist 0.14.0. Pange tähele, et scipy.misc.comb() ei rakenda allpool kirjeldatud argumentide kordamist.

from scipy.special import comb

print(comb(4, 2))
# 6.0

print(comb(4, 2, exact=True))
# 6

print(comb(4, 0, exact=True))
# 1

exact=False
Nagu ka scipy.special.perm() puhul, on kolmas argument vaikimisi määratud nagu eespool ja tagastab ujukomaarvu. Pange tähele, et kui soovite seda saada täisarvuna, tuleb see määrata järgmiselt.
exact=True
Dubleerivate kombinatsioonide koguarvu saab ka neljanda argumendi, korduse, abil. Seda kirjeldatakse allpool.

Pange jällegi tähele, et ainult “import scipy” ei lae scipy.special moodulit.

Nagu ülaltoodud näites, käivitage comb() kui “from scipy.special import comb” või käivitage scipy.special.comb() kui “import scipy.special”. Sama kehtib ka “scipy.misc” kohta.

Kuidas mitte kasutada math.factorial()

Teine meetod, mis kasutab ainult standardraamatukogu ja on kiirem kui meetod, mis kasutab math.factorial(), on järgmine meetod.

from operator import mul
from functools import reduce

def combinations_count(n, r):
    r = min(r, n - r)
    numer = reduce(mul, range(n, n - r, -1), 1)
    denom = reduce(mul, range(1, r + 1), 1)
    return numer // denom

print(combinations_count(4, 2))
# 6

print(combinations_count(4, 0))
# 1

Loovad ja loendavad kombinatsioone nimekirjadest: itertools.combinations()

Võimalik on genereerida ja loetleda kõik kombinatsioonid nimekirjadest (massiividest) jne, samuti koguarvud.

Kasutage mooduli itertools funktsiooni combinations().

Esimeseks argumendiks on iterable (loendi või kogumi tüüp) ja teiseks argumendiks valitavate tükkide arv, mis tagastab selle kombinatsiooni iteraatori.

l = ['a', 'b', 'c', 'd']

c = itertools.combinations(l, 2)

print(type(c))
# <class 'itertools.combinations'>

for v in itertools.combinations(l, 2):
    print(v)
# ('a', 'b')
# ('a', 'c')
# ('a', 'd')
# ('b', 'c')
# ('b', 'd')
# ('c', 'd')

c_list = list(itertools.combinations(l, 2))

print(c_list)
# [('a', 'b'), ('a', 'c'), ('a', 'd'), ('b', 'c'), ('b', 'd'), ('c', 'd')]

print(len(c_list))
# 6

Arvutage dubleerivate kombinatsioonide koguarv.

Dubleerivate kombinatsioonide arv on nende juhtumite arv, kus r on valitud n erineva kombinatsiooni hulgast, võttes arvesse dubleerivaid kombinatsioone.

Topeltkombinatsioonide koguarv on võrdne (n + r – 1) erinevatest kombinatsioonidest (r) valitavate kombinatsioonide arvuga.

Seetõttu võime kasutada eespool määratletud funktsiooni, et arvutada kombinatsioonide koguarvu.

def combinations_with_replacement_count(n, r):
    return combinations_count(n + r - 1, r)

print(combinations_with_replacement_count(4, 2))
# 10

Eespool kirjeldatud funktsioonis “scipy.special.comb()” saab topeltkombinatsioonide koguarvu teada, kui seada neljandaks argumendiks “repetition=True.
Pange tähele, et argument “repetition” ei ole “scipy.misc.comb()” versioonides enne “SciPy0.14.0” rakendatud.

from scipy.special import comb

print(comb(4, 2, exact=True, repetition=True))
# 10

Loovad ja loendavad nimekirjast duplikaatkombinatsioone: itertools.combinations_with_replacement()

Võimalik on genereerida ja loetleda kõik topeltkombinatsioonid nimekirjadest (massiividest) jne, samuti koguarvud.

Kasutage funktsiooni combinations_with_replacement() moodulis itertools.

Esimeseks argumendiks on iterable (loendi või kogumi tüüp) ja teiseks argumendiks valitavate tükkide arv, mis tagastab iteraatori selle kattuva kombinatsiooni jaoks.

h = itertools.combinations_with_replacement(l, 2)

print(type(h))
# <class 'itertools.combinations_with_replacement'>

for v in itertools.combinations_with_replacement(l, 2):
    print(v)
# ('a', 'a')
# ('a', 'b')
# ('a', 'c')
# ('a', 'd')
# ('b', 'b')
# ('b', 'c')
# ('b', 'd')
# ('c', 'c')
# ('c', 'd')
# ('d', 'd')

h_list = list(itertools.combinations_with_replacement(l, 2))

print(h_list)
# [('a', 'a'), ('a', 'b'), ('a', 'c'), ('a', 'd'), ('b', 'b'), ('b', 'c'), ('b', 'd'), ('c', 'c'), ('c', 'd'), ('d', 'd')]

print(len(h_list))
# 10

Anagrammide loomine stringidest

Itertools.permutations() võimaldab hõlpsasti luua stringide permutatsioone (anagramme).

s = 'arc'

for v in itertools.permutations(s):
    print(v)
# ('a', 'r', 'c')
# ('a', 'c', 'r')
# ('r', 'a', 'c')
# ('r', 'c', 'a')
# ('c', 'a', 'r')
# ('c', 'r', 'a')

Selleks, et kombineerida ühe tähemärgiga tupel stringiks ja muuta see loeteluks, tehke järgmist

anagram_list = [''.join(v) for v in itertools.permutations(s)]

print(anagram_list)
# ['arc', 'acr', 'rac', 'rca', 'car', 'cra']

Kasutatakse meetodit join(), mis ühendab loendi või tupli elemendid stringiks, ja loendi mõistmise notatsiooni.

Copied title and URL