Permutação e combinação em Python

Python fornece métodos diretos para encontrar permutações e combinações de uma sequência. Esses métodos estão presentes no pacote itertools.

Permutação

Primeiro, importe o pacote itertools para implementar o método permutations() em python. Este método recebe uma lista como entrada e retorna uma lista de objetos de tuplas que contém todas as permutações em uma forma de lista.

# Um programa Python para imprimir todas as
# permutações usando a função da biblioteca itertools
from itertools import permutations

# Obtem todas as permutações de [1, 2, 3]  
perm = permutations([1, 2, 3])

# Imprime as permutações
for i in list(perm):
    print(i) 

Resultado:

(1, 2, 3)
(1, 3, 2)
(2, 1, 3)
(2, 3, 1)
(3, 1, 2)
(3, 2, 1)

Ele gera n! permutações se o comprimento da sequência de entrada for n.

Se quiser obter permutações de comprimento L, implemente-o desta forma.

# Um programa Python para imprimir todos as
# permutações de determinado comprimento
from itertools import permutations

# Obtem todas as permutações de tamanho 2
# e tamanho 2
perm = permutations([1, 2, 3], 2)

# imprime as permutações
for i in list(perm):
    print(i) 

Resultado:

(1, 2)
(1, 3)
(2, 1)
(2, 3)
(3, 1)
(3, 2)

Ele gera nCr * r! permutações se o comprimento da sequência de entrada for n e o parâmetro de entrada for r.

Combinações

Este método pega uma lista e uma entrada r como entrada e retorna uma lista de objetos de tuplas que contém todas as combinações possíveis de comprimento r em uma forma de lista.

# Um programa Python para imprimir todas as
# combinações de determinado comprimento
from itertools import combinations

# Obtem todas as combinações de [1, 2, 3] 
# e tamanho 2
comb = combinations([1, 2, 3], 2)

# imprime todas as combinações
for i in list(comb):
    print (i)

Resultado:

(1, 2)
(1, 3)
(2, 3)

1. As combinações são emitidas em ordem de classificação lexicográfica de entrada. Portanto, se a lista de entrada for classificada, as tuplas de combinação serão produzidas em ordem classificada.

   # Um programa Python para imprimir todas as
   # combinações de um determinado comprimento
   from itertools import combinations  
     
   # Obtem todas as combinações de [1, 2, 3]  
   # e tamanho 2  
   comb = combinations([1, 2, 3], 2)
   
   # Imprime as combinações
   for i in list(comb):
       print (i)
   

   Resultado:

   (2, 1)
   (2, 3)
   (1, 3)
   

2. Os elementos são tratados como únicos com base em sua posição, não em seu valor. Portanto, se os elementos de entrada forem exclusivos, não haverá valores de repetição em cada combinação.

   # Um programa Python para imprimir todas as combinações
   # de determinado comprimento com entrada não classificada. 
   from itertools import combinations  
     
   # Obtem todas as combinações de [2, 1, 3]  
   # e tamanho 2  
   comb = combinations([2, 1, 3], 2)
   
   # imprime as combinações
   for i in list(comb):
       print(i)
   

   Resultado:

   (2, 1)
   (2, 3)
   (1, 3)
   

3. Se quisermos fazer combinações do mesmo elemento para o mesmo elemento, usamos combinations_with_replacement.

   # Um programa Python para imprimir todas as combinações
   # com uma combinação com o próprio elemento
   # também é incluído 
   from itertools import combinations_with_replacement
   
   # Obtem todas as combinações de [1, 2, 3] e tamanho 2
   comb = combinations_with_replacement([1, 2, 3], 2)
   
   # Imprime as combinações
   for i in list(comb):
       print(i)
   

   Resultado:

   (1, 1)
   (1, 2)
   (1, 3)
   (2, 2)
   (2, 3)
   (3, 3)
   

Artigo escrito por Raju Varshney e traduzido por Acervo Lima de Permutation and Combination in Python