Obtenez toutes les combinaisons possibles (2^N) des éléments d'une liste, de n'importe quelle longueur

Question

J'ai une liste de 15 nombres. Comment puis-je produire les 32 768 combinaisons de ces nombres (c'est-à-dire, n'importe quel nombre d'éléments, dans l'ordre original) ?

J'ai pensé à parcourir les entiers décimaux de 1 à 32768 et à utiliser la représentation binaire de chaque nombre comme filtre pour sélectionner les éléments de liste appropriés. Y a-t-il une meilleure façon de le faire ?

---

_{Pour les combinaisons <strong>d'une longueur spécifique</strong>, consultez <a href="https://stackoverflow.com/questions/27974126">Obtenir toutes les combinaisons de longueur n-choose-k de longueur n</a>. Veuillez utiliser cette question pour fermer les doublons si nécessaire.}

_{Lorsque vous fermez des questions sur la combinatoire en tant que doublons, il est très important de s'assurer de ce que l'OP <strong>veut réellement, pas</strong> les termes qui ont été utilisés pour décrire le problème. Il est extrêmement courant que les personnes qui veulent, par exemple, un produit cartésien (voir <a href="https://stackoverflow.com/questions/533905">Comment obtenir le produit cartésien de plusieurs listes</a>) posent des questions sur les "combinaisons".}

Answer 1

Cette réponse a omis un aspect : l'OP a demandé TOUTES les combinaisons ... pas seulement les combinaisons de longueur "r".

Donc, vous devriez soit parcourir toutes les longueurs "L":

import itertools

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

Ou - si vous voulez être élégant (ou faire travailler le cerveau de celui qui lira votre code après vous) - vous pouvez générer la chaîne des générateurs "combinations()", et itérer à travers ceux-ci :

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)

Answer 2

Jetez un œil à itertools.combinations:

itertools.combinations(iterable, r)

Retourne des sous-séquences de longueur r d'éléments de l'itérable d'entrée.

Les combinaisons sont émises dans l'ordre de tri lexicographique. Donc, si l'itérable d'entrée est trié, les tuples de combinaison seront produits dans l'ordre trié.

Depuis 2.6, les piles sont incluses !

Answer 3

Voici une ligne paresseuse, 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 -- autant que le 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

Choses à considérer:

• Cela nécessite que vous puissiez appeler len(...) sur items (contournement: si items est quelque chose comme un itérable comme un générateur, transformez-le d'abord en liste avec items=list(_itemsArg))
• Cela nécessite que l'ordre d'itération sur items ne soit pas aléatoire (contournement: ne soyez pas insensé)
• Cela nécessite que les éléments soient uniques, sinon {2,2,1} et {2,1,1} se réduiront tous deux à {2,1} (contournement: utilisez collections.Counter comme un remplacement direct pour set; c'est essentiellement un multi-ensemble... bien que vous deviez peut-être ensuite utiliser tuple(sorted(Counter(...).elements())) si vous avez besoin qu'il soit hashable)

---

Démonstration

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

Answer 4

Cette expression en une ligne vous donne toutes les combinaisons (entre 0 et n éléments si la liste/ensemble contient n éléments distincts) et utilise la méthode native 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)], [])

---

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:

http://ideone.com/COghfX

Answer 5

Je suis d'accord avec Dan H que Ben a effectivement demandé toutes les combinaisons. itertools.combinations() ne donne pas toutes les combinaisons.

Un autre problème est que si l'itérable d'entrée est grand, il est peut-être préférable de renvoyer un générateur au lieu de tout mettre dans une liste :

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