Discussion :

[syrius31]

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.

[tyrtamos]

Bonjour,

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

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

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 :

Sélectionner tout - Visualiser dans une fenêtre à part

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 :

Sélectionner tout - Visualiser dans une fenêtre à part

[['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 :

Sélectionner tout - Visualiser dans une fenêtre à part

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 :

Sélectionner tout - Visualiser dans une fenêtre à part

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

[syrius31]

Chouette merci!!! Parfait!!!!

[rambc]

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.

[wiztricks]

Salut,

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

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

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

[wiztricks]

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

[tyrtamos]

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 :

Sélectionner tout - Visualiser dans une fenêtre à part

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.