Calcular e gerar factoriais, permutações e combinações em Python

O negócio

O módulo padrão de matemática para funções matemáticas em Python pode ser utilizado para calcular os factores. SciPy também tem funções para calcular o número total de permutações\combinações.

O módulo itertools também pode ser utilizado para gerar permutações e combinações a partir de listas (matrizes), etc., e enumerá-las.

O seguinte é explicado aqui, juntamente com o código da amostra.

  • factorial:math.factorial()
  • Calcular o número total de permutações
    • math.factorial()
    • scipy.special.perm()
  • Gerar e enumerar permutações a partir de uma lista:itertools.permutations()
  • Calcular o número total de combinações
    • math.factorial()
    • scipy.special.comb()
    • Como não utilizar o math.factorial()
  • Gerar e enumerar combinações a partir de listas:itertools.combinations()
  • Calcular o número total de combinações em duplicado
  • Gerar e enumerar combinações em duplicado a partir de uma lista:itertools.combinations_with_replacement()

Como exemplo de utilização de permutações, também se explica o seguinte.

  • Criar anagramas a partir de cordas

Se quiser gerar uma combinação de elementos de múltiplas listagens em vez de uma única listagem, utilize itertools.product() no módulo itertools.

factorial: math.factorial()

O módulo matemático fornece uma função factorial() que devolve o factorial.

import math

print(math.factorial(5))
# 120

print(math.factorial(0))
# 1

Valores não inteiros e negativos resultarão num ValueError.

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

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

Calcular o número total de permutações

math.factorial()

As autorizações são o número de casos em que r são escolhidos entre n diferentes e colocados em fila.

O número total de permutações, p, é obtido através da seguinte equação utilizando factores.

p = n! / (n - r)!

Pode ser calculado da seguinte forma, utilizando a função math.factorial(), que devolve o factorial. O operador ⌘, que executa a divisão inteira, é utilizado para devolver um tipo inteiro.

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 fornece uma função scipy.special.perm() que devolve o número total de permutações. É necessária uma instalação SciPy separada. Disponível a partir da versão 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 é definido como acima por defeito e devolve um número de ponto flutuante. Note que se quiser obtê-lo como um número inteiro, é necessário defini-lo como se segue.
exact=True

Note-se que apenas “importar scipy” não carregará o módulo scipy.special.

Executar perm() como “de scipy.special import perm”, como no exemplo acima, ou executar scipy.special.perm() como “importar scipy.special”.

Gerar e enumerar permutações a partir de uma lista: itertools.permutations()

Não apenas números totais, mas também permutações podem ser geradas e enumeradas a partir de listas (matrizes), etc.

Utilizar a função permutations() do módulo itertools.

A passagem de um iterável (tipo de lista ou conjunto) como primeiro argumento e o número de peças a seleccionar como segundo argumento devolve um iterador para essa permutação.

import itertools

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

p = itertools.permutations(l, 2)

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

Para enumerar todos eles, pode usar um para loop.

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

Como é um iterador finito, também pode ser convertido para um tipo de lista com lista().

Quando o número de elementos da lista é obtido com len(), pode ser confirmado que corresponde ao número total de permutações 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 o segundo argumento for omitido, a permutação para a selecção de todos os elementos é devolvida.

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

Em itertools.permutations(), os elementos são tratados com base na posição, não no valor. Os valores duplicados não são tidos em conta.

l = ['a', 'a']

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

O mesmo se aplica às seguintes funções, descritas abaixo.

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

Calcular o número total de combinações

math.factorial()

O número de combinações é o número de r peças a escolher entre n peças diferentes. A ordem não é considerada como em permutações.

O número total de combinações c é obtido através da seguinte equação.

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

Pode ser calculado da seguinte forma, utilizando a função math.factorial(), que devolve o factorial. O operador ⌘, que executa a divisão inteira, é utilizado para devolver um tipo inteiro.

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 fornece uma função scipy.special.comb() que devolve o número total de permutações. É necessária uma instalação SciPy separada. Disponível a partir da versão 0.14.0. Note-se que scipy.misc.comb() não implementa a repetição dos argumentos descritos abaixo.

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
Tal como com scipy.special.perm(), o terceiro argumento é definido como acima por defeito e devolve um número de ponto flutuante. Note que se quiser obtê-lo como um número inteiro, precisa de o definir como se segue.
exact=True
O número total de combinações duplicadas também pode ser obtido com o quarto argumento, repetição. Isto é descrito abaixo.

Mais uma vez, note que apenas “importar scipy” não irá carregar o módulo scipy.special.

Como no exemplo acima, executar comb() como “a partir de scipy.special import comb” ou executar scipy.special.comb() como “importar scipy.special”. O mesmo se aplica a “de scipy.misc”.

Como não utilizar o math.factorial()

Outro método que utiliza apenas a biblioteca padrão e é mais rápido do que o método que utiliza o 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

Gerar e enumerar combinações a partir de listas: itertools.combinations()

É possível gerar e enumerar todas as combinações a partir de listas (arrays), etc., bem como os números totais.

Utilizar a função de combinações() do módulo itertools.

A passagem de um iterável (tipo de lista ou conjunto) como primeiro argumento e o número de peças a seleccionar como segundo argumento devolve o iterador para essa combinação.

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 o número total de combinações em duplicado

O número de combinações duplicadas é o número de casos em que r são escolhidos entre n casos diferentes, permitindo duplicações.

O número total de combinações duplicadas é igual ao número de combinações a escolher (r) de (n + r – 1) combinações diferentes.

Portanto, podemos utilizar a função definida acima para calcular o número total de combinações.

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

print(combinations_with_replacement_count(4, 2))
# 10

Em “scipy.special.comb()” descrito acima, o número total de combinações duplicadas pode ser obtido através da definição do quarto argumento “repetition=True”.
Note-se que o argumento “repetição” não é implementado em “scipy.misc.comb()” em versões anteriores a “SciPy0.14.0”.

from scipy.special import comb

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

Gerar e enumerar combinações em duplicado a partir de uma lista: itertools.combinations_with_replacement()

É possível gerar e enumerar todas as combinações duplicadas a partir de listas (arrays), etc., bem como os números totais.

Utilizar a função combinações_com_substituição() no módulo itertools.

A passagem de um iterável (tipo de lista ou conjunto) como primeiro argumento e o número de peças a seleccionar como segundo argumento devolve um iterador para essa combinação sobreposta.

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

Criar anagramas a partir de cordas

Itertools.permutations() facilita a criação de permutações de cordas (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 um tuple de um carácter de cada vez numa corda e transformá-lo numa lista, faça o seguinte

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

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

É utilizado o método join(), que concatena elementos de uma lista ou tuple numa cadeia, e a notação de compreensão da lista.

Copied title and URL