Générer les combinaisons

Version imprimable

23/06/2015, 16h07
simon55

Générer les combinaisons

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 :D
23/06/2015, 16h30
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" ;-)

Bonjour,

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

Code:

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)

23/06/2015, 16h34
Clodion

Citation:

Envoyé par simon55

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
23/06/2015, 16h38
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:

1 2 3 4 5 6 def partition(L): if len(L)==0: return([]) else: return([[L[0]]+partition(L[1:]),partition(L[1:])])
23/06/2015, 22h37
Sve@r
Citation:
Envoyé par simon55

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

Code:

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...

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:

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...

24/06/2015, 17h52
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...