Come ottenere tutte le possibili combinazioni di un elenco di elementi?

Question

Ho un elenco con 15 numeri e ho bisogno di scrivere del codice che produca tutte le 32.768 combinazioni di quei numeri.

Ho trovato del codice (di Google) che apparentemente fa quello che sto cercando, ma ho trovato il codice abbastanza opaco e diffido nell'usarlo. Inoltre ho la sensazione che ci debba essere una soluzione più elegante.

L'unica cosa che mi viene in mente sarebbe semplicemente scorrere gli interi decimali 1 & # 8211; 32768 e convertirli in binari e usare la rappresentazione binaria come filtro per selezionare i numeri appropriati.

Qualcuno sa di un modo migliore? Usando map () , forse?

Answer 1

Dai un'occhiata a itertools.combinations :

itertools.combinations(iterable, r)

     

Restituisce le sottosequenze di lunghezza r degli elementi da   l'input iterabile.

     

Le combinazioni sono emesse in ordine lessicografico. Quindi, se il   input iterable è ordinato, il   verranno prodotte tuple combinate in   ordine ordinato.

Dal 2.6, le batterie sono incluse!

Answer 2

Questa risposta ha perso un aspetto: l'OP ha chiesto TUTTE le combinazioni ... non solo le combinazioni di lunghezza "r".

Quindi dovresti o passare in rassegna tutte le lunghezze " L " ;:

import itertools

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

Oppure - se vuoi diventare snazzy (o piegare il cervello di chi legge il tuo codice dopo di te) - puoi generare la catena di " combinazioni () " generatori e iterate attraverso quello:

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 3

Ecco un one-lazy pigro, usando anche 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)) )

L'idea principale dietro questa risposta: ci sono 2 ^ N combinazioni - uguale al numero di stringhe binarie di lunghezza N. Per ogni stringa binaria, scegli tutti gli elementi corrispondenti a un " 1 " ;.

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

Aspetti da considerare:

• Questo richiede che tu possa chiamare len (...) su items (soluzione alternativa: se items è qualcosa di simile a un iterabile come un generatore, prima trasformalo in un elenco con items = list (_itemsArg) )
• Ciò richiede che l'ordine di iterazione su elementi non sia casuale (soluzione alternativa: non essere pazzo)
• Ciò richiede che gli elementi siano univoci, altrimenti {2,2,1} e {2,1,1} verranno entrambi compressi in { 2,1} (soluzione alternativa: utilizzare collections.Counter come sostituto drop-in per set ; è fondamentalmente un multiset ... anche se potrebbe essere necessario successivamente usa tuple (ordinato (Counter (...). elements ())) se ne hai bisogno per essere hash)

---

Demo

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

Nei commenti sotto la risposta altamente votata di @Dan H, viene menzionato il powerset () nella itertools documentazione & # 8212; di cui uno di Dan stesso . Tuttavia , finora nessuno lo ha pubblicato come risposta. Dato che è probabilmente uno dei migliori se non il migliore approccio al problema & # 8212; e dato un piccolo incoraggiamento da un altro commentatore, è mostrato di seguito. La funzione produce tutto combinazioni uniche degli elementi dell'elenco di ogni lunghezza possibile (compresi quelli che contengono zero e tutti gli elementi).

Nota : se l'obiettivo, leggermente diverso, è ottenere solo combinazioni di elementi univoci, modificare la riga s = list (iterable) in s = list (set (iterable)) per eliminare eventuali elementi duplicati. Indipendentemente da ciò, il fatto che iterable sia in definitiva trasformato in un list significa che funzionerà con i generatori (a differenza di molte altre risposte).

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

Output:

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 5

Eccone uno che usa la ricorsione:

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

Questo one-liner ti offre tutte le combinazioni (tra 0 e n se l'elenco / set originale contiene n elementi distinti) e utilizza il metodo 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)], [])

---

L'output sarà:

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

---

Provalo online:

http://ideone.com/COghfX

Answer 7

Sono d'accordo con Dan H sul fatto che Ben abbia effettivamente chiesto tutte combinazioni. itertools.combinations () non fornisce tutte le combinazioni.

Un altro problema è che, se l'input iterabile è grande, è forse meglio restituire un generatore invece di tutto in un elenco:

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

Answer 8

Puoi generare tutte le combinazioni di un elenco in Python usando questo semplice codice

import itertools

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

Il risultato sarebbe:

[()]
[(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 9

Ho pensato di aggiungere questa funzione per chi cerca una risposta senza importare itertools o altre librerie 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

Utilizzo semplice del generatore di rendimento:

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

Output dall'esempio di utilizzo sopra:

  

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

Ecco un'altra soluzione (one-liner), che prevede l'uso della funzione itertools.combinations , ma qui usiamo una doppia comprensione del listino (al contrario di un ciclo for o sum):

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

---

Demo:

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

Questo è un approccio che può essere facilmente trasferito in tutti i linguaggi di programmazione che supportano la ricorsione (nessun itertools, nessuna resa, nessuna comprensione dell'elenco) :

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

Answer 12

Potrebbe essere fatto usando itertools

Per permutazioni

Questo metodo accetta un elenco come input e restituisce un elenco di oggetti di tuple che contengono permutazione della lunghezza L in un modulo elenco.

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

Per combinazione

Questo metodo accetta un elenco e un input r come input e restituisce un elenco di oggetti di tuple che contengono tutte le possibili combinazioni di lunghezza r in un modulo elenco.

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

vedi this

Answer 13

Di seguito è riportata una "risposta ricorsiva standard", simile all'altra risposta simile https://stackoverflow.com/a/23743696 / 711085 . (Non dobbiamo realisticamente preoccuparci di rimanere senza spazio di stack poiché non è possibile elaborare tutte le permutazioni N!)

Visita ogni elemento a sua volta e lo prende o lo lascia (possiamo vedere direttamente la cardinalità 2 ^ N da questo 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],)

---

Demo:

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

Questo codice utilizza un semplice algoritmo con elenchi nidificati ...

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

So che è molto più pratico usare itertools per ottenere le tutte le combinazioni, ma tu puoi raggiungerlo in parte con solo una comprensione dell'elenco se ti capita di desiderare, a condizione che tu voglia codificare molto

Per combinazioni di due coppie:

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

E, per combinazioni di tre coppie, è facile come questo:

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

---

Il risultato è identico all'utilizzo di 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

Senza usare 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 17

Ecco due implementazioni di itertools.combinations

Uno che restituisce un elenco

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

Uno restituisce un generatore

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

Si noti che fornire una funzione di supporto a questi è consigliato perché l'argomento prepend è statico e non cambia con ogni chiamata

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

Questo è un caso molto superficiale, ma è meglio prevenire che curare

Answer 18

Che ne dici di questo ... ho usato una stringa invece della lista, ma la stessa cosa .. stringa può essere trattata come una lista in 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 19

Combinazione di 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))

Grazie

Answer 20

Senza itertools in Python 3 potresti fare qualcosa del genere:

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

dove inizialmente carry = " " ;.

Answer 21

Utilizzo della comprensione dell'elenco:

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 )

L'output sarebbe:

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

Answer 22

Questa è la mia implementazione

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

Answer 24

Se qualcuno è alla ricerca di un elenco invertito, come me:

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)