Haciendo todas las combinaciones posibles de una lista.

Necesito poder hacer una lista que contenga todas las combinaciones posibles de una lista ingresada. Por ejemplo, la lista [1,2,3] debe devolver [1 [1,2] [1,3] 2 [2,3] 3 [1,2,3]] La lista no tiene que estar en ningún orden particular. En este sitio, he encontrado muchas funciones que utilizan itertools pero son objetos que devuelven cuando solo necesito una list .

Simplemente use itertools.combinations . Por ejemplo:

 import itertools lst = [1, 2, 3] combs = [] for i in xrange(1, len(lst)+1): combs.append(i) els = [list(x) for x in itertools.combinations(lst, i)] combs.append(els) 

Ahora combs tiene este valor:

 [1, [[1], [2], [3]], 2, [[1, 2], [1, 3], [2, 3]], 3, [[1, 2, 3]]] 

Sí, es ligeramente diferente de la salida de muestra que proporcionó, pero en esa salida no estaba enumerando todas las combinaciones posibles.

Estoy enumerando el tamaño de la combinación antes de la lista real para cada tamaño, si lo que necesita es simplemente las combinaciones (sin el tamaño, como aparece en la salida de muestra), pruebe estas otras versiones del código:

 import itertools lst = [1, 2, 3] combs = [] for i in xrange(1, len(lst)+1): els = [list(x) for x in itertools.combinations(lst, i)] combs.extend(els) 

Ahora combs tiene este valor:

 [[1], [2], [3], [1, 2], [1, 3], [2, 3], [1, 2, 3]] 

El módulo de itertools hecho devuelve generadores en lugar de listas, pero:

  • Los generadores suelen ser más eficientes que las listas (especialmente si está generando un gran número de combinaciones)
  • Siempre puede convertir los generadores a listas usando la list(...) cuando realmente lo necesite.

La chain y las funciones de combinations de itertools funcionan bien , pero necesitas usar Python 2.6 o superior:

 import itertools def all_combinations(any_list): return itertools.chain.from_iterable( itertools.combinations(any_list, i + 1) for i in xrange(len(any_list))) 

A continuación, puede llamar a esto como tal:

 # as a generator all_combinations([1,2,3]) # -->  # as a list list(all_combinations([1,2,3])) # --> [(1,), (2,), (3,), (1, 2), (1, 3), (2, 3), (1, 2, 3)] # as a list of lists [list(l) for l in all_combinations([1,2,3])] # --> [[1], [2], [3], [1, 2], [1, 3], [2, 3], [1, 2, 3]] 

Si no ha usado generadores anteriormente, tenga en cuenta que los recorre como si fueran una lista, como esta:

 # a generator returned instead of list my_combinations = all_combinations([1,2,3]) # this would also work if `my_combinations` were a list for c in my_combinations: print "Combo", c """ Prints: Combo (1,) Combo (2,) Combo (3,) Combo (1, 2) Combo (1, 3) Combo (2, 3) Combo (1, 2, 3) """ 

La diferencia de rendimiento puede ser dramática. Si comparas el rendimiento, verás que el generador es mucho más rápido de crear:

 # as a generator all_combinations(range(25)) # timing: 100000 loops, best of 3: 2.53 µs per loop # as a list list(all_combinations(range(25))) # timing: 1 loops, best of 3: 9.37 s per loop 

Tenga en cuenta que aún tomará algún tiempo para recorrer todas las combinaciones en ambos casos, pero puede ser una gran ganancia para usted, especialmente si encuentra lo que está buscando desde el principio.

Podría resolver su problema usando itertools.combinations dentro de un bucle:

 >>> l = [1,2,3] >>> comb = [] >>> for i in range(len(l)): ... comb += itertools.combinations(l,i+1) ... >>> comb [(1,), (2,), (3,), (1, 2), (1, 3), (2, 3), (1, 2, 3)] 

Y si los quieres como lista:

 >>> comb_list = [ list(t) for t in comb ] >>> comb_list [[1], [2], [3], [1, 2], [1, 3], [2, 3], [1, 2, 3]] 

EDITAR: El primer parámetro de las combinaciones es el iterable y el segundo es la longitud de las tuplas resultantes (en este caso, va de 1 a len(l) ).

Más sobre combinaciones: http://docs.python.org/library/itertools.html#itertools.combinations

Las funciones del módulo itertools devuelven iteradores. Todo lo que necesita hacer para convertirlos en listas es la list() llamadas list() en el resultado.

Sin embargo, ya que tendrá que llamarlo itertools.combinations tres veces distintas (una vez para cada longitud diferente), puede usar list.extend para agregar todos los elementos del iterador a su lista final.

Intente lo siguiente:

 import itertools in_list = [1, 2, 3] out_list = [] for i in range(1, len(in_list)+1): out_list.extend(itertools.combinations(in_list, i)) 

O como una lista de comprensión:

 out_list = [c for i in range(len(in_list)) for c in itertools.combinations(in_list, i+1)] 

Estos resultarán en la siguiente lista:

 [(1,), (2,), (3,), (1, 2), (1, 3), (2, 3), (1, 2, 3)] 

Si desea listas en lugar de tuplas, y para convertir las tuplas de una sola longitud a solo el valor, puede hacer lo siguiente:

 out_list = [x[0] if len(x) == 1 else list(x) for x in out_list] # [1, 2, 3, [1, 2], [1, 3], [2, 3], [1, 2, 3]] 

O dejar los elementos individuales como listas:

 out_list = map(list, out_list) 
 l = [1,2,3] combs = reduce(lambda x, y: list(itertools.combinations(l, y)) + x, range(len(l)+1), []) 

Si quieres un oneliner.