Calculați și generați factoriali, permutări și combinații în Python

Afaceri

Modulul standard math pentru funcțiile matematice din Python poate fi utilizat pentru a calcula factoriale. SciPy are, de asemenea, funcții pentru a calcula numărul total de permutări\combinări.

Modulul itertools poate fi utilizat, de asemenea, pentru a genera permutări și combinații din liste (array-uri) etc. și pentru a le enumera.

Următoarele aspecte sunt explicate aici, împreună cu un exemplu de cod.

  • factorială:math.factorial()
  • Calculați numărul total de permutări
    • math.factorial()
    • scipy.special.perm()
  • Generarea și enumerarea permutărilor dintr-o listă:itertools.permutations()
  • Calculați numărul total de combinații
    • math.factorial()
    • scipy.special.comb()
    • Cum să nu folosiți math.factorial()
  • Generarea și enumerarea combinațiilor din liste:itertools.combinations()
  • Calculați numărul total de combinații duplicate
  • Generarea și enumerarea combinațiilor duplicate dintr-o listă:itertools.combinations_with_replacement()

Ca un exemplu de utilizare a permutărilor, se explică, de asemenea, următoarele.

  • Creați anagrame din șiruri de caractere

Dacă doriți să generați o combinație de elemente din mai multe liste în loc de o singură listă, utilizați itertools.product() din modulul itertools.

factorială: math.factorial()

Modulul math oferă o funcție factorial() care returnează factorialul.

import math

print(math.factorial(5))
# 120

print(math.factorial(0))
# 1

Valorile negative, care nu sunt întregi, vor avea ca rezultat un ValueError.

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

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

Calculați numărul total de permutări

math.factorial()

Permutările reprezintă numărul de cazuri în care r sunt alese dintre cele n diferite și plasate pe un rând.

Numărul total de permutări, p, se obține prin următoarea ecuație folosind factoriale.

p = n! / (n - r)!

Acesta poate fi calculat după cum urmează, folosind funcția math.factorial(), care returnează factorialul. Operatorul ⌘, care efectuează diviziunea întregi, este utilizat pentru a returna un tip de număr întreg.

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 oferă o funcție scipy.special.perm() care returnează numărul total de permutări. Este necesară o instalare separată a SciPy. Disponibilă începând cu versiunea 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
Cel de-al treilea argument este setat în mod implicit ca mai sus și returnează un număr cu virgulă mobilă. Rețineți că, dacă doriți să-l obțineți sub formă de număr întreg, trebuie să îl setați după cum urmează.
exact=True

Rețineți că doar „import scipy” nu va încărca modulul scipy.special.

Executați perm() ca „from scipy.special import perm”, ca în exemplul de mai sus, sau executați scipy.special.perm() ca „import scipy.special”.

Generarea și enumerarea permutărilor dintr-o listă: itertools.permutations()

Nu numai numerele totale, ci și permutările pot fi generate și enumerate din liste (array-uri) etc.

Utilizați funcția permutations() din modulul itertools.

Transmiterea unui iterabil (de tip listă sau set) ca prim argument și a numărului de piese care trebuie selectate ca al doilea argument returnează un iterator pentru permutarea respectivă.

import itertools

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

p = itertools.permutations(l, 2)

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

Pentru a le enumera pe toate, puteți utiliza o buclă 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')

Deoarece este un iterator finit, poate fi, de asemenea, convertit într-un tip de listă cu list().

Atunci când numărul de elemente din listă este obținut cu len(), se poate confirma că acesta corespunde numărului total de permutări calculat din factorială.

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

În cazul în care al doilea argument este omis, se returnează permutarea pentru selectarea tuturor elementelor.

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

În itertools.permutations(), elementele sunt tratate în funcție de poziție, nu de valoare. Valorile duplicate nu sunt luate în considerare.

l = ['a', 'a']

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

Același lucru este valabil și pentru următoarele funcții, descrise mai jos.

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

