Výpočet a generovanie faktoriálov, permutácií a kombinácií v jazyku Python

obchodné

Na výpočet faktoriálov možno použiť štandardný modul math pre matematické funkcie v jazyku Python. SciPy má tiež funkcie na výpočet celkového počtu permutácií\kombinácií.

Modul itertools možno použiť aj na generovanie permutácií a kombinácií zo zoznamov (polí) atď. a na ich výpočet.

Nasledujúci postup je vysvetlený spolu so vzorovým kódom.

  • faktoriál:math.factorial()
  • Vypočítajte celkový počet permutácií
    • math.factorial()
    • scipy.special.perm()
  • Generovanie a výpočet permutácií zo zoznamu:itertools.permutations()
  • Vypočítajte celkový počet kombinácií
    • math.factorial()
    • scipy.special.comb()
    • Ako nepoužívať math.factorial()
  • Generovanie a vymenovanie kombinácií zo zoznamov:itertools.combinations()
  • Vypočítajte celkový počet duplicitných kombinácií
  • Generovanie a vypisovanie duplicitných kombinácií zo zoznamu:itertools.combinations_with_replacement()

Ako príklad využitia permutácií je vysvetlený aj nasledujúci postup.

  • Vytváranie anagramov z reťazcov

Ak chcete namiesto jedného výpisu vygenerovať kombináciu prvkov viacerých výpisov, použite itertools.product() v module itertools.

faktoriál: math.factorial()

Modul math poskytuje funkciu factorial(), ktorá vracia faktoriál.

import math

print(math.factorial(5))
# 120

print(math.factorial(0))
# 1

Neceločíselné záporné hodnoty budú mať za následok chybu ValueError.

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

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

Vypočítajte celkový počet permutácií

math.factorial()

Permutácie sú počtom prípadov, keď je r vybraných z n rôznych a umiestnených v jednom rade.

Celkový počet permutácií, p, získame pomocou nasledujúcej rovnice s použitím faktoriálov.

p = n! / (n - r)!

Možno ho vypočítať nasledovne pomocou funkcie math.factorial(), ktorá vráti faktoriál. Na vrátenie celočíselného typu sa používa operátor ⌘, ktorý vykonáva celočíselné delenie.

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 poskytuje funkciu scipy.special.perm(), ktorá vráti celkový počet permutácií. Vyžaduje sa samostatná inštalácia SciPy. K dispozícii od verzie 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
Tretí argument je predvolene nastavený ako vyššie a vracia číslo s pohyblivou desatinnou čiarkou. Ak ho chcete získať ako celé číslo, musíte ho nastaviť takto.
exact=True

Všimnite si, že iba „import scipy“ nenačíta modul scipy.special.

Vykonajte perm() ako „from scipy.special import perm“ ako vo vyššie uvedenom príklade alebo vykonajte scipy.special.perm() ako „import scipy.special“.

Generovanie a výpočet permutácií zo zoznamu: itertools.permutations()

Zo zoznamov (polí) možno generovať a vyčísľovať nielen celkové čísla, ale aj permutácie atď.

Použite funkciu permutations() modulu itertools.

Predaním iterátora (typu zoznam alebo množina) ako prvého argumentu a počtu kusov, ktoré sa majú vybrať, ako druhého argumentu sa vráti iterátor pre danú permutáciu.

import itertools

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

p = itertools.permutations(l, 2)

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

Ak chcete vymenovať všetky, môžete použiť cyklus for.

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')

Keďže ide o konečný iterátor, možno ho tiež previesť na typ zoznam pomocou funkcie list().

Keď sa pomocou funkcie len() zistí počet prvkov v zozname, možno potvrdiť, že sa zhoduje s celkovým počtom permutácií vypočítaným z faktoriálu.

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

Ak je druhý argument vynechaný, vráti sa permutácia pre výber všetkých prvkov.

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

V itertools.permutations() sú prvky spracované na základe pozície, nie hodnoty. Duplicitné hodnoty sa neberú do úvahy.

l = ['a', 'a']

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

To isté platí pre nasledujúce funkcie, ktoré sú opísané nižšie.

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

