Toutes les combinaisons d'une liste de listes

Question

Je suis essentiellement à la recherche d'une version python de Combinaison de List<List<int>>

Étant donné une liste de listes, j'ai besoin d'une nouvelle liste qui donne toutes les combinaisons possibles d'éléments entre les listes.

[[1,2,3],[4,5,6],[7,8,9,10]] -> [[1,4,7],[1,4,8],...,[3,6,10]]

Le nombre de listes est inconnu, j'ai donc besoin de quelque chose qui fonctionne pour tous les cas. Des points bonus pour l'élégance !

Answer 1

Vous avez besoin itertools.product :

>>> import itertools
>>> a = [[1,2,3],[4,5,6],[7,8,9,10]]
>>> list(itertools.product(*a))
[(1, 4, 7), (1, 4, 8), (1, 4, 9), (1, 4, 10), (1, 5, 7), (1, 5, 8), (1, 5, 9), (1, 5, 10), (1, 6, 7), (1, 6, 8), (1, 6, 9), (1, 6, 10), (2, 4, 7), (2, 4, 8), (2, 4, 9), (2, 4, 10), (2, 5, 7), (2, 5, 8), (2, 5, 9), (2, 5, 10), (2, 6, 7), (2, 6, 8), (2, 6, 9), (2, 6, 10), (3, 4, 7), (3, 4, 8), (3, 4, 9), (3, 4, 10), (3, 5, 7), (3, 5, 8), (3, 5, 9), (3, 5, 10), (3, 6, 7), (3, 6, 8), (3, 6, 9), (3, 6, 10)]

Answer 2

La solution la plus élégante est d'utiliser itertools.product dans python 2.6.

Si vous n'utilisez pas Python 2.6, la documentation de itertools.product présente une fonction équivalente pour effectuer le produit de manière "manuelle" :

def product(*args, **kwds):
    # product('ABCD', 'xy') --> Ax Ay Bx By Cx Cy Dx Dy
    # product(range(2), repeat=3) --> 000 001 010 011 100 101 110 111
    pools = map(tuple, args) * kwds.get('repeat', 1)
    result = [[]]
    for pool in pools:
        result = [x+[y] for x in result for y in pool]
    for prod in result:
        yield tuple(prod)

Answer 3

listOLists = [[1,2,3],[4,5,6],[7,8,9,10]]
for list in itertools.product(*listOLists):
  print list;

J'espère que vous trouverez cela aussi élégant que moi lorsque je l'ai rencontré pour la première fois.

Answer 4

Il n'y a rien de mal à utiliser la récursion directe pour cette tâche, et si vous avez besoin d'une version qui fonctionne avec des chaînes de caractères, cela pourrait répondre à vos besoins :

combinations = []

def combine(terms, accum):
    last = (len(terms) == 1)
    n = len(terms[0])
    for i in range(n):
        item = accum + terms[0][i]
        if last:
            combinations.append(item)
        else:
            combine(terms[1:], item)

>>> a = [['ab','cd','ef'],['12','34','56']]
>>> combine(a, '')
>>> print(combinations)
['ab12', 'ab34', 'ab56', 'cd12', 'cd34', 'cd56', 'ef12', 'ef34', 'ef56']

Answer 5

Numpy peut le faire :

 >>> import numpy
 >>> a = [[1,2,3],[4,5,6],[7,8,9,10]]
 >>> [list(x) for x in numpy.array(numpy.meshgrid(*a)).T.reshape(-1,len(a))]
[[ 1, 4, 7], [1, 5, 7], [1, 6, 7], ....]