¿Cómo obtener todas las combinaciones posibles de los elementos de una lista?

Tengo una lista con 15 números y necesito escribir un código que genere las 32,768 combinaciones de esos números.

He encontrado un código (por Google) que aparentemente hace lo que estoy buscando, pero el código me pareció bastante opaco y desconfío de su uso. Además, tengo la sensación de que debe haber una solución más elegante.

Lo único que se me ocurre es simplemente hacer un bucle a través de los enteros decimales 1–32768 y convertirlos en binarios, y usar la representación binaria como filtro para seleccionar los números apropiados.

¿Alguien sabe de una mejor manera? Usando map() , tal vez?

Echa un vistazo a itertools.combinaciones :

 itertools.combinations(iterable, r) 

Devuelve r longitud de las subsecuencias de los elementos desde la entrada iterable.

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

Desde 2.6, las stacks están incluidas!

Esta respuesta omitió un aspecto: el OP solicitó TODAS las combinaciones … no solo combinaciones de longitud “r”.

Así que tendrías que recorrer todas las longitudes “L”:

 import itertools stuff = [1, 2, 3] for L in range(0, len(stuff)+1): for subset in itertools.combinations(stuff, L): print(subset) 

O, si desea ser elegante (o doblar el cerebro de quien lea su código después de usted), puede generar la cadena de generadores de “combinaciones ()”, e iterar a través de eso:

 from itertools import chain, combinations def all_subsets(ss): return chain(*map(lambda x: combinations(ss, x), range(0, len(ss)+1))) for subset in all_subsets(stuff): print(subset) 

Aquí hay una sola línea perezosa, también utilizando 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)) ) 

La idea principal detrás de esta respuesta es que hay 2 ^ N combinaciones, igual que el número de cadenas binarias de longitud N. Para cada cadena binaria, seleccionas todos los elementos correspondientes a un “1”.

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

Cosas para considerar:

  • Esto requiere que pueda llamar a len(...) en los items (solución alternativa: si los items son algo así como un iterable como un generador, primero items=list(_itemsArg) en una lista con items=list(_itemsArg) )
  • Esto requiere que el orden de iteración de los items no sea aleatorio (solución alternativa: no esté loco)
  • Esto requiere que los elementos sean únicos o, de lo contrario, {2,2,1} y {2,1,1} se colapsarán en {2,1} (solución alternativa: utilice collections.Counter {2,1,1} como reemplazo para el set ; es básicamente un conjunto múltiple … aunque es posible que luego necesites usar la tuple(sorted(Counter(...).elements())) si necesitas 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'}] 

En los comentarios bajo la respuesta altamente actualizada por @Dan H, se menciona la receta powerset() en la documentación de itertools , incluida una del propio Dan . Sin embargo , hasta ahora nadie lo ha publicado como una respuesta. Dado que es probablemente uno de los mejores, si no el mejor, enfoque del problema, y ​​dado un poco de aliento por parte de otro comentarista, se muestra a continuación. La función produce todas las combinaciones únicas de los elementos de la lista de todas las longitudes posibles (incluidas las que contienen cero y todos los elementos).

Nota : Si el objective, sutilmente diferente, es obtener solo combinaciones de elementos únicos, cambie la línea s = list(iterable) a s = list(set(iterable)) para eliminar cualquier elemento duplicado. Independientemente, el hecho de que lo iterable se convierta finalmente en una list significa que funcionará con generadores (a diferencia de varias 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)) 

Salida:

 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) 

Aquí hay uno usando recursión:

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

Este one-liner le da todas las combinaciones (entre 0 y n elementos si la lista / conjunto original contiene n elementos distintos) y utiliza el método nativo itertools.combinations :

Python 2

 from itertools import combinations input = ['a', 'b', 'c', 'd'] output = sum([map(list, combinations(input, i)) for i in range(len(input) + 1)], []) 

Python 3

 from itertools import combinations input = ['a', 'b', 'c', 'd'] output = sum([list(map(list, combinations(input, i))) for i in range(len(input) + 1)], []) 

