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 enteros decimales 1–32768 y usar la representación binaria de cada número como filtro para seleccionar los elementos de lista apropiados. Hay una mejor manera de hacerlo?

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

_{Al cerrar preguntas sobre combinatoria como duplicados, es muy importante asegurarse de qué OP realmente quiere, no 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”.}

Mira esto itertools.combinaciones:

itertools.combinations(iterable, r)

Devuelve r subsecuencias de elementos de la entrada iterable.

Las combinaciones se emiten en orden de clasificación lexicográfico. Entonces, si la entrada iterable está ordenada, las tuplas de combinación se producirán en orden ordenado.

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

Aquí hay una sola línea 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, elige 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 pueda llamar len(...) en items (solución alternativa: si items es algo así como un iterable como un generador, primero conviértalo en una lista con items=list(_itemsArg))
• Esto requiere que el orden de iteración en items no es aleatorio (solución: no te vuelvas loco)
• Esto requiere que los artículos sean únicos, o de lo contrario {2,2,1} y {2,1,1} ambos colapsarán a {2,1} (solución alternativa: usar collections.Counter como 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'}]

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

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]]

Aquí hay uno usando recursividad:

>>> import copy
>>> def combinations(target,data):
...     for i in range(len(data)):
...         new_target = copy.copy(target)
...         new_data = copy.copy(data)
...         new_target.append(data[i])
...         new_data = data[i+1:]
...         print new_target
...         combinations(new_target,
...                      new_data)
...                      
... 
>>> target = []
>>> data = ['a','b','c','d']
>>> 
>>> combinations(target,data)
['a']
['a', 'b']
['a', 'b', 'c']
['a', 'b', 'c', 'd']
['a', 'b', 'd']
['a', 'c']
['a', 'c', 'd']
['a', 'd']
['b']
['b', 'c']
['b', 'c', 'd']
['b', 'd']
['c']
['c', 'd']
['d']