Python proporciona métodos directos para encontrar permutaciones y combinaciones de una secuencia. Estos métodos están presentes en el paquete itertools.
Permutación
Primero importe el paquete itertools para implementar el método de permutaciones en Python. Este método toma una lista como entrada y devuelve una lista de objetos de tuplas que contienen todas las permutaciones en forma de lista.
Python3
# A Python program to print all> # permutations using library function> from> itertools>import> permutations> # Get all permutations of [1, 2, 3]> perm>=> permutations([>1>,>2>,>3>])> # Print the obtained permutations> for> i>in> list>(perm):> >print> (i)> |
>
>
Producción:
(1, 2, 3) (1, 3, 2) (2, 1, 3) (2, 3, 1) (3, 1, 2) (3, 2, 1)>
Complejidad del tiempo: O(n!), donde n es la longitud de la lista de entrada. ¡Esto se debe a que hay n! permutaciones de n elementos, y el programa las genera e imprime todas.
Espacio auxiliar: O(n!), ya que el programa necesita almacenar todos los n! permutaciones en la memoria antes de imprimirlas. Específicamente, la variable permanente creada al llamar a permutaciones ([1, 2, 3]) almacena todos los n! permutaciones en la memoria como una lista.
Genera n! permutaciones si la longitud de la secuencia de entrada es n.
Si desea obtener permutaciones de longitud L, impleméntelo de esta manera.
Python3
rj12 frente a rj11
# A Python program to print all> # permutations of given length> from> itertools>import> permutations> # Get all permutations of length 2> # and length 2> perm>=> permutations([>1>,>2>,>3>],>2>)> # Print the obtained permutations> for> i>in> list>(perm):> >print> (i)> |
>
>
Producción:
(1, 2) (1, 3) (2, 1) (2, 3) (3, 1) (3, 2)>
La complejidad temporal de este programa es O(n^r) donde n es la longitud de la matriz de entrada y r es la longitud de las permutaciones que se generarán.
La complejidad del espacio también es O (n^r) ya que todas las permutaciones se almacenan en la memoria antes de imprimir.
Genera nCr*r! permutaciones si la longitud de la secuencia de entrada es n y el parámetro de entrada es r.
Combinación
Este método toma una lista y una entrada r como entrada y devuelve una lista de objetos de tuplas que contienen todas las combinaciones posibles de longitud r en forma de lista.
Python3
# A Python program to print all> # combinations of given length> from> itertools>import> combinations> # Get all combinations of [1, 2, 3]> # and length 2> comb>=> combinations([>1>,>2>,>3>],>2>)> # Print the obtained combinations> for> i>in> list>(comb):> >print> (i)> |
>
>
Producción:
(1, 2) (1, 3) (2, 3)>
1. Las combinaciones se emiten en orden lexicográfico de entrada. Entonces, si la lista de entrada está ordenada, las tuplas combinadas se producirán en orden ordenado.
Python3
# A Python program to print all> # combinations of a given length> from> itertools>import> combinations> # Get all combinations of [1, 2, 3]> # and length 2> comb>=> combinations([>1>,>2>,>3>],>2>)> # Print the obtained combinations> for> i>in> list>(comb):> >print> (i)> |
>
>
Producción:
(1, 2) (1, 3) (2, 3)>
2. Los elementos se tratan como únicos según su posición, no según su valor. Entonces, si los elementos de entrada son únicos, no habrá valores repetidos en cada combinación.
Python3
# A Python program to print all combinations> # of given length with unsorted input.> from> itertools>import> combinations> # Get all combinations of [2, 1, 3]> # and length 2> comb>=> combinations([>2>,>1>,>3>],>2>)> # Print the obtained combinations> for> i>in> list>(comb):> >print> (i)> |
>
>
Producción:
(2, 1) (2, 3) (1, 3)>
3. Si queremos hacer una combinación del mismo elemento con el mismo elemento entonces usamos combinaciones_con_reemplazo.
Python3
# A Python program to print all combinations> # with an element-to-itself combination is> # also included> from> itertools>import> combinations_with_replacement> # Get all combinations of [1, 2, 3] and length 2> comb>=> combinations_with_replacement([>1>,>2>,>3>],>2>)> # Print the obtained combinations> for> i>in> list>(comb):> >print> (i)> |
>
>
Producción:
(1, 1) (1, 2) (1, 3) (2, 2) (2, 3) (3, 3)>