La salida será:

 [[], ['a'], ['b'], ['c'], ['d'], ['a', 'b'], ['a', 'c'], ['a', 'd'], ['b', 'c'], ['b', 'd'], ['c', 'd'], ['a', 'b', 'c'], ['a', 'b', 'd'], ['a', 'c', 'd'], ['b', 'c', 'd'], ['a', 'b', 'c', 'd']] 

Pruébalo en línea:

http://ideone.com/COghfX

Estoy de acuerdo con Dan H en que Ben de hecho pidió todas las combinaciones. itertools.combinations() no da todas las combinaciones.

Otro problema es que, si la entrada iterable es grande, quizás sea mejor devolver un generador en lugar de todo en una lista:

 iterable = range(10) for s in xrange(len(iterable)+1): for comb in itertools.combinations(iterable, s): yield comb 

Puede generar todas las combinaciones de una lista en python usando este simple código

 import itertools a = [1,2,3,4] for i in xrange(0,len(a)+1): print list(itertools.combinations(a,i)) 

El resultado sería:

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

Pensé que agregaría esta función para aquellos que buscan una respuesta sin importar itertools o cualquier otra biblioteca extra.

 def powerSet(items): """ Power set generator: get all possible combinations of a list's elements Input: items is a list Output: returns 2**n combination lists one at a time using a generator Reference: edx.org 6.00.2x Lecture 2 - Decision Trees and dynamic programming """ N = len(items) # enumerate the 2**N possible combinations for i in range(2**N): combo = [] for j in range(N): # test bit jth of integer i if (i >> j) % 2 == 1: combo.append(items[j]) yield combo 

Uso simple del generador de rendimiento:

 for i in powerSet([1,2,3,4]): print (i, ", ", end="") 

Salida del ejemplo de uso anterior:

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

Aquí hay otra solución (de una sola línea), que involucra el uso de la función itertools.combinations , pero aquí usamos una doble lista de comprensión (en oposición a un bucle for o sum):

 def combs(x): return [c for i in range(len(x)+1) for c in combinations(x,i)] 

Manifestación:

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

Se podría hacer utilizando itertools.

Para permutaciones

Este método toma una lista como entrada y devuelve una lista de objetos de tuplas que contienen permutación de longitud L en forma de lista.

 # 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) 

Para combinacion

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.

 # 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) 

ver esto

A continuación se muestra una “respuesta recursiva estándar”, similar a la otra respuesta similar https://stackoverflow.com/a/23743696/711085 . (En realidad, no tenemos que preocuparnos por quedarnos sin espacio en la stack, ya que no hay manera de que podamos procesar todas las permutaciones de N!)

Visita cada elemento a su vez, y lo toma o lo deja (podemos ver directamente la cardinalidad 2 ^ N de este algoritmo).

 def combs(xs, i=0): if i==len(xs): yield () return for c in combs(xs,i+1): yield c yield c+(xs[i],) 

Manifestación:

 >>> list( combs(range(5)) ) [(), (0,), (1,), (1, 0), (2,), (2, 0), (2, 1), (2, 1, 0), (3,), (3, 0), (3, 1), (3, 1, 0), (3, 2), (3, 2, 0), (3, 2, 1), (3, 2, 1, 0), (4,), (4, 0), (4, 1), (4, 1, 0), (4, 2), (4, 2, 0), (4, 2, 1), (4, 2, 1, 0), (4, 3), (4, 3, 0), (4, 3, 1), (4, 3, 1, 0), (4, 3, 2), (4, 3, 2, 0), (4, 3, 2, 1), (4, 3, 2, 1, 0)] >>> list(sorted( combs(range(5)), key=len)) [(), (0,), (1,), (2,), (3,), (4,), (1, 0), (2, 0), (2, 1), (3, 0), (3, 1), (3, 2), (4, 0), (4, 1), (4, 2), (4, 3), (2, 1, 0), (3, 1, 0), (3, 2, 0), (3, 2, 1), (4, 1, 0), (4, 2, 0), (4, 2, 1), (4, 3, 0), (4, 3, 1), (4, 3, 2), (3, 2, 1, 0), (4, 2, 1, 0), (4, 3, 1, 0), (4, 3, 2, 0), (4, 3, 2, 1), (4, 3, 2, 1, 0)] >>> len(set(combs(range(5)))) 32 

