Problème : liste des parties de n!

Code:

---

1 2 3 4 5 6 7 8 9 10 11 12 13

def listePartie(n): if n==0: return [[]] else: rev=listePartie(n-1)[:] rev.reverse() copy=[] p=[] for element in rev: p=element+[n] copy.append(p) return (partie(n-1)+copy)

---

Je viens de réaliser la fonction suivante qui renvoie pour tout n entier, l'ensemble de ses parties de telle façon qu'elles soient uniques...
Si vous tester pour 3 , vous obtiendrez quelque chose du genre :
[], [1], [1, 2], [2], [2, 3], [1, 2, 3], [1, 3], [3]

Je dois maintenant faire une fonction qui prend en paramètre un n, et un k entier, qui cette fois ne renvoie que les parties de n qui sont de tailles égales à k... j'ai éssayer de reprendre ma fonction précedente en ajoutant un test mais je n'y parviens pas. Auriez vous une solution?

Bonjour,

Pour résoudre ce genre de problème, il y a une solution que j'aime bien, qui n'est pas trop complexe à comprendre et qui n'est pas récursive: il s'agit de s'appuyer sur le comptage en binaire.

Avec une liste composée de lg éléments, on va compter de 0 à 2**lg-1, et pour chaque valeur du compteur, on va placer un élément de la liste à chaque 1 qu'on aura dans la représentation binaire du compteur.

Exemple:

liste = ['a', 'b', 'c'] donc lg=len(liste)=3 éléments

On va donc compter de 0 à 2**3-1=7

Code:

---

1 2 3 4 5 6 7 8

0 000 [] 1 001 ['c'] 2 010 ['b'] 3 011 ['b', 'c'] 4 100 ['a'] 5 101 ['a', 'c'] 6 110 ['a', 'b'] 7 111 ['a', 'b', 'c']

---

On voit bien dans cet exemple: pour une valeur du compteur, s'il y a un '1' en 2ème position, alors on ajoute un 'b' dans la liste correspondant à ce compteur.

Et pour n'avoir que les solutions à 2 éléments, par exemple, il suffit de n'ajouter la solution d'un compteur que si cette solution a exactement 2 éléments.

Voilà un code qui fait tout cela (inspiré de: http://guillaume.apinc.org/2005/juil...1-math--python):

Code:

---

1 2 3 4 5 6 7 8

def listecombin(liste, n=None): r = [] for i in range(0, 2 ** len(liste)): s = [item for j,item in enumerate(liste) if (i>>j)&1] if n==None or len(s)==n: r.append(s) return r

---

Exemple d'utilisation:

Code:

---

1 2 3 4 5 6 7 8

liste = (1,2,3)   print listecombin(liste) [[], [1], [2], [1, 2], [3], [1, 3], [2, 3], [1, 2, 3]]   print listecombin(liste,2) [[1, 2], [1, 3], [2, 3]]

---

NB: avec Python 2.6, tu peux afficher la représentation binaire d'un nombre avec la fonction bin()

Tyrtamos

Fiou merci beaucoup!

Mais n'est il pas possible de modifier ma fonction pour conserver les parametres (deux entiers n et k) et en retournant toujours la liste voulue?

Avec tes notations, cela devrait donner quelque chose comme:

Code:

---

1 2 3 4 5 6 7 8 9

def listecombin(n, k=None): liste = range(1,n+1) r = [] for i in range(0, 2 ** len(liste)): s = [item for j,item in enumerate(liste) if (i>>j)&1] if k==None or len(s)==k: r.append(s) return r

---

Et les appels:

Code:

---

1 2 3

print listecombin(3) print listecombin(3,2)

---

Vérifie! je n'ai pas essayé.

Tyrtamos

Impressionant, merci beaucoup !

Autre solution :

Code:

---

1 2	def nouvell_fun(n, k): return [l for l in listePartie(n) if len(l) == k]

---