Combiner plusieurs listes

Bonjour,

Je me heurte au problème suivant:

Je voudrais développer une fonction à laquelle je passerai un nombre illimité de liste et qui ferait le traitement suivant:

Exemple de listes passées en paramètres : [a,b] , [c,d,e,f] , [g,h,i]
Résultat attendu : [[a,c,g], [a,c,h], [a,c,i], [a,d,g], [a,d,h], [a,d,i], .... , [b,c,g], [b,c,h], [b,c,i], ... ]

Bref, vous l'aurez compris, je souhaiterais pouvoir déterminer toutes les combinaisons possible des éléments des listes passées en paramètres de la fonction.

Si vous pouviez me donner des pistes, ça serait super.
Merci d'avance de votre aide. :D

Bonjour,

Voilà une solution possible (Python 2.7), adaptée d'un de mes tutos (http://python.jpvweb.com/mesrecettes...les_imbriquees) :
Code:

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 def combmultiboucles(L): """""" # on fabrique les critères des boucles n = len(L) boucles = [] for l in L: boucles.append([0, len(l), 1]) compteurs = [x[0] for x in boucles] # initialisation compteurs de boucle compteurs[-1] -= boucles[-1][2] # le 1er incrément sera pour rien indmax = len(boucles)-1 # index de la dernière boucle (la plus interne) finboucle = False # drapeau pour condition de fin de la boucle globale # traitement des boucles R = [] while True: for x in range(indmax, -1, -1): compteurs[x] += boucles[x][2] if compteurs[x]>=boucles[x][1]: if x==0: finboucle = True break compteurs[x] = boucles[x][0] else: break if finboucle: break # enregistrement des résultats de chaque boucle du while R.append([]) for i in xrange(0, n): R[-1].append(L[i][compteurs[i]]) return R
Utilisation:
Code:

1 2 3 L = [['a','b'], ['c','d','e','f'], ['g','h','i']] R = combmultiboucles(L) print R
Ce qui donne avec l'exemple la liste des 24 sous-listes représentant les combinaisons cherchées: :

Code:

[['a', 'c', 'g'], ['a', 'c', 'h'], ['a', 'c', 'i'], ['a', 'd', 'g'], ['a', 'd', 'h'], ['a', 'd', 'i'], ['a', 'e', 'g'], ['a', 'e', 'h'], ['a', 'e', 'i'], ['a', 'f', 'g'], ['a', 'f', 'h'], ['a', 'f', 'i'], ['b', 'c', 'g'], ['b', 'c', 'h'], ['b', 'c', 'i'], ['b', 'd', 'g'], ['b', 'd', 'h'], ['b', 'd', 'i'], ['b', 'e', 'g'], ['b', 'e', 'h'], ['b', 'e', 'i'], ['b', 'f', 'g'], ['b', 'f', 'h'], ['b', 'f', 'i']]

Bien entendu, la fonction peut "avaler" n'importe quelle liste:
Code:

1 2 3 L = [['a','b'], ['c','d','e','f'], ['g','h','i'], ['j','k','l','m','n','o','p']] R = combmultiboucles(L) print R
Ce qui donne une liste comportant 168 sous-listes représentant les combinaisons cherchées:

Code:

