Discussion :

[simon55]

Bonjour à tous,

Etant donné une liste L=[0..n-1], j'aimerai écrire un programme qui me renvoie la liste de toutes les parties à k éléments de L.
Je me doute qu'il va falloir travailler récursivement, j'ai tenté d'appliquer l'idée de la preuve de la formule de Pascal mais je n'aboutis pas, pourriez vous m'aider s'il-vous-plait?

Merci

[mokochan]

Bonjour,

le mieux ce serait de nous montrer ce que tu as essayé pour qu'on reparte de là!
Mais effectivement l'idée d'utiliser la récursivité s'applique bien ici, puisque on a (n k) + (n k+1) = (n+1 k+1).
Détaille donc nous plus ton "je n'aboutis pas" ;-)

[tyrtamos]

Bonjour,

Est-ce que ça répond à ta question, ou tu aimerais le programmer toi-même?

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
from itertools import combinations
 
x = [1,2,3,4,5]
 
for y in combinations(x, 3):
    print(y)
 
(1, 2, 3)
(1, 2, 4)
(1, 2, 5)
(1, 3, 4)
(1, 3, 5)
(1, 4, 5)
(2, 3, 4)
(2, 3, 5)
(2, 4, 5)
(3, 4, 5)

[Clodion]

Etant donné une liste L=[0..n-1], j'aimerai écrire un programme qui me renvoie la liste de toutes les parties à k éléments de L.

Bonsoir,
Avez-vous pensé à regarder du coté du module itertools (de la bibliothèque standard)?

Clodion

[simon55]

Merci pour vos réponses,

Clodion & Tyrtamos : Effectivement, j'aimerai le programmer moi même.

Mokochan : Voici ce que j'ai essayé, le problème est que je n'arrive pas à ressortir une liste convenable :

Code :

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

1
2
3
4
5
6
 
def partition(L):
   if len(L)==0:
      return([])
   else:
      return([[L[0]]+partition(L[1:]),partition(L[1:])])

[Sve@r]

Mokochan : Voici ce que j'ai essayé, le problème est que je n'arrive pas à ressortir une liste convenable :

Code :

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

1
2
3
4
5
6
 
def partition(L):
   if len(L)==0:
      return([])
   else:
      return([[L[0]]+partition(L[1:]),partition(L[1:])])

Bonjour

T'as regardé l'exemple de tyrtamos ? T'en tires aucune conclusion ???
Déjà il y a forcément une notion de "n" (nombres d'items demandés) à mettre en place. Ca me semble un peu évident. Certains demanderont une combinaison de 3 parmi 5, d'autres de 2 parmi 5 et d'autres de 4. Donc déjà là t'es complètement bancal.

Ensuite ben pour n items tu pars des n premiers de ta liste puis tu prends le dernier demandé (3 dans l'exemple de tyrtamos) et tu itères jusqu'à la fin de la liste (4 et 5). Puis tu pars de cette nouvelle liste (1, 2, 4) et tu itères l'avant dernier (2) qui passe à 3. Puis 1, 4, 5 puis etc etc etc. Donc forcément il y aura une notion de boucle à mettre en place...

[Captain'Flam]

Je sais qu'on n'est pas là pour faire les devoirs des copains, mais un code bien algorithmique comme ça, je n'ai pas pu résister :

Code :

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

1
2
3
4
5
6
7
8
9
10
11
12
def part ( l,n ):
    if n == 0 :
        yield []
    elif n <= len( l ) :
        for p in part( l[1:],n-1 ): yield l[0:1] + p
        for p in part( l[1:],n   ): yield          p
 
 
for n in xrange( 6 ):
    print '-----',n
    for p in part( [1,2,3,4],n ):
        print p

Ça me rappelle le bon vieux temps du lisp...

[fred1599]

Oui c'est ce qu'on voit dans tous les pseudos code, une simple recherche de 2 minutes auraient suffit pour trouver ce type de code...