Výpočet a generování faktoriálů, permutací a kombinací v jazyce Python

Podnikání

K výpočtu faktoriálů lze použít standardní modul math pro matematické funkce v jazyce Python. SciPy má také funkce pro výpočet celkového počtu permutací\kombinací.

Modul itertools lze také použít ke generování permutací a kombinací ze seznamů (polí) atd. a k jejich výčtu.

Zde je vysvětlen následující postup spolu s ukázkovým kódem.

  • faktoriál:math.factorial()
  • Vypočítejte celkový počet permutací
    • math.factorial()
    • scipy.special.perm()
  • Generování a výčet permutací ze seznamu:itertools.permutations()
  • Vypočítejte celkový počet kombinací
    • math.factorial()
    • scipy.special.comb()
    • Jak nepoužívat funkci math.factorial()
  • Generování a výčet kombinací ze seznamů:itertools.combinations()
  • Výpočet celkového počtu duplicitních kombinací
  • Generování a výčet duplicitních kombinací ze seznamu:itertools.combinations_with_replacement()

Jako příklad využití permutací je také vysvětleno následující.

  • Vytváření přesmyček z řetězců

Pokud chcete místo jednoho výpisu vygenerovat kombinaci prvků více výpisů, použijte itertools.product() v modulu itertools.

faktoriál: math.factorial()

Modul math poskytuje funkci factorial(), která vrací faktoriál.

import math

print(math.factorial(5))
# 120

print(math.factorial(0))
# 1

Neceločíselné záporné hodnoty způsobí 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čítejte celkový počet permutací

math.factorial()

Permutace je počet případů, kdy je r vybráno z n různých a umístěno do řady.

Celkový počet permutací, p, získáme pomocí následující rovnice s použitím faktoriálů.

p = n! / (n - r)!

Lze jej vypočítat následujícím způsobem pomocí funkce math.factorial(), která vrací faktoriál. Operátor ⌘, který provádí celočíselné dělení, se používá k vrácení celočíselného typu.

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 funkci scipy.special.perm(), která vrací celkový počet permutací. Je nutná samostatná instalace SciPy. K dispozici od verze 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
Třetí argument je ve výchozím nastavení nastaven stejně jako výše a vrací číslo s plovoucí desetinnou čárkou. Všimněte si, že pokud jej chcete získat jako celé číslo, musíte jej nastavit následujícím způsobem.
exact=True

Všimněte si, že pouze „import scipy“ nenačte modul scipy.special.

Proveďte perm() jako „from scipy.special import perm“ jako ve výše uvedeném příkladu nebo proveďte scipy.special.perm() jako „import scipy.special“.

Generování a výčet permutací ze seznamu: itertools.permutations()

Ze seznamů (polí) lze generovat a vyčíslovat nejen celková čísla, ale také permutace atd.

Použijte funkci permutations() modulu itertools.

Předáním iterovatelné položky (typu seznam nebo množina) jako prvního argumentu a počtu kusů, které mají být vybrány, jako druhého argumentu se vrátí iterátor pro danou permutaci.

import itertools

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

p = itertools.permutations(l, 2)

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

Chcete-li je všechny vyjmenovat, můžete použít smyčku 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')

Protože se jedná o konečný iterátor, lze jej také převést na typ seznam pomocí funkce list().

Po zjištění počtu prvků v seznamu pomocí funkce len() lze potvrdit, že se shoduje s celkovým počtem permutací vypočtený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

Pokud je druhý argument vynechán, je vrácena permutace pro výběr všech prvků.

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() jsou prvky zpracovávány na základě pozice, nikoli hodnoty. Duplicitní hodnoty nejsou brány v úvahu.

l = ['a', 'a']

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

Totéž platí pro následující funkce popsané níže.

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

Vypočítejte celkový počet kombinací

math.factorial()

Počet kombinací je počet r dílků, které lze vybrat z n různých dílků. Pořadí se neuvažuje jako u permutací.

Celkový počet kombinací c získáme podle následující rovnice.

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

Lze jej vypočítat následujícím způsobem pomocí funkce math.factorial(), která vrací faktoriál. Operátor ⌘, který provádí celočíselné dělení, se používá k vrácení celočíselného typu.

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 funkci scipy.special.comb(), která vrací celkový počet permutací. Je nutná samostatná instalace SciPy. K dispozici od verze 0.14.0. Všimněte si, že funkce scipy.misc.comb() neimplementuje opakování argumentů popsané níže.

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
Stejně jako u scipy.special.perm() je třetí argument nastaven jako výše a vrací číslo s plovoucí desetinnou čárkou. Všimněte si, že pokud jej chcete získat jako celé číslo, musíte jej nastavit následujícím způsobem.
exact=True
Celkový počet duplicitních kombinací lze získat také pomocí čtvrtého argumentu, opakování. To je popsáno níže.

Opět si všimněte, že pouze „import scipy“ nenačte modul scipy.special.

Stejně jako ve výše uvedeném příkladu proveďte comb() jako „from scipy.special import comb“ nebo proveďte scipy.special.comb() jako „import scipy.special“. Totéž platí pro „scipy.misc“.

Jak nepoužívat funkci math.factorial()

Další metodou, která využívá pouze standardní knihovnu a je rychlejší než metoda využívající math.factorial(), je následující metoda.

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

Generování a výčet kombinací ze seznamů: itertools.combinations()

Je možné vygenerovat a vyčíslit všechny kombinace ze seznamů (polí) atd., stejně jako celková čísla.

Použijte funkci combinations() modulu itertools.

Předáním iterovatelné položky (typu seznam nebo množina) jako prvního argumentu a počtu kusů, které mají být vybrány, jako druhého argumentu se vrátí iterátor pro tuto kombinaci.

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

Výpočet celkového počtu duplicitních kombinací

Počet duplicitních kombinací je počet případů, ve kterých je r vybráno z n různých kombinací, přičemž se připouští duplicity.

Celkový počet duplicitních kombinací je roven počtu kombinací pro výběr (r) z (n + r – 1) různých kombinací.

K výpočtu celkového počtu kombinací proto můžeme použít výše definovanou funkci.

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

print(combinations_with_replacement_count(4, 2))
# 10

Ve výše popsané funkci „scipy.special.comb()“ lze celkový počet duplicitních kombinací získat nastavením čtvrtého argumentu „repetition=True.
Všimněte si, že argument „repetition“ není implementován v „scipy.misc.comb()“ ve verzích před „SciPy0.14.0“.

from scipy.special import comb

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

Generování a výčet duplicitních kombinací ze seznamu: itertools.combinations_with_replacement()

Je možné vygenerovat a vyčíslit všechny duplicitní kombinace ze seznamů (polí) atd., stejně jako celková čísla.

Použijte funkci combinations_with_replacement() v modulu itertools.

Předáním iterovatelné položky (typu seznam nebo množina) jako prvního argumentu a počtu kusů, které mají být vybrány, jako druhého argumentu se vrátí iterátor pro tuto překrývající se kombinaci.

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áření přesmyček z řetězců

Itertools.permutations() umožňuje snadno vytvářet permutace řetězců (anagramy).

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

Chcete-li zkombinovat tuple po jednom znaku do řetězce a vytvořit z něj seznam, postupujte následovně.

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

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

Používá se metoda join(), která spojuje prvky seznamu nebo tuple do řetězce, a zápis pro porozumění seznamu.

Copied title and URL