[['a', 'c', 'g', 'j'], ['a', 'c', 'g', 'k'], ['a', 'c', 'g', 'l'], ['a', 'c', 'g', 'm'], ['a', 'c', 'g', 'n'], ['a', 'c', 'g', 'o'], ['a', 'c', 'g', 'p'], ['a', 'c', 'h', 'j'], ['a', 'c', 'h', 'k'], ['a', 'c', 'h', 'l'], ['a', 'c', 'h', 'm'], ['a', 'c', 'h', 'n'], ['a', 'c', 'h', 'o'], ['a', 'c', 'h', 'p'], ['a', 'c', 'i', 'j'], ['a', 'c', 'i', 'k'], ['a', 'c', 'i', 'l'], ['a', 'c', 'i', 'm'], ['a', 'c', 'i', 'n'], ['a', 'c', 'i', 'o'], ['a', 'c', 'i', 'p'], ['a', 'd', 'g', 'j'], ['a', 'd', 'g', 'k'], ['a', 'd', 'g', 'l'], ['a', 'd', 'g', 'm'], ['a', 'd', 'g', 'n'], ['a', 'd', 'g', 'o'], ['a', 'd', 'g', 'p'], ['a', 'd', 'h', 'j'], ['a', 'd', 'h', 'k'], ['a', 'd', 'h', 'l'], ['a', 'd', 'h', 'm'], ['a', 'd', 'h', 'n'], ['a', 'd', 'h', 'o'], ['a', 'd', 'h', 'p'], ['a', 'd', 'i', 'j'], ['a', 'd', 'i', 'k'], ['a', 'd', 'i', 'l'], ['a', 'd', 'i', 'm'], ['a', 'd', 'i', 'n'], ['a', 'd', 'i', 'o'], ['a', 'd', 'i', 'p'], ['a', 'e', 'g', 'j'], ['a', 'e', 'g', 'k'], ['a', 'e', 'g', 'l'], ['a', 'e', 'g', 'm'], ['a', 'e', 'g', 'n'], ['a', 'e', 'g', 'o'], ['a', 'e', 'g', 'p'], ['a', 'e', 'h', 'j'], ['a', 'e', 'h', 'k'], ['a', 'e', 'h', 'l'], ['a', 'e', 'h', 'm'], ['a', 'e', 'h', 'n'], ['a', 'e', 'h', 'o'], ['a', 'e', 'h', 'p'], ['a', 'e', 'i', 'j'], ['a', 'e', 'i', 'k'], ['a', 'e', 'i', 'l'], ['a', 'e', 'i', 'm'], ['a', 'e', 'i', 'n'], ['a', 'e', 'i', 'o'], ['a', 'e', 'i', 'p'], ['a', 'f', 'g', 'j'], ['a', 'f', 'g', 'k'], ['a', 'f', 'g', 'l'], ['a', 'f', 'g', 'm'], ['a', 'f', 'g', 'n'], ['a', 'f', 'g', 'o'], ['a', 'f', 'g', 'p'], ['a', 'f', 'h', 'j'], ['a', 'f', 'h', 'k'], ['a', 'f', 'h', 'l'], ['a', 'f', 'h', 'm'], ['a', 'f', 'h', 'n'], ['a', 'f', 'h', 'o'], ['a', 'f', 'h', 'p'], ['a', 'f', 'i', 'j'], ['a', 'f', 'i', 'k'], ['a', 'f', 'i', 'l'], ['a', 'f', 'i', 'm'], ['a', 'f', 'i', 'n'], ['a', 'f', 'i', 'o'], ['a', 'f', 'i', 'p'], ['b', 'c', 'g', 'j'], ['b', 'c', 'g', 'k'], ['b', 'c', 'g', 'l'], ['b', 'c', 'g', 'm'], ['b', 'c', 'g', 'n'], ['b', 'c', 'g', 'o'], ['b', 'c', 'g', 'p'], ['b', 'c', 'h', 'j'], ['b', 'c', 'h', 'k'], ['b', 'c', 'h', 'l'], ['b', 'c', 'h', 'm'], ['b', 'c', 'h', 'n'], ['b', 'c', 'h', 'o'], ['b', 'c', 'h', 'p'], ['b', 'c', 'i', 'j'], ['b', 'c', 'i', 'k'], ['b', 'c', 'i', 'l'], ['b', 'c', 'i', 'm'], ['b', 'c', 'i', 'n'], ['b', 'c', 'i', 'o'], ['b', 'c', 'i', 'p'], ['b', 'd', 'g', 'j'], ['b', 'd', 'g', 'k'], ['b', 'd', 'g', 'l'], ['b', 'd', 'g', 'm'], ['b', 'd', 'g', 'n'], ['b', 'd', 'g', 'o'], ['b', 'd', 'g', 'p'], ['b', 'd', 'h', 'j'], ['b', 'd', 'h', 'k'], ['b', 'd', 'h', 'l'], ['b', 'd', 'h', 'm'], ['b', 'd', 'h', 'n'], ['b', 'd', 'h', 'o'], ['b', 'd', 'h', 'p'], ['b', 'd', 'i', 'j'], ['b', 'd', 'i', 'k'], ['b', 'd', 'i', 'l'], ['b', 'd', 'i', 'm'], ['b', 'd', 'i', 'n'], ['b', 'd', 'i', 'o'], ['b', 'd', 'i', 'p'], ['b', 'e', 'g', 'j'], ['b', 'e', 'g', 'k'], ['b', 'e', 'g', 'l'], ['b', 'e', 'g', 'm'], ['b', 'e', 'g', 'n'], ['b', 'e', 'g', 'o'], ['b', 'e', 'g', 'p'], ['b', 'e', 'h', 'j'], ['b', 'e', 'h', 'k'], ['b', 'e', 'h', 'l'], ['b', 'e', 'h', 'm'], ['b', 'e', 'h', 'n'], ['b', 'e', 'h', 'o'], ['b', 'e', 'h', 'p'], ['b', 'e', 'i', 'j'], ['b', 'e', 'i', 'k'], ['b', 'e', 'i', 'l'], ['b', 'e', 'i', 'm'], ['b', 'e', 'i', 'n'], ['b', 'e', 'i', 'o'], ['b', 'e', 'i', 'p'], ['b', 'f', 'g', 'j'], ['b', 'f', 'g', 'k'], ['b', 'f', 'g', 'l'], ['b', 'f', 'g', 'm'], ['b', 'f', 'g', 'n'], ['b', 'f', 'g', 'o'], ['b', 'f', 'g', 'p'], ['b', 'f', 'h', 'j'], ['b', 'f', 'h', 'k'], ['b', 'f', 'h', 'l'], ['b', 'f', 'h', 'm'], ['b', 'f', 'h', 'n'], ['b', 'f', 'h', 'o'], ['b', 'f', 'h', 'p'], ['b', 'f', 'i', 'j'], ['b', 'f', 'i', 'k'], ['b', 'f', 'i', 'l'], ['b', 'f', 'i', 'm'], ['b', 'f', 'i', 'n'], ['b', 'f', 'i', 'o'], ['b', 'f', 'i', 'p']]

