Discussion :

[sbeu]

Bonjour.
Ca fait bien longtemps que j'ai appris à développer mais j'ai complètement oublié comment on fait de la récursivité. J'ai un problème pour trouver toutes les combinaisons possibles dans un tableau. Je m'explique.

J'ai un tableau de x cases sur y.

Code :

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

1
2
3
A1   B1   C1
A2   B2   C2
A3   B3   C3

Pour l'exemple je fais un tableau de 3X3


Je cherche à avoir dans un fichier toutes les combinaisons possibles des valeurs des 3 colonnes. Sans permutations. Donc le résultat doit être:

A1B1C1
A1B1C2
A1B1C3
A1B2C1
A1B2C2
A1B2C3
A1B3C1
A1B3C2
A1B3C3
A2B1C1
A2B1C2
A2B1C3
A2B2C1
A2B2C2
A2B2C3

Etc... Jusqu'à A3B3C3

Je n'arrive pas à trouver par quel bout le prendre!!! Ca ne doit pas être difficile mais je n'arrive plus à réfléchir... Ca doit être l'âge et le manque de pratique...


Merci

[dourouc05]

Un des principes pour construire une fonction récursive, c'est d'effectuer un tout petit bout de travail, puis déléguer à un appel récursif. Ici, tu pourrais avoir un appel récursif sur les deux dernières colonnes, tu traites le cas d'une seule colonne : pour toutes les combinaisons possibles des deux dernières colonnes, tu ajoutes les valeurs nécessaires de la première. Il faut définir un cas de base : si tu as zéro colonnes à traiter, tu n'as qu'une seule possibilité, une liste vide.

[Flodelarab]

Bonjour

Code :

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

Pour chaque case de la colonne, traiter la colonne suivante.

[tbc92]

Ici, si on veut un truc qui traite 26 lettres, et 9 chiffres :

Code :

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

1
2
3
4
5
6
 
alphabet = "ABCDEFGHIJKLMNOPQRSTUV"
Resultat = ""
rang_en_cours = 0
 
traite ( alphabet , resultat , rang_en_cours )

Et la fonction traite sera celle ci :

Code :

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

1
2
3
4
5
6
7
8
9
10
11
12
 
procedure traite ( alph, resu, rg)
 
si rg = 26 alors 
    print ( resu )
    retour
sinon
   pour i = 1 a  9
        res = resu ||  ' ' || milieu( alph,i) || i
        traite ( alph, res, rg+1 )
   fin
fin

Reste à traduire ce pseudo-code dans un vrai langage, à l'adapter, à le tester ... mais c'est une base.
Ici 26 caractères, 9 options à chaque caractère, le nombre de combinaisons va être énorme, et ce ne serait pas raisonnable de l'exécuter tel quel !

Le principe d'une fonction récursive, c'est qu'on a une fonction ffff , avec souvent 2 paramètres (un des paramètres compte les étapes déjà effectuées ou restant à effectuer). Et dans le corps de cette fonction ffff, on fait un appel à ffff !

[sbeu]

Je vais maintenant essayer de finir... Une fois résolu je cocherai "résolu"

Merci

[valentin03]

