Comment obtenir toutes les combinaisons possibles des éléments d’une liste?
-
19-08-2019 - |
Question
J'ai une liste de 15 chiffres et je dois écrire un code qui produit toutes les 32 768 combinaisons de ces chiffres.
J'ai trouvé du code (par Google) qui fait apparemment ce que je cherche, mais j'ai trouvé le code assez opaque et je me méfie de l'utiliser. De plus, j'ai le sentiment qu'il doit y avoir une solution plus élégante.
La seule chose qui me vient à l'esprit serait de simplement parcourir les entiers décimaux 1 & # 8211; 32768, de les convertir en fichiers binaires et d'utiliser la représentation binaire comme filtre pour choisir les nombres appropriés.
Est-ce que quelqu'un connaît un meilleur moyen? Utiliser map ()
, peut-être?
La solution
Consultez itertools.combinations :
itertools.combinations(iterable, r)
Retourne les sous-séquences de longueur r d'éléments l'entrée itérable.
Les combinaisons sont émises dans l’ordre de tri lexicographique. Donc, si le l’entrée itérable est triée, la tuples combinés seront produits dans ordre trié.
Depuis la version 2.6, les piles sont incluses!
Autres conseils
Cette réponse omis un aspect: le PO a demandé TOUTES les combinaisons ... et pas seulement les combinaisons de longueur "r".
Vous devez donc parcourir toutes les longueurs "L":
import itertools
stuff = [1, 2, 3]
for L in range(0, len(stuff)+1):
for subset in itertools.combinations(stuff, L):
print(subset)
Ou - si vous souhaitez vous mettre en colère (ou plier le cerveau de quiconque lit votre code après vous) - vous pouvez générer la chaîne de "combinaisons ()". générateurs, et itérer à travers cela:
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)
Voici un one-liner paresseux, utilisant également 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)) )
Idée principale derrière cette réponse: il y a 2 ^ N combinaisons - identique au nombre de chaînes binaires de longueur N. Pour chaque chaîne binaire, vous sélectionnez tous les éléments correspondant à un "1".
items=abc * mask=###
|
V
000 ->
001 -> c
010 -> b
011 -> bc
100 -> a
101 -> a c
110 -> ab
111 -> abc
Points à considérer:
- Cela nécessite que vous puissiez appeler
len (...)
sur leséléments
(solution de contournement: siéléments
est quelque chose qui ressemble à un élément itérable. générateur, commencez par en faire une liste avecitems = list (_itemsArg)
) - Ceci nécessite que l'ordre des itérations sur les
éléments
ne soit pas aléatoire (solution de contournement: ne soyez pas fou) - Cela nécessite que les éléments soient uniques, sinon <
{2,2,1}
et{2,1,1}
seront tous deux réduits à{ 2,1}
(solution de contournement: utilisezcollections.Counter
pour remplacer leset
; il s’agit en réalité d’un multiset ... mais vous devrez peut-être utilisez plus tardtuple (trié (Counter (...). elements ()))
si vous avez besoin que ce soit hashable)
Démo
>>> 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'}]
Dans les commentaires figurant sous le réponse de @Dan H, très prisée, il est fait mention du powerset () Recette
dans la itertools
documentation & # 8212; y compris un Dan lui-même . Cependant , personne n’a jusqu’à présent posté cette réponse. Comme c’est probablement l’une des meilleures, sinon la meilleure approche du problème & # 8212; elle est petit encouragement d'un autre intervenant, il est présenté ci-dessous. La fonction génère toutes des combinaisons uniques des éléments de liste de toutes les longueurs possibles (y compris celles contenant zéro et tous les éléments).
Remarque : si l'objectif est légèrement différent d'obtenir uniquement des combinaisons d'éléments uniques, modifiez la ligne s = list (itérable)
en s = list (set (iterable))
pour éliminer les éléments en double. Quoi qu'il en soit, le fait que iterable
soit finalement transformé en une liste
signifie qu'il fonctionnera avec des générateurs (contrairement à plusieurs autres réponses).
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))
Sortie:
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)
En voici un qui utilise la récursivité:
>>> 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']
Ce one-liner vous donne toutes les combinaisons (entre les éléments 0
et n
si la liste / le jeu d'origine contient des éléments distincts n
) et utilise la méthode native itertools.combinations
a>:
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)], [])
Le résultat sera:
[[],
['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']]
Essayez-le en ligne:
Je suis d'accord avec Dan H pour dire que Ben a effectivement demandé toutes les combinaisons. itertools.combinations ()
ne donne pas toutes les combinaisons.
Un autre problème est que, si l'entrée est itérable est grande, il est peut-être préférable de renvoyer un générateur plutôt que tout dans une liste:
iterable = range(10)
for s in xrange(len(iterable)+1):
for comb in itertools.combinations(iterable, s):
yield comb
Vous pouvez générer toutes les combinaisons d'une liste en python à l'aide de ce code simple
import itertools
a = [1,2,3,4]
for i in xrange(0,len(a)+1):
print list(itertools.combinations(a,i))
Le résultat serait:
[()]
[(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)]
Je pensais que j'ajouterais cette fonction à ceux qui recherchent une réponse sans importer d'itertools ou d'autres bibliothèques supplémentaires.
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
Utilisation du générateur de rendement simple:
for i in powerSet([1,2,3,4]):
print (i, ", ", end="")
Résultat de l'exemple d'utilisation ci-dessus:
[], [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],
Voici encore une autre solution (one-liner), impliquant l'utilisation de la fonction itertools.combinations
, mais nous utilisons ici une double compréhension (par opposition à une boucle for ou sum):
def combs(x):
return [c for i in range(len(x)+1) for c in combinations(x,i)]
Démo:
>>> 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)]
Il s'agit d'une approche facilement transférable à tous les langages de programmation prenant en charge la récursivité (aucun outil, aucun rendement, aucune compréhension de la liste) :
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]]
Cela pourrait être fait en utilisant itertools
Pour les permutations
Cette méthode prend une liste en tant qu'entrée et renvoie une liste d'objets de n-uplets contenant une permutation de longueur L sous la forme d'une liste.
# 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)
Pour la combinaison
Cette méthode prend en entrée une liste et une entrée r et renvoie une liste d'objets de n-uplets contenant toutes les combinaisons possibles de longueur r dans une liste.
# 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)
voir ceci
Vous trouverez ci-dessous une "réponse récursive standard", similaire à l'autre réponse similaire https://stackoverflow.com/a/23743696 / 711085 . (Nous n’avons pas à nous inquiéter de manquer de pile car il est impossible de traiter toutes les permutations de N!).
Il visite chaque élément à tour de rôle et le prend ou le laisse (nous pouvons voir directement la cardinalité 2 ^ N de cet algorithme).
def combs(xs, i=0):
if i==len(xs):
yield ()
return
for c in combs(xs,i+1):
yield c
yield c+(xs[i],)
Démo:
>>> 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
Ce code utilise un algorithme simple avec des listes imbriquées ...
# 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()
Je sais qu’il est bien plus pratique d’utiliser itertools pour obtenir toutes les combinaisons, mais vous pouvez y parvenir en partie avec une compréhension de liste uniquement si vous le souhaitez, si vous voulez coder beaucoup
Pour les combinaisons de deux paires:
lambda l: [(a, b) for i, a in enumerate(l) for b in l[i+1:]]
Et pour les combinaisons de trois paires, c’est aussi simple que cela:
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:]]
Le résultat est identique à l'utilisation 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)]
Sans utiliser 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']))
Voici deux implémentations de itertools.combinations
Celui qui renvoie une liste
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
On retourne un générateur
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
Notez que fournir une fonction d'assistance à ces personnes est conseillé car l'argument prepend est statique et ne change pas à chaque appel
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]]
C’est un cas très superficiel mais il vaut mieux prévenir que guérir
Qu'en est-il de ceci .. a utilisé une chaîne au lieu de liste, mais la même chose .. chaîne peut être traitée comme une liste 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)
Combinaison d'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))
Merci
Sans itertools
en Python 3, vous pourriez faire quelque chose comme ceci:
def combinations(arr, carry):
for i in range(len(arr)):
yield carry + arr[i]
yield from combinations(arr[i + 1:], carry + arr[i])
où initialement carry = "".
Utilisation de la compréhension de liste:
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 )
Le résultat serait:
['A', 'A']
['A', 'B']
['A', 'C']
['B', 'B']
['B', 'C']
['C', 'C']
Ceci est mon implémentation
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
Si quelqu'un recherche une liste inversée, comme je l'étais:
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)