repeticion - permutaciones python

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

Question

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 a 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?

Answer 1

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

Answer 2

A continuación se muestra una "respuesta recursiva estándar", similar a otra respuesta similar https://.com/a/23743696/711085 . (De manera realista, no tenemos que preocuparnos por quedarnos sin espacio en la pila, 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

Answer 3

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 esas personas, ya que el argumento de prepéndulo 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.

Answer 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 suma):

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

Answer 5

Aquí hay un perezoso de una sola línea, 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)) )

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

Answer 6

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

Answer 7

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

Answer 8

Echa un vistazo a itertools.combinations :

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 pilas están incluidas!

Answer 9

En los comentarios bajo la answer altamente actualizada de @Dan H, se menciona la receta de 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 objetivo, 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. En cualquier caso, 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)

Answer 10

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

Answer 11

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 (e.g., 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 (e.g., 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()

Answer 12

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

from itertools import combinations

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

output = sum([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

Answer 13

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

Answer 14

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

Answer 15

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

Answer 16

Se podría hacer usando 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 this

Answer 17

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)

Answer 18

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

Answer 19

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

Answer 20

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)

Answer 21

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

Answer 22

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 = "".

Answer 23

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