Sinon, tu peux aller pécher des algos de combinatoire sur le net et les déchiffrer, si tu bute sur de la syntaxe, tu peux revenir demander des explics spécifiques(en nommant le langage (bien qu'on puisse le deviner) (c'est ce que je fais en général quand je cherche un algo particulier).

[sbeu]

Aïe... Je n'y arrive pas... Je vous colle ici où j'en suis. Je crois qu'il ne manque pas grand chose mais le résultat n'est pas bon. C'est en Pascal.

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
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
procedure TForm_campagne.cxButton2Click(Sender: TObject);var
ligneInit:integer;
Chaine:String;
begin
    cxMemo1.Lines.Clear;
 
 
    for ligneInit := 0 to Grid.DataController.RecordCount-1 do
    begin
         chaine:='';
         Traiter(LigneInit,0,Chaine);
 
 
    end;
end;
 
 
procedure TForm_campagne.Traiter(ligne, colonne: integer; Var Chaine:String);
var
valeur:String;
i: Integer;
begin
     if Grid.DataController.GetValue(ligne,colonne)<>Null then
     begin
         Valeur:=Grid.DataController.GetValue(ligne,colonne);
         if valeur<>'' then
         begin
            Chaine:=Chaine+Valeur;
            if colonne+1<Grid.ItemCount-1 then
              Traiter(ligne,colonne+1,chaine)
            else
            begin
                if (Valeur<>'') and (chaine<>'') then
                begin
                  cxmemo1.Lines.Add(chaine);
                  chaine:='';
                end;
                //if ligne+1<Grid.datacontroller.RecordCount-1 then
                //    Traiter(ligne+1,colonne,chaine);
            end;
         end;
 
 
     end
     else
     begin
       if Chaine<>'' then
       begin
          cxmemo1.Lines.Add(chaine);
          chaine:='';
       end;
 
 
     end;
 
 
end;

[tbc92]

En ligne 8 de ton code, tu as une boucle for. for ligneInit := 0 to Grid.DataController.RecordCount-1 doPourquoi pas. Je pense que ce n'est pas indispensable, mais dans certains cas, ça simplifie bien les choses.

Mais, il faut également une boucle for dans la procédure Traiter(). Là, avec la version actuelle, si tu pars d'un élément de la ligne 10 colonne 1, tu vas l'associer avec ligne 10 colonne 2, ligne 10, colonne 3... Il n'y a aucune instruction qui modifie la variable ligne.

Je propose ça :

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
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
procedure TForm_campagne.cxButton2Click(Sender: TObject);var
ligneInit:integer;
Chaine:String;
begin
    cxMemo1.Lines.Clear;
 
         chaine:='';
         Traiter(0,Chaine);
 
end;
 
procedure TForm_campagne.Traiter(  colonne: integer; Var Chaine:String);
var
ligne:integer;
valeur:String;
i: Integer;
begin
   for ligne := 0 to Grid.DataController.RecordCount-1 do
   begin
     if Grid.DataController.GetValue(ligne,colonne)<>Null then
     begin
         Valeur:=Grid.DataController.GetValue(ligne,colonne);
         if valeur<>'' then
         begin
            Chaine:=Chaine+Valeur;
            if colonne+1<Grid.ItemCount-1 then
              Traiter(ligne,colonne+1,chaine)
            else
            begin
                if (Valeur<>'') and (chaine<>'') then
                begin
                  cxmemo1.Lines.Add(chaine);
                  chaine:='';
                end;
                //if ligne+1<Grid.datacontroller.RecordCount-1 then
                //    Traiter(ligne+1,colonne,chaine);
            end;
         end;
 
     end
     else
     begin
       if Chaine<>'' then
       begin
          cxmemo1.Lines.Add(chaine);
          chaine:='';
       end;
 
     end;
  end ;
 
end;

Je ne suis pas 100% convaincu. Si ça marche, tant mieux, mais si ça ne marche pas, il faut probablement ENLEVER des trucs.

[sbeu]

Merci de ton code. Le résultat donne ça, avec cet algo. J'ai l'impression que la récursivité s'applique mal... Il faudrait "revenir" en colonne 0 mais je ne sais pas comment.

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
18
19
20
21
22
23
24
25
26
a1B1C1C2
C3
B2C1
C2
C3
B3C1
C2
C3
a2B1C1
C2
C3
B2C1
C2
C3
B3C1
C2
C3
a3B1C1
C2
C3
B2C1
C2
C3
B3C1
C2
C3

[sbeu]

Je pense qu'il ne faut pas de boucle dans la fonction récursive. En effet, on doit faire une boucle seulement sur les lignes de la première colonne. non?
De plus je me demande si il ne faut pas DEUX fonctions pour que ça marche...

[Flodelarab]

Vos codes m'ont l'air bien compliqués.

Voici un exemple simple de script python en récursion :

Code Python :

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

1
2
3
4
5
6
7
8
9
10
11
#!/usr/bin/python
 
def combi(col,maxcol,maxrow,historique):
    if  (col>maxcol) :
        print historique
    else :
        for row in range(1,maxrow+1):
            combi(col+1,maxcol,maxrow,historique+"("+str(col)+","+str(row)+")")
 
combi(1,4,2,"");
combi(1,0,1,"");

Et les 2 résultats (un tableau 4x2 et un tableau 0x1) :

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
(1,1)(2,1)(3,1)(4,1)
(1,1)(2,1)(3,1)(4,2)
(1,1)(2,1)(3,2)(4,1)
(1,1)(2,1)(3,2)(4,2)
(1,1)(2,2)(3,1)(4,1)
(1,1)(2,2)(3,1)(4,2)
(1,1)(2,2)(3,2)(4,1)
(1,1)(2,2)(3,2)(4,2)
(1,2)(2,1)(3,1)(4,1)
(1,2)(2,1)(3,1)(4,2)
(1,2)(2,1)(3,2)(4,1)
(1,2)(2,1)(3,2)(4,2)
(1,2)(2,2)(3,1)(4,1)
(1,2)(2,2)(3,1)(4,2)
(1,2)(2,2)(3,2)(4,1)
(1,2)(2,2)(3,2)(4,2)

[sbeu]

Grand merci et bravo. Très élégant. Je n'aurais pas pu trouver... Trop conceptuel pour moi. Tu me sauves la vie