Vypočítajte celkový počet kombinácií

math.factorial()

Počet kombinácií je počet r dielikov, ktoré si môžete vybrať z n rôznych dielikov. Poradie sa neberie do úvahy ako pri permutáciách.

Celkový počet kombinácií c sa získa nasledujúcou rovnicou.

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

Možno ho vypočítať nasledovne pomocou funkcie math.factorial(), ktorá vráti faktoriál. Na vrátenie celočíselného typu sa používa operátor ⌘, ktorý vykonáva celočíselné delenie.

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 poskytuje funkciu scipy.special.comb(), ktorá vráti celkový počet permutácií. Vyžaduje sa samostatná inštalácia SciPy. K dispozícii od verzie 0.14.0. Všimnite si, že funkcia scipy.misc.comb() neimplementuje opakovanie argumentov opísané nižšie.

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
Rovnako ako pri scipy.special.perm() je tretí argument predvolene nastavený ako vyššie a vracia číslo s pohyblivou desatinnou čiarkou. Všimnite si, že ak ho chcete získať ako celé číslo, musíte ho nastaviť takto.
exact=True
Celkový počet duplicitných kombinácií možno získať aj pomocou štvrtého argumentu, opakovania. Tento postup je opísaný nižšie.

Opäť si všimnite, že iba „import scipy“ nenačíta modul scipy.special.

Rovnako ako vo vyššie uvedenom príklade vykonajte comb() ako „from scipy.special import comb“ alebo vykonajte scipy.special.comb() ako „import scipy.special“. To isté platí pre „scipy.misc“.

Ako nepoužívať math.factorial()

Ďalšou metódou, ktorá využíva iba štandardnú knižnicu a je rýchlejšia ako metóda využívajúca math.factorial(), je nasledujúca metóda.

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

Generovanie a vymenovanie kombinácií zo zoznamov: itertools.combinations()

Je možné generovať a vyčísliť všetky kombinácie zo zoznamov (polí) atď., ako aj celkové počty.

Použite funkciu combinations() modulu itertools.

Pri odovzdaní iterátora (typu zoznam alebo množina) ako prvého argumentu a počtu kusov, ktoré sa majú vybrať, ako druhého argumentu sa vráti iterátor pre túto kombináciu.

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

Vypočítajte celkový počet duplicitných kombinácií

Počet duplicitných kombinácií je počet prípadov, v ktorých sa vyberie r z n rôznych kombinácií, pričom sa pripustia duplicity.

Celkový počet duplicitných kombinácií sa rovná počtu kombinácií na výber (r) z (n + r – 1) rôznych kombinácií.

Preto môžeme použiť vyššie definovanú funkciu na výpočet celkového počtu kombinácií.

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

print(combinations_with_replacement_count(4, 2))
# 10

Vo vyššie opísanej funkcii „scipy.special.comb()“ možno celkový počet duplicitných kombinácií získať nastavením štvrtého argumentu „repetition=True.
Všimnite si, že argument „repetition“ nie je implementovaný v „scipy.misc.comb()“ vo verziách pred „SciPy0.14.0“.

from scipy.special import comb

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

Generovanie a vypisovanie duplicitných kombinácií zo zoznamu: itertools.combinations_with_replacement()

Je možné generovať a vyčísliť všetky duplicitné kombinácie zo zoznamov (polí) atď., ako aj celkové počty.

Použite funkciu combinations_with_replacement() v module itertools.

Predaním iterátora (typu zoznam alebo množina) ako prvého argumentu a počtu kusov, ktoré sa majú vybrať, ako druhého argumentu sa vráti iterátor pre túto prekrývajúcu sa kombináciu.

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

Vytváranie anagramov z reťazcov

Funkcia Itertools.permutations() uľahčuje vytváranie permutácií reťazcov (anagramov).

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')

Ak chcete spojiť tuple po jednom znaku do reťazca a vytvoriť z neho zoznam, postupujte takto

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

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

Používa sa metóda join(), ktorá spája prvky zoznamu alebo trojuholníka do reťazca, a zápis porozumenia zoznamu.