Este es un enfoque que se puede transferir fácilmente a todos los lenguajes de progtwigción que soportan la recursión (sin herramientas, sin rendimiento, sin listas de comprensión) :

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

Este código emplea un algoritmo simple con listas anidadas …

 # FUNCTION getCombos: To generate all combos of an input list, consider the following sets of nested lists... # # [ [ [] ] ] # [ [ [] ], [ [A] ] ] # [ [ [] ], [ [A],[B] ], [ [A,B] ] ] # [ [ [] ], [ [A],[B],[C] ], [ [A,B],[A,C],[B,C] ], [ [A,B,C] ] ] # [ [ [] ], [ [A],[B],[C],[D] ], [ [A,B],[A,C],[B,C],[A,D],[B,D],[C,D] ], [ [A,B,C],[A,B,D],[A,C,D],[B,C,D] ], [ [A,B,C,D] ] ] # # There is a set of lists for each number of items that will occur in a combo (including an empty set). # For each additional item, begin at the back of the list by adding an empty list, then taking the set of # lists in the previous column (eg, in the last list, for sets of 3 items you take the existing set of # 3-item lists and append to it additional lists created by appending the item (4) to the lists in the # next smallest item count set. In this case, for the three sets of 2-items in the previous list. Repeat # for each set of lists back to the initial list containing just the empty list. # def getCombos(listIn = ['A','B','C','D','E','F'] ): listCombos = [ [ [] ] ] # list of lists of combos, seeded with a list containing only the empty list listSimple = [] # list to contain the final returned list of items (eg, characters) for item in listIn: listCombos.append([]) # append an emtpy list to the end for each new item added for index in xrange(len(listCombos)-1, 0, -1): # set the index range to work through the list for listPrev in listCombos[index-1]: # retrieve the lists from the previous column listCur = listPrev[:] # create a new temporary list object to update listCur.append(item) # add the item to the previous list to make it current listCombos[index].append(listCur) # list length and append it to the current list itemCombo = '' # Create a str to concatenate list items into a str for item in listCur: # concatenate the members of the lists to create itemCombo += item # create a string of items listSimple.append(itemCombo) # add to the final output list return [listSimple, listCombos] # END getCombos() 

Sé que es mucho más práctico usar itertools para obtener todas las combinaciones, pero puede lograr esto en parte con solo una lista de comprensión, si así lo desea, si desea codificar mucho

Para combinaciones de dos pares:

  lambda l: [(a, b) for i, a in enumerate(l) for b in l[i+1:]] 

Y, para combinaciones de tres pares, es tan fácil como esto:

  lambda l: [(a, b, c) for i, a in enumerate(l) for ii, b in enumerate(l[i+1:]) for c in l[i+ii+2:]] 

El resultado es idéntico al uso de itertools.combinations:

 import itertools combs_3 = lambda l: [ (a, b, c) for i, a in enumerate(l) for ii, b in enumerate(l[i+1:]) for c in l[i+ii+2:] ] data = ((1, 2), 5, "a", None) print("A:", list(itertools.combinations(data, 3))) print("B:", combs_3(data)) # A: [((1, 2), 5, 'a'), ((1, 2), 5, None), ((1, 2), 'a', None), (5, 'a', None)] # B: [((1, 2), 5, 'a'), ((1, 2), 5, None), ((1, 2), 'a', None), (5, 'a', None)] 

Sin usar itertools:

 def combine(inp): return combine_helper(inp, [], []) def combine_helper(inp, temp, ans): for i in range(len(inp)): current = inp[i] remaining = inp[i + 1:] temp.append(current) ans.append(tuple(temp)) combine_helper(remaining, temp, ans) temp.pop() return ans print(combine(['a', 'b', 'c', 'd'])) 

¿Qué tal esto? … usé una cadena en lugar de una lista, pero lo mismo … una cadena puede tratarse como una lista en Python:

 def comb(s, res): if not s: return res.add(s) for i in range(0, len(s)): t = s[0:i] + s[i + 1:] comb(t, res) res = set() comb('game', res) print(res) 

