Faire toutes les combinaisons possibles d'une liste

Question

Je dois être en mesure de créer une liste contenant toutes les combinaisons possibles d'une liste saisie. Par exemple, la liste [1,2,3] devrait retourner [1 [1,2] [1,3] 2 [2,3] 3 [1,2,3]] La liste ne doit pas nécessairement être dans un ordre particulier. Sur ce site, j'ai trouvé de nombreuses fonctions utilisant la fonction itertools mais ce sont des objets qui reviennent quand j'ai besoin d'une simple list .

Answer 1

Il suffit d'utiliser itertools.combinations . Par exemple :

import itertools

lst = [1, 2, 3]
combs = []

for i in xrange(1, len(lst)+1):
    combs.append(i)
    els = [list(x) for x in itertools.combinations(lst, i)]
    combs.append(els)

Maintenant combs détient cette valeur :

[1, [[1], [2], [3]], 2, [[1, 2], [1, 3], [2, 3]], 3, [[1, 2, 3]]]

Oui, c'est légèrement différent de l'exemple de sortie que vous avez fourni, mais dans cette sortie vous n'avez pas listé toutes les combinaisons possibles.

J'indique la taille de la combinaison avant la liste réelle pour chaque taille, si ce dont vous avez besoin est simplement les combinaisons (sans la taille, comme il apparaît dans votre exemple de sortie), alors essayez ces autres versions du code :

import itertools

lst = [1, 2, 3]
combs = []

for i in xrange(1, len(lst)+1):
    els = [list(x) for x in itertools.combinations(lst, i)]
    combs.extend(els)

Maintenant combs détient cette valeur :

[[1], [2], [3], [1, 2], [1, 3], [2, 3], [1, 2, 3]]

Answer 2

El itertools Le module renvoie en effet générateurs au lieu de listes, mais :

• Les générateurs sont souvent plus efficaces que les listes (surtout si vous générez un grand nombre de combinaisons).
• Vous pouvez toujours convertir les générateurs en listes en utilisant list(...) quand vous en avez vraiment besoin.

El chain y combinations fonctions de itertools bien travailler mais vous devez utiliser Python 2.6 ou supérieur :

import itertools

def all_combinations(any_list):
    return itertools.chain.from_iterable(
        itertools.combinations(any_list, i + 1)
        for i in xrange(len(any_list)))

Vous pouvez alors l'appeler comme tel :

# as a generator
all_combinations([1,2,3])  # --> <itertools.chain at 0x10ef7ce10>

# as a list
list(all_combinations([1,2,3]))  # --> [(1,), (2,), (3,), (1, 2), (1, 3), (2, 3), (1, 2, 3)]

# as a list of lists
[list(l) for l in all_combinations([1,2,3])]  # --> [[1], [2], [3], [1, 2], [1, 3], [2, 3], [1, 2, 3]]

Si vous n'avez jamais utilisé de générateurs auparavant, notez que vous les parcourez en boucle comme s'il s'agissait d'une liste, comme ceci :

# a generator returned instead of list
my_combinations = all_combinations([1,2,3])

# this would also work if `my_combinations` were a list
for c in my_combinations:
    print "Combo", c

"""
Prints:
  Combo (1,)
  Combo (2,)
  Combo (3,)
  Combo (1, 2)
  Combo (1, 3)
  Combo (2, 3)
  Combo (1, 2, 3)
"""

La différence de performance peut être spectaculaire. Si vous comparez les performances, vous verrez que le générateur est beaucoup plus rapide à créer :

# as a generator
all_combinations(range(25))  # timing: 100000 loops, best of 3: 2.53 µs per loop

# as a list
list(all_combinations(range(25)))  # timing: 1 loops, best of 3: 9.37 s per loop

Notez que l'itération de toutes les combinaisons prendrait encore un certain temps dans les deux cas, mais cela peut être une grande victoire pour vous, surtout si vous trouvez rapidement ce que vous cherchez.

Answer 3

Les fonctions du module itertools renvoient des itérateurs. Tout ce que vous devez faire pour les convertir en listes est d'appeler list() sur le résultat.

Cependant, puisque vous devrez appeler itertools.combinations trois fois distinctes (une fois pour chaque longueur différente), vous pouvez simplement utiliser la fonction list.extend pour ajouter tous les éléments de l'itérateur à votre liste finale.

Essayez ce qui suit :

import itertools
in_list = [1, 2, 3]
out_list = []
for i in range(1, len(in_list)+1):
    out_list.extend(itertools.combinations(in_list, i))

Ou comme une compréhension de liste :

out_list = [c for i in range(len(in_list)) for c in itertools.combinations(in_list, i+1)]

Vous obtiendrez ainsi la liste suivante :

[(1,), (2,), (3,), (1, 2), (1, 3), (2, 3), (1, 2, 3)]

Si vous voulez des listes au lieu de tuples, et pour convertir les tuples de longueur unique en une seule valeur, vous pouvez faire ce qui suit :

out_list = [x[0] if len(x) == 1 else list(x) for x in out_list]
# [1, 2, 3, [1, 2], [1, 3], [2, 3], [1, 2, 3]]

Ou de laisser les éléments individuels sous forme de listes :

out_list = map(list, out_list)

Answer 4

l = [1,2,3]
combs = reduce(lambda x, y: list(itertools.combinations(l, y)) + x, range(len(l)+1), [])

Si vous voulez un oneliner.

Answer 5

Je pense qu'il vaut la peine de résumer les autres réponses en un simple exemple Python 3 :

from itertools import chain, combinations

def all_combinations(array):
    return chain(*(list(combinations(array, i + 1)) for i in range(len(array))))

Cela renvoie un itérable, pour afficher les valeurs :

>>> print(list(all_combinations((1, 2, 3))))
[(1,), (2,), (3,), (1, 2), (1, 3), (2, 3), (1, 2, 3)]