Wie erhält man alle möglichen Kombinationen der Elemente einer Liste?

Question

Ich habe eine Liste mit 15 Zahlen, und ich muss einen Code schreiben, der alle 32.768 Kombinationen dieser Zahlen erzeugt.

Ich habe gefunden einige Codes (durch Googeln), die anscheinend tut, was ich suche, aber ich fand den Code ziemlich undurchsichtig und bin vorsichtig, es zu benutzen. Außerdem habe ich das Gefühl, dass es eine elegantere Lösung geben muss.

Das Einzige, was mir einfällt, wäre, einfach eine Schleife durch die Dezimalzahlen 1-32768 zu ziehen und diese in Binärzahlen umzuwandeln, und die Binärdarstellung als Filter zu verwenden, um die entsprechenden Zahlen herauszufiltern.

Kennt jemand einen besseren Weg? Verwendung von map() vielleicht?

Answer 1

Hier ist eine, die Rekursion verwendet:

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

Dieser Einzeiler gibt Ihnen alle Kombinationen (zwischen 0 y n Elemente, wenn die ursprüngliche Liste/der ursprüngliche Satz Folgendes enthält n verschiedene Elemente) und verwendet die native Methode 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)], [])

---

Die Ausgabe wird sein:

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

---

Probieren Sie es online aus:

http://ideone.com/COghfX

Answer 3

Mit diesem einfachen Code können Sie alle Kombinationen einer Liste in Python erzeugen:

import itertools

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

Das Ergebnis wäre:

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

Ich dachte, ich würde diese Funktion für diejenigen hinzufügen, die eine Antwort suchen, ohne itertools oder andere zusätzliche Bibliotheken zu importieren.

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

Einfacher Renditegenerator Verwendung:

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

Ausgabe des obigen Verwendungsbeispiels:

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

Ich stimme mit Dan H. überein, dass Ben in der Tat darum gebeten hat todos Kombinationen. itertools.combinations() gibt nicht alle Kombinationen an.

Ein weiteres Problem ist, dass es vielleicht besser ist, einen Generator anstelle einer Liste zurückzugeben, wenn die Eingabe-Iterable groß ist:

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