Combinación de itertools

 import itertools col_names = ["aa","bb", "cc", "dd"] all_combinations = itertools.chain(*[itertools.combinations(col_names,i+1) for i,_ in enumerate(col_names)]) print(list(all_combinations)) 

Gracias

Sin itertools en Python 3 podrías hacer algo como esto:

 def combinations(arr, carry): for i in range(len(arr)): yield carry + arr[i] yield from combinations(arr[i + 1:], carry + arr[i]) 

donde inicialmente carry = "".

Usando la lista de comprensión:

 def selfCombine( list2Combine, length ): listCombined = str( ['list2Combine[i' + str( i ) + ']' for i in range( length )] ).replace( "'", '' ) \ + 'for i0 in range(len( list2Combine ) )' if length > 1: listCombined += str( [' for i' + str( i ) + ' in range( i' + str( i - 1 ) + ', len( list2Combine ) )' for i in range( 1, length )] )\ .replace( "', '", ' ' )\ .replace( "['", '' )\ .replace( "']", '' ) listCombined = '[' + listCombined + ']' listCombined = eval( listCombined ) return listCombined list2Combine = ['A', 'B', 'C'] listCombined = selfCombine( list2Combine, 2 ) 

La salida sería:

 ['A', 'A'] ['A', 'B'] ['A', 'C'] ['B', 'B'] ['B', 'C'] ['C', 'C'] 

Esta es mi implementacion

  def get_combinations(list_of_things): """gets every combination of things in a list returned as a list of lists Should be read : add all combinations of a certain size to the end of a list for every possible size in the the list_of_things. """ list_of_combinations = [list(combinations_of_a_certain_size) for possible_size_of_combinations in range(1, len(list_of_things)) for combinations_of_a_certain_size in itertools.combinations(list_of_things, possible_size_of_combinations)] return list_of_combinations 

Aquí hay dos implementaciones de itertools.combinations

Uno que devuelve una lista.

 def combinations(lst, depth, start=0, items=[]): if depth <= 0: return [items] out = [] for i in range(start, len(lst)): out += combinations(lst, depth - 1, i + 1, items + [lst[i]]) return out 

Se devuelve un generador.

 def combinations(lst, depth, start=0, prepend=[]): if depth <= 0: yield prepend else: for i in range(start, len(lst)): for c in combinations(lst, depth - 1, i + 1, prepend + [lst[i]]): yield c 

Tenga en cuenta que se recomienda proporcionar una función de ayuda a esos usuarios, ya que el argumento de prefijo es estático y no cambia con cada llamada.

 print([c for c in combinations([1, 2, 3, 4], 3)]) # [[1, 2, 3], [1, 2, 4], [1, 3, 4], [2, 3, 4]] # get a hold of prepend prepend = [c for c in combinations([], -1)][0] prepend.append(None) print([c for c in combinations([1, 2, 3, 4], 3)]) # [[None, 1, 2, 3], [None, 1, 2, 4], [None, 1, 3, 4], [None, 2, 3, 4]] 

Este es un caso muy superficial, pero es mejor prevenir que lamentar.

 def combinations(iterable, r): # combinations('ABCD', 2) --> AB AC AD BC BD CD # combinations(range(4), 3) --> 012 013 023 123 pool = tuple(iterable) n = len(pool) if r > n: return indices = range(r) yield tuple(pool[i] for i in indices) while True: for i in reversed(range(r)): if indices[i] != i + n - r: break else: return indices[i] += 1 for j in range(i+1, r): indices[j] = indices[j-1] + 1 yield tuple(pool[i] for i in indices) x = [2, 3, 4, 5, 1, 6, 4, 7, 8, 3, 9] for i in combinations(x, 2): print i 

Si alguien está buscando una lista invertida, como yo:

 stuff = [1, 2, 3, 4] def reverse(bla, y): for subset in itertools.combinations(bla, len(bla)-y): print list(subset) if y != len(bla): y += 1 reverse(bla, y) reverse(stuff, 1)