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

Ont un coup d'oeil à itertools.combinaisons:

itertools.combinations(iterable, r)

Retour r longueur de sous-séquences d'éléments de
l'entrée itératif.

Combinaisons sont émis dans l'ordre de tri lexicographique. Donc, si l'
entrée itérable est triée, les
la combinaison des n-uplets sera produite dans
l'ordre de tri.

Depuis la 2.6, les piles sont inclus!

Voici un paresseux one-liner, également à l'aide de 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 -- même que le nombre de chaînes binaires de longueur N. Pour chaque chaîne binaire, vous choisissez 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

Choses à considérer:

• Cela nécessite que vous pouvez appeler len(...) sur items (solution de contournement: si items est quelque chose comme un objet iterable comme un générateur, la transformer en une liste d'abord avec items=list(_itemsArg))
• Cela exige que l'ordre d'itération sur items n'est pas aléatoire (solution: ne pas être aliéné)
• Cela nécessite que les objets sont uniques, ou d'autre {2,2,1} et {2,1,1} permettra à la fois de l'effondrement du {2,1} (solution de contournement: utilisez collections.Counter que d'une baisse-dans le remplacement pour set; c'est essentiellement un multiset... mais vous devrez peut-être utiliser plus tard tuple(sorted(Counter(...).elements())) si vous en avez besoin pour être 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'}]

Ici est en utilisant 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 Ben en effet demandé pour tous combinaisons. itertools.combinations() ne donne pas toutes les combinaisons.

Une autre question est, si l'entrée itérable est grand, il est peut-être mieux de retourner un générateur au lieu de tout dans une liste:

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

J'ai pensé que je voudrais ajouter cette fonction pour ceux qui cherchent une réponse sans import itertools ou toutes les 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

De Rendement Simple Utilisation D'Un Générateur:

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

Sortie à partir de l'Utilisation de l'exemple 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] ,

Il pourrait être fait à l'aide de itertools

Pour les permutations

Cette méthode prend une liste en entrée et retourne un objet de la liste de tuples contenant permutation de longueur L dans un formulaire de 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 une liste et une entrée r en entrée et renvoie un objet de la liste de tuples qui contiennent toutes les combinaisons possibles de longueur r dans une forme de 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 cette

Ci-dessous est un "standard récursive réponse", à l'instar des autres semblables réponse https://stackoverflow.com/a/23743696/711085 . (Nous n'avons pas réellement avoir à vous soucier de manquer d'espace de pile car il n'y a aucun moyen que nous pourrions traiter tous les N! permutations.)

Il visite chaque élément à son tour, et, soit qu'il le prend ou laisse (on peut voir directement la 2^N la cardinalité 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

Je sais que c'est beaucoup plus pratique à utiliser itertools pour obtenir le tous les combinaisons, mais vous peut résultats s'expliquent en partie avec seulement la compréhension de liste si vous arriver à souhait, certes vous souhaitez code 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 des 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'aide de itertools.combinaisons:

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

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

Veuillez noter que le fait de fournir une fonction d'assistance à personnes est conseillé parce que le préfixe argument est statique et n'est pas en train de changer avec 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 très superficiel cas, mais mieux vaut prévenir que guérir

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

Grâce

L'aide de la liste de compréhension:

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 )

Sortie:

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

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