Aide sur un algorithme récursif

**christianf** · 14/08/2010, 16h43

Bonjour.
J'ai déjà posté sur ce sujet, mais je pense que je m'y suis mal pris, vu les orientations dans les réponses...
J'ai un problème d'ordre algorithmique.
J'arrive pas à écrire un algorithme qui me retourne toutes mes valeurs.
Je vais d'abord expliquer ce que j'ai envie de faire, de façon globale, puis sur un exemple je vais détailler ce que j'ai envie d'obtenir, et enfin proposer l'algorithme que j'ai implémenté, qui ne marche pas.
Donc, je dispose d'éléments, qui peuvent par exemple être des lettres de l'alphabet a, b, c ...sont des éléments.
Je peux donc avoir des listes d'éléments l1 = abc l2= cde l3= fghij ....
mon problème:
Je voudrais partir d'une liste initiale qui contient toutes ces listes (liste_initiale = (l1, l2, l3...), et obtenir une liste finale avec d'autres listes liste_finale = (l10, l11, l12,....).
Les listes de la liste finale sont construites de façon incrémentale, en respectant l'algorithme que je vais détailler ci dessous pour 3 listes par exemple. De façon générale, quand le constructeur prend un élément d'une liste, il se rappelle sur toutes les listes, mais en ne considérant plus l'élément qu'il vient de prendre...

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
liste_initiale = (l1, l2, l3) avec l1 = ab  l2 = def  et l3 = g
Mon constructeur de la liste finale fonctionne ainsi:
constructeur(ab, def, g) 

aconstructeur(b, def, g), dconstructeur(ab, ef, g), gconstructeur(ab, def)

abconstructeur(def, g), adconstructeur(b, ef, g), agconstructeur(b, def), daconstructeur(b, ef, g), deconstructeur(ab, f, g), dgconstructeur(b, ef), gaconstructeur(b, def), gdconstructeur(ab, ef)

abdconstructeur(ef, g), abgconstructeur(def), adbconstructeur(ef, g), adeconstructeur(b, f, g), adgconstructeur(b, ef), agbconstructeur(def), agdconstructeur(b, ef), dabconstructeur(ef, g), daeconstructeur(b,f,g), dagconstructeur(b, ef), deaconstructeur(b, f, g), defconstructeur(ab, g), degconstructeur(ab, f), dgbconstructeur(ef), dgeconstructeur(b, f), gabconstructeur(def), gadconstructeur(b, ef), gdaconstructeur(b, ef), gdeconstructeur(ab, f)

abdeconstructeur(f, g), abdgconstructeur(ef), abgdconstructeur(ef), adbeconstructeur(f, g), adbgconstructeur(ef), adebconstructeur(f, g), adefconstructeur(b, g), adegconstructeur(b, f), adgbconstructeur(ef), adgeconstructeur(b, f), agbdconstructeur(ef), agdbconstructeur(ef), agdeconstructeur(b, f), dabeconstructeur(f, g), dabgconstructeur(ef), daebconstructeur(f, g), daefconstructeur(b, g), daegconstructeur(b, f), dagbconstructeur(ef), dageconstructeur(b, f), deabconstructeur(f, g), deafconstructeur(b, g), deagconstructeur(b, f), defaconstructeur(b, g), defgconstructeur(ab), degaconstructeur(b, f), degfconstructeur(ab), dgbeconstructeur(f), dgebconstructeur(f), dgefconstructeur(b), gabdconstructeur(ef), gadbconstructeur(ef), gadeconstructeur(b, f), gdabconstructeur(ef), gdaeconstructeur(b, f), gdeaconstructeur(b, f), gdefconstructeur(ab)

abdefconstructeur(g), abdegconstructeur(f), abdgeconstructeur(f), abgdeconstructeur(f), adbefconstructeur(g), adbegconstructeur(f), adbgeconstructeur(f), adebfconstructeur(g), adebgconstructeur(f), adefbconstructeur(g), adefgconstructeur(b), ...............................
....................................................

abdefg, abdegf, abdgef, abgdef, adbefg, adbegf, adbgef, adebfg, adebgf, adefbg, adefgb..............................................................................
...................................................................................

Maintenant que j'ai détaillé l'algorithme, voici ce que je propose pour son implémentation.

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
 
liste_liste_element est ma structure qui contient les listes d'éléments;
liste_element est ma structre qui contient les éléments;
 
