Discussion :

[Zanga]

Code :

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

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?

[tyrtamos]

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 :

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

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 :

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

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 :

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

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

[Zanga]

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?

[tyrtamos]

Avec tes notations, cela devrait donner quelque chose comme:

Code :

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

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 :

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

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

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

Tyrtamos

[Zanga]

Impressionant, merci beaucoup !

[Matthieu Brucher]

Autre solution :

Code :

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

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