Wie alle möglichen Kombinationen von einer Liste der Elemente zu bekommen?

https://stackoverflow.com/questions/464864

19-08-2019
|

Frage

Ich habe eine Liste mit 15 Zahlen, und ich brauche einige Code zu schreiben, der alle 32.768 Kombinationen aus diesen Zahlen hervorbringt.

Ich habe festgestellt,

Lösung

Hier finden Sie aktuelle itertools.combinations :

itertools.combinations(iterable, r)
Zurück r Länge Sequenzen von Elementen aus   der Eingang iterable.

Auch Kombinationen sind in lexikographischer Sortierreihenfolge ausgegeben. Also, wenn die   Eingabe iterable sortiert ist, die   Kombination Tupeln produziert werden in   sortierter Reihenfolge.

Seit 2.6 Batterien enthalten sind!

Andere Tipps

Diese Antwort verpassten einen Aspekt. die OP für alle Kombinationen gefragt ... nicht nur Kombinationen von Länge „r“

So können Sie entweder eine Schleife durch alle Längen "L" haben würde:

import itertools

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

oder - wenn Sie pfiffigen erhalten möchten (oder das Gehirn zu beugen wer auch immer Ihr Code, nachdem Sie liest) - die Kette von „Kombinationen ()“ erzeugen können Generatoren und durchlaufen, dass:

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)

Hier ist ein fauler Einzeiler, auch itertools mit:

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

Hauptidee hinter dieser Antwort. Gibt es 2 ^ N Kombinationen - gleich der Anzahl von binären Strings der Länge N. Für jede binäre Zeichenfolge, Sie alle Elemente auswählen, entsprechend einer „1“

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

Zu beachten:

Dies erfordert, dass Sie len(...) auf items nennen kann (Abhilfe: Wenn items ist so etwas wie ein iterable wie ein Generator, schalten Sie ihn in eine Liste zuerst mit items=list(_itemsArg))
Dies erfordert, dass die Reihenfolge der Iteration auf items nicht zufällig ist (Abhilfe: nicht verrückt sein)
Dies erfordert, dass die Einzelteile sind einzigartig, sonst {2,2,1} und {2,1,1} sowohl Zusammenbruch {2,1} (Abhilfe: Verwendung collections.Counter als Drop-in-Ersatz für set, es ist im Grunde ein multiset ... wenn Sie später benötigen tuple(sorted(Counter(...).elements())) verwenden wenn Sie müssen es sein hashable)

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

In den Kommentaren unter dem hoch upvoted von @ Dan H beantworten, erwähnt wird das powerset() Rezept in der gemacht itertools Dokumentation -einschließlich eines von Dan selbst . Jedoch , hat bisher niemand es als Antwort geschrieben. Da es wahrscheinlich eines der besseren, wenn nicht der beste Ansatz für die ist problemlos und wenig Ermutigung von einem anderen Kommentator, wird es weiter unten. Die Funktion erzeugt alle einzigartige Kombinationen der Listenelemente von alle Länge möglich (einschließlich solche, die Null und alle Elemente).

Hinweis : Wenn das, auf subtile Weise anders, Ziel nur Kombinationen verschiedenen Elemente zu erhalten, ist die Zeile s = list(iterable) ändern s = list(set(iterable)) alle doppelten Elemente zu eliminieren. Unabhängig davon, dass der iterable schließlich in eine list gedreht wird bedeutet, dass es mit Generatoren arbeitet (im Gegensatz zu einigen der anderen Antworten).

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

Ausgabe:

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)

Hier ist eine Verwendung von Rekursion:

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

Dieser Einzeiler gibt Ihnen alle Kombinationen (zwischen 0 und n Einzelteilen, wenn die ursprüngliche Liste / set n verschiedene Elemente enthält) 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)], [])

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

Versuchen Sie es online:

http://ideone.com/COghfX

ich mit Dan H einig, dass Ben in der Tat gefragt, für alle Kombinationen. itertools.combinations() nicht alle Kombinationen geben.

Ein weiteres Problem ist, wenn der Eingang iterable groß ist, ist es vielleicht besser ist, einen Generator, anstatt alles in einer Liste zurück:

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

Sie können alle Kombinationen aus einer Liste in Python mit diesem einfachen Code zu erzeugen

import itertools

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

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

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

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 Yield Generator Verbrauch:

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

Die Ausgabe von Anwendungsbeispiel oben:

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

Hier ist noch eine andere Lösung (Einzeiler), an denen die itertools.combinations Funktion verwenden, aber hier benutzen wir eine doppelte Liste Verständnis (als for-Schleife oder die Summe zu einem gegen):

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

Dies ist ein Ansatz, der auf alle Programmiersprachen unterstützt Rekursion (keine itertools, keinen Ertrag, keine Liste Verständnis) leicht übertragen werden können:

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

Es getan werden könnte, mit itertools

Für Permutationen

Dieses Verfahren nimmt eine Liste als eine Eingabe und das Rück eine Objektliste von Tupeln, die Permutation der Länge L in einer Listenform enthalten.

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

Für Kombination

Dieses Verfahren nimmt eine Liste und einen Eingang R als Eingangs- und Rück eine Objektliste von Tupeln, die alle möglichen Kombinationen der Länge r in einer Listenform enthalten.

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

finden Sie unter diese

Im Folgenden finden Sie eine „Standard-rekursive Antwort“, ähnlich wie die anderen ähnlichen Antwort https://stackoverflow.com/a/23743696/ 711.085 . (Wir nicht realistisch aus Stapelspeicher über das Laufen zu kümmern, da keine Möglichkeit, es könnten wir alle N! Permutationen verarbeiten.)

Es besucht jedes Element wiederum, und entweder dauert es oder läßt es (wir direkt die 2 ^ N Mächtigkeit von diesem Algorithmus sehen).

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

Dieser Code verwendet einen einfachen Algorithmus mit verschachtelten Listen ...

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

Ich weiß, es ist viel praktischer itertools nutzen, um die alle die Kombinationen, aber Sie können erreichen dies zum Teil mit nur Liste Verständnis, wenn Sie so geschehen zu wünschen übrig, gewähren Sie viel

codieren wollen

Bei Kombinationen von zwei Paaren:

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

Und für Kombinationen von drei Paaren, es ist so einfach wie folgt aus:

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

Das Ergebnis ist identisch mit 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)]

Ohne itertools mit:

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

Hier sind zwei Implementierungen von itertools.combinations

Eine, die eine Liste zurückgibt

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

Ein gibt einen Generator

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

Bitte beachten Sie, dass eine Hilfsfunktion, die die empfohlen wird, weil das prepend Argument statisch ist und nicht bei jedem Aufruf zu ändern

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

Dies ist ein sehr oberflächlicher Fall aber besser sicher als traurig

Wie .. über dieses eine Zeichenfolge statt Liste verwendet, aber gleiche Sache .. String kann wie eine Liste in Python behandelt werden:

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)

Die Kombination von 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))

Danke

Ohne itertools in Python 3 Sie so etwas tun könnte:

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

Dabei steht zunächst carry = "".

Mit Liste Verständnis:

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 )

Ausgabe wäre:

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

Dies ist meine Implementierung

    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

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

Wenn jemand für eine umgekehrte Liste suchen, wie ich war:

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)

Lizenziert unter: CC-BY-SA mit Zuschreibung

Nicht verbunden mit StackOverflow