Generar todas las permutaciones de todas las longitudes

Question

¿Cómo generaría todas las posibles permutaciones de la lista b(1,6,8,3,9,5) incluyendo las de diferente longitud? Ejemplo:

List a = [1,2,3] 
generateperms(a) 
1,2,3 
3,1,2 
3,2,1 
1,3,2 
2,1,3 
2,3,1 
2,3 
1,2 
1,3 
2,1 
3,2 
3,1 

¿Y así sucesivamente y obtener todas las permutariones de cada longitud?

EDIT: sólo voy a usar esto, escrito en Python, funciona bastante bien:

import itertools 
a = ['a','b','c'] 
for i in range(len(a)): 
    print list(itertools.permutations(a,i+1)) 

Answer 1

Creo que serían todas las permutaciones de cada subconjunto.

La manera más fácil de devolver subconjuntos es considerar todos los enteros binarios desde 0 (el conjunto vacío) a través de la longitud de su lista de entrada (el conjunto completo). Por lo tanto, cuenta desde 0 hasta 2**(length(input)) y usa los resultados para enmascarar todos los elementos para excluir de ese subconjunto en particular.

Desde allí, debería poder utilizar cualquiera de los muchos ejemplos de código en la red para las permutaciones de retorno.

Answer 2

yo sugeriría comenzando con algo más simple. Supongamos que l es una lista con n elementos. Primero, ¿puedes escribir una función para generar todas las permutaciones de l que tengan una longitud fija de k? Entonces, ¿puede encontrar una forma de llamar a esa función repetidamente con diferentes valores k para generar las permutaciones de longitud 0, todas las permutaciones de longitud 1, todas las permutaciones de longitud 2, y así sucesivamente hasta llegar a n?

Answer 3

En general, una lista de longitud n tiene n! arreglos o permutaciones. Entonces con longitudes múltiples, tendríamos n! ​​(N-k)! donde k es 0 < k < n.

Answer 4

Considere la implementación recursiva de generar todas las permutaciones de una cadena. Si almacena las subpermanentes a medida que las construye, tendrá todas las que desee.

en Erlang, como punto de partida (que es una versión modificada de 3.3 Permutations)

perms([]) -> [[]]; 
perms(L) -> 
    [ [H|T] || H <- L, T <- perms(L -- [H])] 
    ++ [ [T] || H <- L, T <- perms(L -- [H]) ]. 

pero tenga en cuenta que esto te deja con duplicados y un montón de matrices de matrices vacías que usted tiene que quitar a hacer que la salida sea más bonita.

Answer 5

Anteriormente mencioné que inventé, en Python, una horrible expresión lambda para generar todos los subconjuntos de una secuencia usando el bin() número entero de la función incorporada de cadena binaria que agregaron en 2.6.

Aquí está la versión más feo de la misma:

subsets = lambda s: (
    (s[x] for x,c in 
     enumerate("0" * (len(s)-len(bin(i)[2:])) + bin(i)[2:]) 
     if int(c)) 
    for i in range(0,2**len(s) 
    ) 
) 

pero me di cuenta de que puedo reemplazar la parte "0" * ... +" de esa expresión con una simple llamada al método de la cadena zfill() (gracias SO User: gimel). De manera que se convierte en el poco menos odiosa:

subsets = lambda s: (
     [s[x] for x,c in 
       enumerate(bin(i)[2:].zfill(len(s))) 
       if int(c) 
       ] 
     for i in range(0,2**len(s)) 
    ) 

Esto, a pesar de sus apariencias, es un relativamente simple aplicación de lo que he descrito: dada la cadena binaria que representa cualquier número entero desde cero hasta el tamaño de nuestro conjunto, enmascarar cualquier de los elementos correspondientes a ceros en nuestra cadena binaria. Esa es la comprensión de la lista interna.La expresión externa (generador) simplemente cubre el rango necesario.

El enfoque del OP de usar itertools.permutations() con dos argumentos es más elegante. Podría haberlo pensado si hubiera visto la cadena __doc__ para esa función. Sin embargo, tuve que pasar un poco de tiempo para convencerme de que ambos enfoques dan los mismos resultados.