Calcular y generar factoriales, permutaciones y combinaciones en Python

Negocio

El módulo estándar math para funciones matemáticas en Python se puede utilizar para calcular factoriales. SciPy también tiene funciones para calcular el número total de permutaciones\combinaciones.

El módulo itertools también puede utilizarse para generar permutaciones y combinaciones a partir de listas (arrays), etc., y enumerarlas.

Aquí se explica lo siguiente, junto con un código de ejemplo.

  • factorial:math.factorial()
  • Calcular el número total de permutaciones
    • math.factorial()
    • scipy.special.perm()
  • Generar y enumerar permutaciones a partir de una lista:itertools.permutations()
  • Calcular el número total de combinaciones
    • math.factorial()
    • scipy.special.comb()
    • Cómo no usar math.factorial()
  • Generar y enumerar combinaciones a partir de listas:itertools.combinations()
  • Calcular el número total de combinaciones duplicadas
  • Generar y enumerar combinaciones duplicadas a partir de una lista:itertools.combinations_with_replacement()

Como ejemplo de utilización de las permutaciones, también se explica lo siguiente.

  • Crear anagramas a partir de cadenas

Si desea generar una combinación de elementos de varios listados en lugar de un único listado, utilice itertools.product() en el módulo itertools.

factorial: math.factorial()

El módulo matemático proporciona una función factorial() que devuelve el factorial.

import math

print(math.factorial(5))
# 120

print(math.factorial(0))
# 1

Los valores negativos no enteros 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

Calcular el número total de permutaciones

math.factorial()

Las permutaciones son el número de casos en los que se eligen r de entre n diferentes y se colocan en una fila.

El número total de permutaciones, p, se obtiene mediante la siguiente ecuación utilizando factoriales.

p = n! / (n - r)!

Se puede calcular de la siguiente manera utilizando la función math.factorial(), que devuelve el factorial. El operador ⌘, que realiza la división de enteros, se utiliza para devolver un tipo de entero.

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ón scipy.special.perm() que devuelve el número total de permutaciones. Se requiere una instalación separada de SciPy. Disponible a partir de la 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
El tercer argumento se establece como arriba por defecto y devuelve un número de punto flotante. Tenga en cuenta que si desea obtenerlo como un número entero, debe configurarlo de la siguiente manera.
exact=True

Tenga en cuenta que sólo «importar scipy» no cargará el módulo scipy.special.

Ejecuta perm() como «from scipy.special import perm» como en el ejemplo anterior, o ejecuta scipy.special.perm() como «import scipy.special».

Generar y enumerar permutaciones a partir de una lista: itertools.permutations()

No sólo se pueden generar y enumerar números totales, sino también permutaciones de listas (arrays), etc.

Utilice la función permutations() del módulo itertools.

Pasando un iterable (tipo lista o conjunto) como primer argumento y el número de piezas a seleccionar como segundo argumento devuelve 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 enumerarlas todas, puede utilizar 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 es un iterador finito, también se puede convertir a un tipo de lista con list().

Cuando se obtiene el número de elementos de la lista con len(), se puede confirmar que coincide con el número total de permutaciones calculado 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 se omite el segundo argumento, se devuelve la permutación para seleccionar todos los 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(), los elementos se tratan en función de la posición, no del valor. Los valores duplicados no se tienen en cuenta.

l = ['a', 'a']

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

Lo mismo ocurre con las siguientes funciones, que se describen a continuación.

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

Calcular el número total de combinaciones

math.factorial()

El número de combinaciones es el número de r piezas a elegir entre n piezas diferentes. El orden no se considera como en las permutaciones.

El número total de combinaciones c se obtiene mediante la siguiente ecuación.

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

Se puede calcular de la siguiente manera utilizando la función math.factorial(), que devuelve el factorial. El operador ⌘, que realiza la división de enteros, se utiliza para devolver un tipo de entero.

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ón scipy.special.comb() que devuelve el número total de permutaciones. Se requiere una instalación separada de SciPy. Disponible a partir de la versión 0.14.0. Tenga en cuenta que scipy.misc.comb() no implementa la 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
Al igual que con scipy.special.perm(), el tercer argumento se establece como arriba por defecto y devuelve un número de punto flotante. Tenga en cuenta que si quiere obtenerlo como un entero, debe configurarlo de la siguiente manera.
exact=True
El número total de combinaciones duplicadas también puede obtenerse con el cuarto argumento, la repetición. Esto se describe a continuación.

De nuevo, ten en cuenta que sólo «import scipy» no cargará el módulo scipy.special.

Como en el ejemplo anterior, ejecute comb() como «from scipy.special import comb» o ejecute scipy.special.comb() como «import scipy.special». Lo mismo se aplica a «scipy.misc».

Cómo no usar math.factorial()

Otro método que utiliza sólo la biblioteca estándar y es más rápido que el método que utiliza math.factorial() es el siguiente 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

Generar y enumerar combinaciones a partir de listas: itertools.combinations()

Es posible generar y enumerar todas las combinaciones a partir de listas (arrays), etc., así como los números totales.

Utilice la función combinations() del módulo itertools.

Pasando un iterable (tipo lista o conjunto) como primer argumento y el número de piezas a seleccionar como segundo argumento devuelve el 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

Calcular el número total de combinaciones duplicadas

El número de combinaciones duplicadas es el número de casos en los que se eligen r de entre n diferentes, teniendo en cuenta los duplicados.

El número total de combinaciones duplicadas es igual al número de combinaciones a elegir (r) de entre (n + r – 1) diferentes.

Por lo tanto, podemos utilizar la función definida anteriormente para calcular el número total de combinaciones.

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, el número total de combinaciones duplicadas puede obtenerse estableciendo el cuarto argumento «repetition=True».
Tenga en cuenta que el argumento «repetición» no está implementado en «scipy.misc.comb()» en versiones anteriores a «SciPy0.14.0».

from scipy.special import comb

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

Generar y enumerar combinaciones duplicadas a partir de una lista: itertools.combinations_with_replacement()

Es posible generar y enumerar todas las combinaciones duplicadas de las listas (arrays), etc. así como los números totales.

Utilice la función combinations_with_replacement() del módulo itertools.

Pasando un iterable (tipo lista o conjunto) como primer argumento y el número de piezas a seleccionar como segundo argumento devuelve un iterador para esa combinación superpuesta.

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

Crear anagramas a partir de cadenas

Itertools.permutations() facilita la creación de permutaciones de cadenas (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 una tupla de un carácter a la vez en una cadena y convertirla en una lista, haz lo siguiente

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

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

Se utiliza el método join(), que concatena elementos de una lista o tupla en una cadena, y la notación de comprensión de listas.

Copied title and URL