Wie alle möglichen Kombinationen von einer Liste der Elemente zu bekommen?
-
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 : 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!
itertools.combinations(iterable, r)
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(...)
aufitems
nennen kann (Abhilfe: Wennitems
ist so etwas wie ein iterable wie ein Generator, schalten Sie ihn in eine Liste zuerst mititems=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: Verwendungcollections.Counter
als Drop-in-Ersatz fürset
, es ist im Grunde ein multiset ... wenn Sie später benötigentuple(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:
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 wollenBei 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)