Comment obtenir toutes les combinaisons possibles des éléments d’une liste?

StackOverflow https://stackoverflow.com/questions/464864

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

Était-ce utile?

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 avec items = 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: utilisez collections.Counter pour remplacer le set ; il s’agit en réalité d’un multiset ... mais vous devrez peut-être utilisez plus tard tuple (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']

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)
Licencié sous: CC-BY-SA avec attribution
Non affilié à StackOverflow
scroll top