Obtenga todas las combinaciones posibles (2^N) de los elementos de una lista, de cualquier longitud

Tengo una lista con 15 números. ¿Cómo puedo producir las 32.768 combinaciones de esos números (es decir, cualquier número de elementos, en el orden original)?

Pensé en recorrer los números enteros decimales del 1 al 32768 y usar la representación binaria de cada número como filtro para seleccionar los elementos de la lista apropiados. Hay una mejor manera de hacerlo?

_{Para combinaciones de una longitud específica , consulte Obtener todas (n-elegir-k) combinaciones de longitud n . Utilice esa pregunta para cerrar duplicados cuando corresponda.}

_{Al cerrar preguntas sobre combinatoria como duplicados, es muy importante asegurarse de lo que realmente quiere OP, no de las palabras que se usaron para describir el problema. Es extremadamente común que las personas que quieren, por ejemplo, un producto cartesiano (consulte Cómo obtener el producto cartesiano de varias listas ) pregunten sobre "combinaciones".}

Jan 21 '09 18:01 Ben

Eche un vistazo a itertools.combinations :

itertools.combinations(iterable, r)

Devuelve subsecuencias de r longitud de elementos del iterable de entrada.

Las combinaciones se emiten en orden lexicográfico. Entonces, si el iterable de entrada está ordenado, las tuplas combinadas se producirán en orden.

¡Desde 2.6, las baterías están incluidas!

Jan 21 '2009 11:01 James Brady

En los comentarios bajo la respuesta altamente votada de @Dan H, se menciona la powerset()receta en la itertoolsdocumentación , incluida una del propio Dan . Sin embargo , hasta ahora nadie lo ha publicado como respuesta. Dado que probablemente sea uno de los mejores, si no el mejor, enfoque para el problema, y ​​con el apoyo de otro comentarista, se muestra a continuación. La función produce todas las combinaciones únicas de los elementos de la lista de cada longitud posible (incluidas aquellas que contienen cero y todos los elementos).

Nota : Si el objetivo, sutilmente diferente, es obtener solo combinaciones de elementos únicos, cambie la línea s = list(iterable)para s = list(set(iterable))eliminar cualquier elemento duplicado. Independientemente, el hecho de que iterablefinalmente se convierta en un listmedio funcionará con generadores (a diferencia de muchas de las otras respuestas).

from itertools import chain, combinations

def powerset(iterable):
    "powerset([1,2,3]) --> () (1,) (2,) (3,) (1,2) (1,3) (2,3) (1,2,3)"
    s = list(iterable)  # allows duplicate elements
    return chain.from_iterable(combinations(s, r) for r in range(len(s)+1))

stuff = [1, 2, 3]
for i, combo in enumerate(powerset(stuff), 1):
    print('combo #{}: {}'.format(i, combo))

Producción:

combo #1: ()
combo #2: (1,)
combo #3: (2,)
combo #4: (3,)
combo #5: (1, 2)
combo #6: (1, 3)
combo #7: (2, 3)
combo #8: (1, 2, 3)

Dec 06 '2016 01:12 martineau

Este es un enfoque que se puede transferir fácilmente a todos los lenguajes de programación que admitan la recursividad (sin itertools, sin rendimiento, sin comprensión de listas) :

def combs(a):
    if len(a) == 0:
        return [[]]
    cs = []
    for c in combs(a[1:]):
        cs += [c, c+[a[0]]]
    return cs

>>> combs([1,2,3,4,5])
[[], [1], [2], [2, 1], [3], [3, 1], [3, 2], ..., [5, 4, 3, 2, 1]]

Feb 01 '2019 13:02 Jonathan R

Aquí hay una frase perezosa, que también usa itertools:

from itertools import compress, product

def combinations(items):
    return ( set(compress(items,mask)) for mask in product(*[[0,1]]*len(items)) )
    # alternative:                      ...in product([0,1], repeat=len(items)) )

Idea principal detrás de esta respuesta: hay 2 ^ N combinaciones, igual que el número de cadenas binarias de longitud N. Para cada cadena binaria, selecciona todos los elementos correspondientes a un "1".

items=abc * mask=###
 |
 V
000 -> 
001 ->   c
010 ->  b
011 ->  bc
100 -> a
101 -> a c
110 -> ab
111 -> abc

Cosas para considerar:

• Esto requiere que puedas llamar len(...)( itemssolución alternativa: si itemses algo así como un iterable como un generador, conviértelo primero en una lista con items=list(_itemsArg))
• Esto requiere que el orden de iteración itemsno sea aleatorio (solución alternativa: no se vuelva loco)
• Esto requiere que los elementos sean únicos, de lo contrario, {2,2,1}ambos {2,1,1}colapsarán {2,1}(solución alternativa: úselo collections.Countercomo un reemplazo directo para set; es básicamente un conjunto múltiple... aunque es posible que necesite usarlo más adelante tuple(sorted(Counter(...).elements()))si necesita que sea hashable)

Manifestación

>>> list(combinations(range(4)))
[set(), {3}, {2}, {2, 3}, {1}, {1, 3}, {1, 2}, {1, 2, 3}, {0}, {0, 3}, {0, 2}, {0, 2, 3}, {0, 1}, {0, 1, 3}, {0, 1, 2}, {0, 1, 2, 3}]

>>> list(combinations('abcd'))
[set(), {'d'}, {'c'}, {'c', 'd'}, {'b'}, {'b', 'd'}, {'c', 'b'}, {'c', 'b', 'd'}, {'a'}, {'a', 'd'}, {'a', 'c'}, {'a', 'c', 'd'}, {'a', 'b'}, {'a', 'b', 'd'}, {'a', 'c', 'b'}, {'a', 'c', 'b', 'd'}]

Jul 01 '2011 00:07 ninjagecko