Calculați numărul total de combinații

math.factorial()

Numărul de combinații este numărul de r piese care pot fi alese din n piese diferite. Ordinea nu este luată în considerare ca în cazul permutărilor.

Numărul total de combinații c se obține prin următoarea ecuație.

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

Acesta poate fi calculat după cum urmează, folosind funcția math.factorial(), care returnează factorialul. Operatorul ⌘, care efectuează diviziunea întregi, este utilizat pentru a returna un tip de număr întreg.

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 oferă o funcție scipy.special.comb() care returnează numărul total de permutări. Este necesară o instalare separată a SciPy. Disponibilă începând cu versiunea 0.14.0. Rețineți că scipy.misc.comb() nu implementează repetarea argumentelor descrisă mai jos.

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
Ca și în cazul scipy.special.perm(), al treilea argument este setat în mod implicit ca mai sus și returnează un număr în virgulă mobilă. Rețineți că, dacă doriți să îl obțineți ca număr întreg, trebuie să îl setați după cum urmează.
exact=True
Numărul total de combinații duplicate poate fi obținut, de asemenea, cu ajutorul celui de-al patrulea argument, repetiția. Acesta este descris mai jos.

Din nou, rețineți că doar „import scipy” nu va încărca modulul scipy.special.

Ca în exemplul de mai sus, executați comb() ca „from scipy.special import comb” sau executați scipy.special.comb() ca „import scipy.special”. Același lucru este valabil și pentru „scipy.misc”.

Cum să nu folosiți math.factorial()

O altă metodă care utilizează doar biblioteca standard și este mai rapidă decât metoda care utilizează math.factorial() este următoarea metodă.

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

Generarea și enumerarea combinațiilor din liste: itertools.combinations()

Este posibil să se genereze și să se enumere toate combinațiile din liste (array-uri) etc., precum și numerele totale.

Utilizați funcția combinations() din modulul itertools.

Dacă se trece un iterabil (de tip listă sau set) ca prim argument și numărul de piese care trebuie selectate ca al doilea argument, se returnează iteratorul pentru combinația respectivă.

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

Calculați numărul total de combinații duplicate

Numărul de combinații duplicate este numărul de cazuri în care r sunt alese din n combinații diferite, ținând cont de duplicate.

Numărul total de combinații duplicate este egal cu numărul de combinații de ales (r) din (n + r – 1) combinații diferite.

Prin urmare, putem utiliza funcția definită mai sus pentru a calcula numărul total de combinații.

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

print(combinations_with_replacement_count(4, 2))
# 10

În „scipy.special.comb()” descris mai sus, numărul total de combinații duplicate poate fi obținut prin setarea celui de-al patrulea argument „repetition=True”.
Rețineți că argumentul „repetiție” nu este implementat în „scipy.misc.comb()” în versiunile anterioare la „SciPy0.14.0”.

from scipy.special import comb
print(comb(4, 2, exact=True, repetition=True))
# 10

Generarea și enumerarea combinațiilor duplicate dintr-o listă: itertools.combinations_with_replacement()

Este posibil să se genereze și să se enumere toate combinațiile duplicate din liste (array-uri) etc., precum și numerele totale.

Utilizați funcția combinations_with_replacement() din modulul itertools.

Transmiterea unui iterabil (de tip listă sau set) ca prim argument și a numărului de piese care trebuie selectate ca al doilea argument returnează un iterator pentru acea combinație suprapusă.

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

Creați anagrame din șiruri de caractere

Itertools.permutations() facilitează crearea de permutări de șiruri de caractere (anagrame).

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

Pentru a combina un tuple de câte un caracter într-un șir de caractere și a-l transforma într-o listă, procedați după cum urmează

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

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

Se utilizează metoda join(), care concatenează elementele unei liste sau ale unui tuple într-un șir de caractere, precum și notația de înțelegere a listei.