[combinatoire] combinaisons de toutes longueur

Version imprimable

20/02/2003, 17h32
Toorop

[RESOLU][combinatoire] combinaisons de toutes longueur

salut à tous,

quelqu'un aurait-il une idée pour un algorithme permettant de trouver toutes les combinaisons simples (sans ordre, sans répétition) de N éléments pris par groupes de 1 à N.

Un petit exemple : soient 3 éléments A,B,C

l'algorithme devrait retourner :

A
B
C
AB
AC
BC
ABC

Mon but n'est donc pas de connaître le nombre de combinaisons, mais bien d'obtenir toutes ces combinaisons.
20/02/2003, 17h57
delphi-fan

1- As-tu lu l'annonce faite en début de cette section Algo concernant les anagrammes et autres applications de la récursivité ?

2- Le principe est d'explorer en profondeur les combinaisons en utilisant la récursivité comme solution élégante.
Si tu as Delphi, j'ai donné le code complet de ce que tu recherches à cet endroit (mais tu pourras l'adapter facilement à d'autres langages à condition de connaître les principes des fonctions récursives) :
http://www.developpez.net/forums/vie...t=combinaisons

A+

Code:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
 
afficherCombinason(chaine : Chaine,liste : liste des elments) 
   Si liste est vide Alors
       afficher chaine
   Sinon
      tete <-- tete de la liste
      afficher chaine ^ tete
      queue <-- queue de la liste
      Si queue n'est pas vide Alors
          afficherCombinaison(chaine,queue)  
          afficherCombinaison(chaine ^ tete,queue)
       Fin-Si
   Fin-Si
Fin-afficherCombinaison

Ce qui donne pour ton exemple :

Code:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
 
afficherCombinaison("",{A,B,C})
1) {A,B,C} nest pas vide
2) tete = A
3) on affiche A
4) queue = {B,C}
5) queue n'est pas vide
6) appel de afficherCombinaison("",{B,C})
    6)1) {B,C} n'est pas vide
    6)2) tete=B
    6)3) on affiche B
    6)4) queue={C}
    6)5) queue n'est pas vide
    6)6) appel de afficherCombinaison("",{C})
           6)6)1) {C} n'est pas vide
           6)6)2) tete = C
           6)6)3) on affiche C
           6)6)4) queue={}
           6)6)5) queue est vide
           6)6)7) FIN
     6)7) appel de afficherCombinaison("B",{C})
           6)6)1) {C} n'est pas vide
           6)6)2) tete = C
           6)6)3) on affiche BC
           6)6)4) queue={}
           6)6)5) queue est vide
           6)6)7) FIN
      6)9) FIN
7) appel de afficherCombinaison("A",{B,C})
.....

Ce qui donne :

Citation:

A
B
C
BC
AB
AC
ABC

JHelp

21/02/2003, 09h26
Toorop

Ok merci pour vos réponses (et désolé si la solution avait déjà été exposée sur le forum), je m'en vais de ce pas marquer ma question [RESOLU]
16/02/2007, 16h08
ealias

implémentation en java

private static void affiche(ArrayList str,ArrayList reste)
{

if (reste.isEmpty())
{
System.out.println(str.toString());
}
else
{
String tete = (String)reste.get(0);
reste.remove(0);
System.out.println(str.toString()+tete);

if (!reste.isEmpty())
{
// chaine, queue
affiche(str,reste);
// chaine & tete,queue
str.add(tete);
affiche(str,reste);

}
}

J'appelle cette fonction avec reste qui [a,b,c] et str qui vaut [""] et voici le résultat :

[]a
[]b
[]c
[b]
[b, a]
[]

Il me manque des résultats !!!

Quelqu'un a une idée sur ce qui coince ?