Calcula e xera factoriais, permutacións e combinacións en Python

Negocios

O módulo estándar de matemáticas para funcións matemáticas en Python pódese usar para calcular factoriais. SciPy tamén ten funcións para calcular o número total de permutacións/combinacións.

O módulo itertools tamén se pode usar para xerar permutacións e combinacións a partir de listas (matrices), etc., e enumeralas.

Aquí explícase o seguinte, xunto co código de mostra.

  • factorial:math.factorial()
  • Calcula o número total de permutacións
    • math.factorial()
    • scipy.special.perm()
  • Xerar e enumerar permutacións a partir dunha lista:itertools.permutations()
  • Calcula o número total de combinacións
    • math.factorial()
    • scipy.special.comb()
    • Como non usar math.factorial()
  • Xerar e enumerar combinacións a partir de listas:itertools.combinations()
  • Calcula o número total de combinacións duplicadas
  • Xerar e enumerar combinacións duplicadas a partir dunha lista:itertools.combinations_with_replacement()

Como exemplo de utilización de permutacións, tamén se explica o seguinte.

  • Crea anagramas a partir de cadeas

Se queres xerar unha combinación de elementos de varias listas en lugar dunha única lista, usa itertools.product() no módulo itertools.

factorial:math.factorial()

O módulo matemático proporciona unha función factorial() que devolve o factorial.

import math

print(math.factorial(5))
# 120

print(math.factorial(0))
# 1

Os valores negativos non enteiros darán lugar 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 o número total de permutacións

math.factorial()

As permutacións son o número de casos nos que r son escollidos entre n diferentes e colocados nunha fila.

O número total de permutacións, p, obtense mediante a seguinte ecuación utilizando factoriais.

p = n! / (n - r)!

Pódese calcular do seguinte xeito usando a función math.factorial(), que devolve o factorial. O operador ⌘, que realiza a división de enteiros, úsase para devolver un tipo de enteiro.

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 unha función scipy.special.perm() que devolve o número total de permutacións. Requírese unha instalación de SciPy separada. Dispoñible desde a versión 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
O terceiro argumento establécese como anteriormente e devolve un número de coma flotante. Teña en conta que se queres obtelo como un número enteiro, debes configuralo como segue.
exact=True

Teña en conta que só “import scipy” non cargará o módulo scipy.special.

Execute perm() como “de scipy.special import perm” como no exemplo anterior, ou executa scipy.special.perm() como “import scipy.special”.

Xerar e enumerar permutacións a partir dunha lista:itertools.permutations()

Non só se poden xerar e enumerar números totais, senón tamén permutacións a partir de listas (matrices), etc.

Use a función permutations() do módulo itertools.

Pasar un iterable (tipo de lista ou conxunto) como primeiro argumento e o número de pezas que se seleccionarán como segundo argumento devolve un iterador para esa permutación.

import itertools

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

p = itertools.permutations(l, 2)

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

Para enumeralos todos, pode usar 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')

Dado que é un iterador finito, tamén se pode converter nun tipo de lista con list().

Cando o número de elementos da lista se obtén con len(), pódese confirmar que coincide co número total de permutacións calculadas a partir do 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

Se se omite o segundo argumento, devólvese a permutación para seleccionar todos os elementos.

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

En itertools.permutations(), os elementos trátanse en función da posición, non do valor. Non se teñen en conta os valores duplicados.

l = ['a', 'a']

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

O mesmo aplícase ás seguintes funcións, descritas a continuación.

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

Calcula o número total de combinacións

math.factorial()

O número de combinacións é o número de r pezas para escoller entre n pezas diferentes. A orde non se considera como nas permutacións.

O número total de combinacións c obtense coa seguinte ecuación.

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

Pódese calcular do seguinte xeito usando a función math.factorial(), que devolve o factorial. O operador ⌘, que realiza a división de enteiros, úsase para devolver un tipo de enteiro.

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 unha función scipy.special.comb() que devolve o número total de permutacións. Requírese unha instalación de SciPy separada. Dispoñible desde a versión 0.14.0. Teña en conta que scipy.misc.comb() non implementa a repetición de argumentos descrita a continuación.

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
Do mesmo xeito que con scipy.special.perm(), o terceiro argumento establécese como anteriormente e devolve un número de coma flotante. Teña en conta que se queres obtelo como un número enteiro, debes configuralo como segue.
exact=True
O número total de combinacións duplicadas tamén se pode obter co cuarto argumento, a repetición. Isto descríbese a continuación.

De novo, teña en conta que só “import scipy” non cargará o módulo scipy.special.

Como no exemplo anterior, executa comb() como “de scipy.special import comb” ou executa scipy.special.comb() como “import scipy.special”. O mesmo aplícase a “scipy.misc”.

Como non usar math.factorial()

Outro método que usa só a biblioteca estándar e é máis rápido que o método que usa math.factorial() é o seguinte método.

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

Xerar e enumerar combinacións a partir de listas:itertools.combinations()

É posible xerar e enumerar todas as combinacións a partir de listas (matrices), etc., así como os números totais.

Use a función combinaisons() do módulo itertools.

Ao pasar un iterable (tipo de lista ou conxunto) como primeiro argumento e o número de pezas a seleccionar como segundo argumento devolve o iterador para esa combinación.

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 o número total de combinacións duplicadas

O número de combinacións duplicadas é o número de casos nos que r son escollidos entre n diferentes, permitindo duplicados.

O número total de combinacións duplicadas é igual ao número de combinacións para escoller (r) entre (n + r – 1) diferentes.

Polo tanto, podemos utilizar a función definida anteriormente para calcular o número total de combinacións.

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

print(combinations_with_replacement_count(4, 2))
# 10

En “scipy.special.comb()” descrito anteriormente, pódese obter o número total de combinacións duplicadas configurando o cuarto argumento “repetition=True.
Teña en conta que o argumento “repetición” non está implementado en “scipy.misc.comb()” nas versións anteriores a “SciPy0.14.0”.

from scipy.special import comb

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

Xerar e enumerar combinacións duplicadas a partir dunha lista:itertools.combinations_with_replacement()

É posible xerar e enumerar todas as combinacións duplicadas a partir de listas (matrices), etc., así como os números totais.

Use a función combinaisons_with_replacement() no módulo itertools.

Ao pasar un iterable (tipo de lista ou conxunto) como primeiro argumento e o número de pezas a seleccionar como segundo argumento, devolve un iterador para esa combinación superposta.

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 anagramas a partir de cadeas

Itertools.permutations() facilita a creación de permutacións de cadeas (anagramas).

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

Para combinar unha tupla dun carácter á vez nunha cadea e convertela nunha lista, faga o seguinte

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

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

Emprégase o método join(), que concatena elementos dunha lista ou tupla nunha cadea, e a notación de comprensión da lista.