Mon constructeur renvoie donc une liste_liste_element (la liste finale). Il prend en entrée une liste_liste_element (la liste initiale).
 
//j'initialise liste_finale à vide;
//pour chaque liste linit de la liste initiale, j'initialise une liste d'élément lelt, //j'ajoute le premier élément de linit à lelt, j'appelle le constructeur sur la //nouvelle liste initiale (qui est l'ancienne liste, moins le premier élément de la //liste traitée) et j'ajoute lelt à liste_finale
 
liste_liste_element constructeur(liste_liste_element liste_initiale)
{
    liste_liste_element liste_initiale = 
    enlever_listes_vide_de_la_liste_initiale(liste_initiale);
 
    liste_liste_element liste_finale = vide;
    pour linit dans liste_initiale faire
        liste_element lelt = vide;
        lelt = ajoute_element(lelt, premier_element(linit);
        liste_finale = ajouter_liste(liste_finale, lelt);
        liste_finale = constructeur(nouvelle_liste(liste_initiale));
    finpour;
 
    retourne liste_finale;
}

maintenant j'explique les fonctions utilisées

Code :

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

1
2
 
enlever_listes_vide_de_la_liste_initiale est une fonction qui prend en entrée une liste_liste_element et renvoie une liste_liste_element sans les liste_element vides.

Code :

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

1
2
 
ajoute_element ajoute un élément à une liste d'éléments, et retourne la nouvelle liste d'élements

Code :

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

1
2
 
ajouter_liste ajoute une liste d'éléments à une liste de liste d'éléments et retourne la nouvelle liste de liste d'éléments.

Cet algorithme ne marche pas.
Je vois bien par exemple que je n'ajoute que le premier élément, raison pour laquelle j'obtiens à la fin une liste finale dont les listes ont un seul élément...
Je ne vois vraiment pas comment écrire cet algorithme pour obtenir toutes mes listes...
D'avance merci..

**diogene** · 16/08/2010, 19h04

Je ne vois pas de raison pour utiliser un algorithme récursif dans ce problème.

Note: plutôt que parler de "liste de listes", ce qui donne un ambiguité lorsqu'on utilise le terme de "liste" ou oblige à alourdir le discours, j'ai préféré utiliser l'expression "liste de suites"

Les suites de la liste finale ont comme caractéristiques :
- Elles comportent tous les éléments des suites de départ
- Les éléments d'une même suite de départ apparaissent dans l'ordre où ils figurent dans la liste de départ
Ceci suggère que l'on peut concevoir chaque suite de départ comme une pile où on va piocher des éléments pour constituer chaque suite de la liste finale. Par conséquent, une suite de la liste finale est caractérisée par l'ordre dans lequel on va piocher dans les suites de départ. Appelons cette caractéristique sa signature. La signature peut être représentée par la suite des numéros des suites dans lesquelles on va piocher. Dans ce cas, la signature doit comporter autant de valeurs i qu'il y a d'éléments dans la ième suite de départ.

Par exemple :

Liste de départ (ab,c,g)
La signature doit avoir 2 fois 1 , 1 fois 2 et 1 fois 3
Exemple de signature (2131) ; la suite associée est (cagb)

La liste finale comporte toute les suites dont on peut construire une signature. L'ordre dans lequel elles sont placées correspond à des signatures croissantes.

Exemple :

dans l'exemple précédent, la première suite de la liste finale a pour signature (1123) soit (abcg), la suivante (1132) soit (abgc) et la dernière (3211) soit (gcab).

Il suffit donc d'engendrer les signatures possibles dans l'ordre croissant pour obtenir les suites de la liste finale dans le bon ordre.
La recherche des signatures est indépendante des éléments ou de la manière dont les listes sont représentées (tableaux ou listes chainées). Elle ne dépend que du nombre de suites et du nombre d'éléments de chaque suite dans la liste de départ.

On peut envisager de représenter ce calcul par une structure TSignature qui contient
- nbsuite : un entier contenant le nombre de suites dans la liste initiale
- nbtotelem : un entier contenant le nombre total d'éléments dans les suites de la liste initiale
- suites : un tableau de nbsuite entiers contenant le nombre d'éléments non utilisé par la signature pour chaque suite de départ
- signature :un tableau de nbtotelem entiers contenant la signature
- pile : éventuellement. un tableau de nbsuite éléments permettant de gèrer chaque suite comme une pile (par exemple un tableau d'indices si les suites sont organisées en tableaux ou un tableau de pointeur si elles le sont en listes chainées). Il peut être commode d'inclure cette possibilité bien qu'elle n'intervienne pas dans le calcul des signatures mais est utile ensuite pour déduire des signatures les suites finales.

Pour créer un TSignature, il faut connaitre le nombre de suites et le nombre d'éléments de chaque suite. Une fois créé, il doit être initialisé. En particulier
- suites[] doit contenir le nombre d'éléments de chaque suite
- signature[] doit contenir des zéros.

Il reste à calculer les signatures dans le bon ordre :

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
void CompleterSignature(TSignature* p)
// Vide le tableau suites[] des termes disponibles en mettant à jour signature
// Exemple entrée : suites[] = {1,2,1}  signature[] = {1,2,0,0,0,0}
//         sortie : suites[] = {0,0,0}  signature[] = {1,2,1,2,2,3}
{
   int i,k;
   for (k=0,i=0; i<p->nbsuite;i++)
      while(p->suites[i] != 0)
      {
         if(p->signature[k]==0)
         {
            p->signature[k]= i+1;
            p->suites[i]--;
         }
         k++;
      }
}
//---------------------------------------------------------------------------
int Signature(TSignature* p)
// Calcule la signature suivante
// Renvoie 0 si pas de signature suivante
{
   int i,k,a;
   for(i=0; i<p->nbsuite;i++)p->pile[i]=0;
   if(p->signature[0] == 0)  // construction de la première signature
   {
     CompleterSignature(p);
     return 1;
   }
   i=p->nbtotelem-1;          // signature suivante
   while(i>=0)
   {
     a = p->signature[i]-1;   // enlever le dernier terme (!= 0) de signature
     p->signature[i] = 0;
     p->suites[a]++;          // et le déclarer disponible
                              // chercher si un terme plus grand est disponible
     for(k=a+1; k<p->nbsuite;k++)if (p->suites[k]!= 0) break;
     if(k<p->nbsuite)
     {                        // oui
       p->signature[i] = k+1; //    le mettre dans signature
       p->suites[k]--;        //    le rendre indisponible
       CompleterSignature(p);
       return 1;
     }
     else i--;
   }
   return 0;
}

Il reste à écrire le code spécifique de dépilement des éléments à partir des signatures et tester.
Dans l'exemple suivant, j'ai supposé que les suites étaient des tableaux de char et les listes des tableaux de pointeurs sur char.
La fonction Suite() permet d'obtenir la suite correspondant à une signature :

Code :

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

1
2
3
4
5
6
7
8
9
10
11
12
void Suite( TSignature * p, char ** listesuite, char* dest)
{
  int i;
  int li;
  for(i=0; i< p->nbtotelem;i++)
  {
   li = p->signature[i]-1;            // la liste à dépiler
   dest[i] = listesuite[li][p->pile[li]];   // dépilage et stockage dans la liste de destination
   p->pile[li]++;            // mise à jour du pointeur de pile
  }
  dest[i] ='\0'; // terminer la suite
}

Enfin le main() pour tester l'ensemble (les allocations ne sont pas vérifiées pour ce test):

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
int main(void)
{
  char *liste[]= {"ab","cde","f"};
  TSignature *signature;
  int * suite;
  int i;
  int totelem=0;
  int nbsuite = sizeof liste/sizeof *liste;
  char *  result;
  // Création/initialisation de signature dans mon cas
  suite = malloc(nbsuite*sizeof *suite);
  for(i=0;i<nbsuite;i++)
  {
    suite[i] = strlen(liste[i]);
    totelem += suite[i];
  }
  result = malloc(totelem+1);
  i=1;
  signature = CreerSignature(nbsuite,suite);
  // affichage des suites obtenues
  while(Signature(signature)!= 0)   // signature suivante
  {
    printf("%3d    ",i);
    Suite(signature,liste, result); // la suite qui correspond
    printf("%s  \n",result);
    i++;
  }
  DetruireSignature(signature);
  free(suite);
  free(result);
  return 0;
}

On obtient

1 abcdef
2 abdefg
3 abdegf
4 abdgef
5 adbefg
6 adbegf
....
57 fcadeb
58 fcdabe
59 fcdaeb
60 fcdeab

**christianf** · 20/08/2010, 04h35

Merci diogene pour ta réponse encore une fois bien détaillée.
Je m'en suis inspiré pour résoudre mon problème.

Aide sur un algorithme récursif

C

Discussions similaires

Partager

Partager