Trouver toutes les combinaisons, uniques et de tailles différentes, des éléments d’une liste avec Python
par nojhan le 22 mars 2007
Ce petit bout de code sert à trouver différentes combinaisons d’éléments d’une liste. Ces combinaisons sont uniques (ab==ba) et on cherche dans les différentes tailles possibles (a, ab, abc, etc.). Le tout dans le langage de script Python.
Exemple
Mieux vaut un exemple qu’un long discours. Soit la liste :
['a', 'b', 'c', 'd']
On cherche les combinaisons suivantes :
a
b
c
d
ab
ac
ad
bc
bd
cd
abc
abd
acd
bcd
abcd
Combinaisons uniques
Une première fonction consiste à chercher la liste des combinaisons uniques d’une taille n donnée, au sein d’une liste items.
def combinationsUniques(items, n):
if n==0:
yield []
else:
for i in xrange( len(items) - n+1 ):
for j in combinationsUniques( items[i+1:], n-1 ):
yield [items[i]] + j
La fonction utilise l’instruction yield pour gérer proprement la récursivité. L’utilisation de xrange est recommandée pour les boucles.
Toutes les combinaisons uniques
De manière très simple, la seconde fonction parcours les différentes tailles possibles.
def combinationsUniquesSizes(items):
res = []
for n in xrange(1,len(items)+1):
res += combinationsUniques(items,n)
return res
Licence : WTFPL
Téléchargements
Le module
: Les fonctions sont dans ce module, avec une démo pour l’appel direct.
(Zip - 357 octets)
Commentaires
Bonjour,
Cela fait plusieurs jours que je cherche une fonction comme celle là mais je ne connais pas Python :-( Te serait il possible de la refaire en PHP stp ?
Merci beaucoup :-)
Par nojhan, le 6 décembre 2011 : Trouver toutes les combinaisons, uniques et de tailles différentes, des éléments d’une liste avec Python
Non