Chouette merci!!! Parfait!!!! :)

Bonjour,
je ne connais pas la taille de tes listes mais il faut prendre garde à ce que le nombre de permutation grandit vite. Voir par exemple la formule de Stirling.

Salut,

Et pourquoi ne pas utiliser la fonction product du module itertools?

Code:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
>>> from itertools import product
>>> L = [['a','b'] , ['c','d','e','f'] , ['g','h','i']]
>>> for e in product(*L):
...     print (e)
...
('a', 'c', 'g')
('a', 'c', 'h')
('a', 'c', 'i')
('a', 'd', 'g')
('a', 'd', 'h')
('a', 'd', 'i')
('a', 'e', 'g')
('a', 'e', 'h')
('a', 'e', 'i')
('a', 'f', 'g')
('a', 'f', 'h')
('a', 'f', 'i')
('b', 'c', 'g')
('b', 'c', 'h')
('b', 'c', 'i')
('b', 'd', 'g')
('b', 'd', 'h')
('b', 'd', 'i')
('b', 'e', 'g')
('b', 'e', 'h')
('b', 'e', 'i')
('b', 'f', 'g')
('b', 'f', 'h')
('b', 'f', 'i')
>>>

- W

Citation:

Envoyé par rambc

je ne connais pas la taille de tes listes mais il faut prendre garde à ce que le nombre de permutation grandit vite. Voir par exemple la formule de Stirling.

Bonne remarque!
Mais s'agit-il de "permutations" ou de "produits cartésien" ?

- W

Citation:

Envoyé par wiztricks

Et pourquoi ne pas utiliser la fonction product du module itertools?

Bien vu! J'avais développé ce code dans le cas général de boucles imbriquées avec des critères de boucles quelconques (début, fin, pas), mais là, c'est plus simple (début=0 et pas=1), et "product" d'itertools marche très bien:
Code:

1 2 3 4 5 6 7 from itertools import product def combmultiboucles(L): R = [] for e in product(*L): R.append(list(e)) return R
Ce qui donne, bien entendu, le même résultat (=produit cartésien).

Le nombre de sous-listes obtenues est facile à calculer: c'est la multiplication des longueurs des sous-listes de départ: 2*4*3=24.