Calcular i generar factorials, permutacions i combinacions en Python

Negocis

El mòdul estàndard de matemàtiques per a funcions matemàtiques a Python es pot utilitzar per calcular factorials. SciPy també té funcions per calcular el nombre total de permutacions/combinacions.

El mòdul itertools també es pot utilitzar per generar permutacions i combinacions a partir de llistes (matrius), etc., i enumerar-les.

Aquí s’explica el següent, juntament amb el codi d’exemple.

  • factorial:math.factorial()
  • Calcula el nombre total de permutacions
    • math.factorial()
    • scipy.special.perm()
  • Generar i enumerar permutacions a partir d’una llista:itertools.permutations()
  • Calcula el nombre total de combinacions
    • math.factorial()
    • scipy.special.comb()
    • Com no utilitzar math.factorial()
  • Generar i enumerar combinacions a partir de llistes:itertools.combinations()
  • Calcula el nombre total de combinacions duplicades
  • Generar i enumerar combinacions duplicades a partir d’una llista:itertools.combinations_with_replacement()

Com a exemple d’utilització de permutacions, també s’explica el següent.

  • Crea anagrames a partir de cadenes

Si voleu generar una combinació d’elements de diverses fitxes en lloc d’una única llista, utilitzeu itertools.product() al mòdul itertools.

factorial:math.factorial()

El mòdul matemàtic proporciona una funció factorial() que retorna el factorial.

import math

print(math.factorial(5))
# 120

print(math.factorial(0))
# 1

Els valors negatius no enters donaran lloc a 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 el nombre total de permutacions

math.factorial()

Les permutacions són el nombre de casos en què r es trien entre n diferents i es col·loquen en una fila.

El nombre total de permutacions, p, s’obté mitjançant l’equació següent utilitzant factorials.

p = n! / (n - r)!

Es pot calcular de la següent manera utilitzant la funció math.factorial(), que retorna el factorial. L’operador ⌘, que realitza la divisió sencer, s’utilitza per retornar un tipus d’enter.

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 proporciona una funció scipy.special.perm() que retorna el nombre total de permutacions. Es requereix una instal·lació de SciPy independent. Disponible des de la versió 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
El tercer argument s’estableix com a anterior per defecte i retorna un nombre de coma flotant. Tingueu en compte que si voleu obtenir-lo com a nombre enter, heu de configurar-lo de la següent manera.
exact=True

Tingueu en compte que només “import scipy” no carregarà el mòdul scipy.special.

Executeu perm() com a “des de scipy.special import perm” com a l’exemple anterior, o executeu scipy.special.perm() com a “import scipy.special”.

Generar i enumerar permutacions a partir d’una llista:itertools.permutations()

No només es poden generar i enumerar nombres totals, sinó també permutacions a partir de llistes (matrius), etc.

Utilitzeu la funció permutations() del mòdul itertools.

Passar un iterable (tipus de llista o conjunt) com a primer argument i el nombre de peces que s’han de seleccionar com a segon argument retorna un iterador per a aquesta permutació.

import itertools

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

p = itertools.permutations(l, 2)

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

Per enumerar-los tots, podeu utilitzar un bucle 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')

Com que és un iterador finit, també es pot convertir a un tipus de llista amb list().

Quan el nombre d’elements de la llista s’obté amb len(), es pot confirmar que coincideix amb el nombre total de permutacions calculades a partir del 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

Si s’omet el segon argument, es retorna la permutació per seleccionar tots els elements.

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

A itertools.permutations(), els elements es tracten en funció de la posició, no del valor. No es tenen en compte els valors duplicats.

l = ['a', 'a']

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

El mateix s’aplica a les funcions següents, descrites a continuació.

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

Calcula el nombre total de combinacions

math.factorial()

El nombre de combinacions és el nombre de r peces per triar entre n peces diferents. L’ordre no es considera com a permutacions.

El nombre total de combinacions c s’obté mitjançant l’equació següent.

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

Es pot calcular de la següent manera utilitzant la funció math.factorial(), que retorna el factorial. L’operador ⌘, que realitza la divisió sencer, s’utilitza per retornar un tipus d’enter.

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 proporciona una funció scipy.special.comb() que retorna el nombre total de permutacions. Es requereix una instal·lació de SciPy independent. Disponible des de la versió 0.14.0. Tingueu en compte que scipy.misc.comb() no implementa la repetició d’arguments descrita a continuació.

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
Igual que amb scipy.special.perm(), el tercer argument s’estableix com a anterior per defecte i retorna un nombre de coma flotant. Tingueu en compte que si voleu obtenir-lo com a nombre enter, heu de configurar-lo de la següent manera.
exact=True
El nombre total de combinacions duplicades també es pot obtenir amb el quart argument, la repetició. Això es descriu a continuació.

De nou, tingueu en compte que només “import scipy” no carregarà el mòdul scipy.special.

Com a l’exemple anterior, executeu comb() com a “des de scipy.special import comb” o executeu scipy.special.comb() com a “import scipy.special”. El mateix s’aplica a “scipy.misc”.

Com no utilitzar math.factorial()

Un altre mètode que utilitza només la biblioteca estàndard i és més ràpid que el mètode que utilitza math.factorial() és el següent.

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

Generar i enumerar combinacions a partir de llistes:itertools.combinations()

És possible generar i enumerar totes les combinacions de llistes (matrius), etc., així com nombres totals.

Utilitzeu la funció combinacions() del mòdul itertools.

Passar un iterable (tipus de llista o conjunt) com a primer argument i el nombre de peces a seleccionar com a segon argument retorna l’iterador d’aquesta combinació.

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 el nombre total de combinacions duplicades

El nombre de combinacions duplicades és el nombre de casos en què r s’escull entre n de diferents, permetent els duplicats.

El nombre total de combinacions duplicades és igual al nombre de combinacions per triar (r) entre (n + r – 1) diferents.

Per tant, podem utilitzar la funció definida anteriorment per calcular el nombre total de combinacions.

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

print(combinations_with_replacement_count(4, 2))
# 10

A “scipy.special.comb()” descrit anteriorment, es pot obtenir el nombre total de combinacions duplicades establint el quart argument “repetition=True.
Tingueu en compte que l’argument “repetició” no s’implementa a “scipy.misc.comb()” en versions anteriors a “SciPy0.14.0”.

from scipy.special import comb

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

Generar i enumerar combinacions duplicades a partir d’una llista:itertools.combinations_with_replacement()

És possible generar i enumerar totes les combinacions duplicades de llistes (matrius), etc., així com nombres totals.

Utilitzeu la funció combinaisons_with_replacement() al mòdul itertools.

Passar un iterable (tipus de llista o conjunt) com a primer argument i el nombre de peces que s’han de seleccionar com a segon argument retorna un iterador per a aquesta combinació superposada.

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 anagrames a partir de cadenes

Itertools.permutations() facilita la creació de permutacions de cadena (anagrames).

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

Per combinar una tupla d’un caràcter alhora en una cadena i convertir-la en una llista, feu el següent

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

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

S’utilitza el mètode join(), que concatena elements d’una llista o tupla en una cadena, i la notació de comprensió de la llista.

Copied title and URL