[Résolu] boucle for récursive

boucle for récursive [Résolu] - C++ - Programmation

Marsh Posté le 17-11-2006 à 12:10:34    

Salut,
 
J'ai besoin de parcourir toutes les combinaisons possibles de M valeurs dans un choix de N (le C(M,N) en combinatoire). Par exemple pour M=3 valeurs dans les entiers de 0 à 4 valeurs (donc N=5) je veux les jeux :

Code :
  1. 012
  2. 013
  3. 014
  4. 023
  5. 024
  6. 034
  7. 123
  8. 124
  9. 134
  10. 234


 
La meilleure méthode que j'ai trouvé pour l'instant est une fonction récursive :

Code :
  1. void recursive(int i, int u)
  2. {
  3. for(int j=i; j<N; ++j)
  4. {
  5.  k[u]=j;
  6.  if(u<M-1) recursive(j+1, u+1);
  7.  else
  8.                 {
  9.                       for(int g=0; g<M; ++g) cout<<k[g];
  10.                       cout<<endl;
  11.                       grosse_fonction();
  12.                 }
  13. }
  14. return;
  15. }

où le u varie sur M et le i sur N. Le premier appel est donc recursive(0,0). Le cout est là de manière à afficher le résultat précédent.
 
Le problème est que la fonction grosse_fonction prend une palanquée d'arguments qui n'ont pas spécialement besoin d'être défini globalement, ce qui fait que je dois fournir tous ces arguments aussi à la fonction récursive... Donc je me demande s'il n'y a pas moyen (mais je ne pense pas...  :( ) de faire dans la fonction qui appelle recursive(0,0) une boucle sur M de boucles for, de manière à ce que tout reste dans cette fonction (plus besoin des fonctions "recursive" et "grosse_fonction" ).
 
Voilà, je veux pas vous faire réfléchir à ma place, mais si quelqu'un a une idée de génie ou a déjà eu affaire à un truc de ce genre, on sait jamais...  :hello:  
 
Merci.

Message cité 1 fois
Message édité par SkippyleGrandGourou le 20-11-2006 à 11:56:01
Reply

Marsh Posté le 17-11-2006 à 12:10:34   

Reply

Marsh Posté le 17-11-2006 à 13:25:19    

C ou C++ ?

Reply

Marsh Posté le 17-11-2006 à 13:48:49    

C++, mais si t'as une idée en C dis toujours...


Message édité par SkippyleGrandGourou le 17-11-2006 à 13:49:31
Reply

Marsh Posté le 17-11-2006 à 14:19:45    

on a déjà fait 30000 sujets le dessus, fait une recherche, nous aussi on en a marre de répondre en boucle aux mêmes questions.

Message cité 1 fois
Reply

Marsh Posté le 17-11-2006 à 14:31:48    

Reply

Marsh Posté le 17-11-2006 à 14:40:49    

Taz a écrit :

on a déjà fait 30000 sujets le dessus, fait une recherche, nous aussi on en a marre de répondre en boucle aux mêmes questions.


+1 : le sujet a été plusieurs fois abordé.
 
Un exemple de topic très proche du tien : [algo] parcourir une matrice de taille (lignes et colonnes) variable


---------------
TriScale innov
Reply

Marsh Posté le 17-11-2006 à 16:43:59    

Je dois avoir des problèmes d'expression, ou alors certains gueulent avant de lire...  :sarcastic:  
 
Le problème n'est pas de faire un algo bidon pour parcourir un arbre ou je ne sais trop quoi, mais d'imbriquer un nombre indéfini de boucles for... Je ne parle pas de permutations mais de combinaisons.
 
Bon, j'ai trouvé ça sur le net :

Code :
  1. bool comb[]={0,0,1,1,1};
  2. int data[]={0,1,2,3,4};
  3. do {
  4.     for(int c=0;c<4;c++) if(comb[c])  cout<<data[c];
  5.     cout<<endl;
  6. } while(next_permutation(comb,comb+5));


C'est astucieux, mais le souci c'est que dans mon cas il s'agit de millions d'appels de la fonction contenant ces lignes, et le tableau comb doit contenir une centaine de 0 pour trois ou quatre 1, ce qui fait beaucoup trop de if(comb[c]) à mon goût...
 
J'ai aussi trouvé ça :

Code :
  1. template <class BidIt>
  3. bool next_combination(BidIt n_begin, BidIt n_end,
  4. BidIt r_begin, BidIt r_end)
  5. {
  6.   bool boolmarked=false;
  7.   BidIt r_marked;
  8.   BidIt n_it1=n_end;
  9.   --n_it1;
  11.   BidIt tmp_r_end=r_end;
  12.   --tmp_r_end;
  13.   BidIt tmp_r_begin=r_begin;
  14.   --tmp_r_begin;
  16.   for(BidIt r_it1=tmp_r_end; r_it1!=tmp_r_begin ; --r_it1,--n_it1)
  17.   {
  18.     if(*r_it1==*n_it1 )
  19.     {
  20.       if(r_it1!=r_begin) //to ensure not at the start of r sequence
  21.       {
  22.         boolmarked=true;
  23.         r_marked=(--r_it1);
  24.         ++r_it1;//add it back again  
  25.         continue;
  26.       }
  27.       else // it means it is at the start the sequence, so return false
  28.         return false;     
  29.     }
  30.     else //if(*r_it1!=*n_it1 )
  31.     {
  32.       //marked code
  33.       if(boolmarked==true)
  34.       {
  35.         //for loop to find which marked is in the first sequence
  36.         BidIt n_marked;//mark in first sequence
  37.         for (BidIt n_it2=n_begin;n_it2!=n_end;++n_it2)
  38.           if(*r_marked==*n_it2) {n_marked=n_it2;break;}
  39.    
  40.         BidIt n_it3=++n_marked;   
  41.         for  (BidIt r_it2=r_marked;r_it2!=r_end;++r_it2,++n_it3)
  42.         {
  43.           *r_it2=*n_it3;
  44.         }
  45.         return true;
  46.       }
  47.       for(BidIt n_it4=n_begin; n_it4!=n_end; ++n_it4)
  48.         if(*r_it1==*n_it4)
  49.         {
  50.           *r_it1=*(++n_it4);
  51.           return true;         
  52.         }
  53.     }
  54.   } 
  55.   return true;//will never reach here     
  56. }


mais je me demande si ça vaut vraiment le coup de passer par une telle fonction, qui me semble un peu longue et donc peut-être moins efficace que l'appel récursif... non ?
 
PS : J'avais pas vu qu'il y avait une section algo, désolé...

Message cité 2 fois
Message édité par SkippyleGrandGourou le 17-11-2006 à 17:27:32
Reply

Marsh Posté le 17-11-2006 à 18:15:28    

SkippyleGrandGourou a écrit :

Je dois avoir des problèmes d'expression, ou alors certains gueulent avant de lire...  :sarcastic:  
 
Le problème n'est pas de faire un algo bidon pour parcourir un arbre ou je ne sais trop quoi, mais d'imbriquer un nombre indéfini de boucles for...

Je ne sais pas si tu as lu le lien que je t'ai donné, mais il y a de grandes similitudes entre le problème posé dans ce topic et le tien. En particulier, tous deux admettent des solutions récursives presque triviales, qu'on cherche à rendre itératives.
Tu pourras aussi remarquer que la solution que j'ai proposée dans le topic mentionné est basée sur la notion d'incrément permettant de passer d'une combinaison à la suivante, ce qui est exactement le rôle joué par la fonction next_combination que tu as trouvé sur le web. Tant que tu raisonnes en termes de "nombre indéfini de boucles for imbriquées", tu ne débouches que sur des solutions récursives ; c'est la notion d'incrément qui te permet de changer de point de vue et de rendre l'algorithme itératif.
 
Tu n'as apparemment pas de problème d'expression, mais je ne suis pas sûr que ce soit moi qui gueule avant de lire :spamafote:

Message cité 1 fois

---------------
TriScale innov
Reply

Marsh Posté le 18-11-2006 à 13:52:16    

SkippyleGrandGourou a écrit :

Salut,
 
J'ai besoin de parcourir toutes les combinaisons possibles de M valeurs dans un choix de N (le C(M,N) en combinatoire). Par exemple pour M=3 valeurs dans les entiers de 0 à 4 valeurs (donc N=5) je veux les jeux :

Code :
  1. 012
  2. 013
  3. 014
  4. 023
  5. 024
  6. 034
  7. 123
  8. 124
  9. 134
  10. 234


 
La meilleure méthode que j'ai trouvé pour l'instant est une fonction récursive :

Code :
  1. void recursive(int i, int u)
  2. {
  3. for(int j=i; j<N; ++j)
  4. {
  5.  k[u]=j;
  6.  if(u<M-1) recursive(j+1, u+1);
  7.  else
  8.                 {
  9.                       for(int g=0; g<M; ++g) cout<<k[g];
  10.                       cout<<endl;
  11.                       grosse_fonction();
  12.                 }
  13. }
  14. return;
  15. }

où le u varie sur M et le i sur N. Le premier appel est donc recursive(0,0). Le cout est là de manière à afficher le résultat précédent.
 
Le problème est que la fonction grosse_fonction prend une palanquée d'arguments qui n'ont pas spécialement besoin d'être défini globalement, ce qui fait que je dois fournir tous ces arguments aussi à la fonction récursive... Donc je me demande s'il n'y a pas moyen (mais je ne pense pas...  :( ) de faire dans la fonction qui appelle recursive(0,0) une boucle sur M de boucles for, de manière à ce que tout reste dans cette fonction (plus besoin des fonctions "recursive" et "grosse_fonction" ).
 
Voilà, je veux pas vous faire réfléchir à ma place, mais si quelqu'un a une idée de génie ou a déjà eu affaire à un truc de ce genre, on sait jamais...  :hello:  
 
Merci.


 
Il faudrait avoir quelques précisions. Il y a peu j'avais besoin d'appliquer une fonction prenant en argument toutes les "combinaisons avec répétitions" de k éléments parmi n ( http://fr.wikipedia.org/wiki/Combi [...] 3%A9tition ). Pas exactement comme toi, mais similaire en ce que je me suis aperçu que j'aurai du mal à écrire une procédure itérative de génération de ces combinaisons. Surtout sans bug... La fonction next_combination() que tu reproduit plus haut me conforte dans mon idée, même si je pense que les combinaisons avec répétitions sont plus simples.
 
Par contre :

  • Ma procédure récursive a une profondeur égale à n, et la complexité du programme que j'écris explose avec n pour des raisons qui n'ont rien à voir avec les combinaisons. Il est de toutes façons hors de question d'utiliser ce programme pour n > 3. Donc, en tenant compte des contraintes d'utilisation du programme, ma procédure récursive n'est pas limitante, ni en temps de calcul ni en risque de se manger un stack overflow. Comme la récursion est "élégante" et compréhensible, je l'ai gardée.
  • J'ai besoin d'itérer un grand nombre de fois sur l'ensemble des combinaisons. Il serait catastrophique pour les temps de calcul que je les recalcule à chaque fois. J'ai donc utilisé ma procédure récursive une seule fois pour me générer toutes les combinaisons. L'équivalent de ta fonction "grosse_fonction()" prend en paramètre une combinaison et je l'appelle en itérant sur toutes les combinaisons :


Code :
  1. for ( comb in Combinaisons )
  2.   grosse_fonction(comb, ...)


 
Bon, tout ce 3615 MyLife pour te dire que si tu as les mêmes contraintes que moi, la solution est simple. Notamment, vérifie bien que la récursivité te pose un problème avant de passer à un algo itératif. J'aurais quelques hésitations avant de coller une horreur comme ton "next_combination" dans mon programme.  
 
Imaginons que tu gardes la récursivité. Si tu ne veux pas comme moi stocker en mémoire l'ensemble des combinaisons, mais bien appliquer "grosse_fonction" pendant le parcours, pourquoi ne pas t'inspirer des "functors" de la STL ( http://www.sgi.com/tech/stl/functors.html ) ? Tu passes à ta procédure de parcours un objet qui encapsule ta fonction + tous ses arguments qui n'ont rien à voir avec le parcours. Je l'ai fait ci-dessous pour une fonction qui doit être appliquée à tous les entiers i de 0 à max. Cela oblige à "templater" le parcours mais ce n'est pas horrible.
 

Code :
  1. template <class Func> void parcours( const int max, const Func &f)
  2. {
  3. for ( int i = 0; i < max; i++ )
  4. {
  5.  f(i);
  6. }
  7. }


 
La fonction à appliquer est un objet, elle doit juste implémenter l'opérateur () appliqué à un entier i. Tu pourrais adapter sans grosse difficulté le principe à une fonction qui implémente l'opérateur () appliqué à une combinaison c, passée en paramètre à ta procédure de parcours.
 
Les autres arguments de la fonction f sont passés à la construction de l'objet qui l'encapsule. Par exemple pour une fonction qui affiche les entiers i en collant une "étiquette" derrière (paramètre supplémentaire de f qui n'a rien à voir avec le parcours), voici :
 

Code :
  1. class Affiche
  2. {
  3. private:
  5. Affiche();
  6. const std::string _etiquette;
  8. public:
  10. Affiche( const std::string &etiquette ) : _etiquette(etiquette) {;};
  12. void operator()(const int i) const
  13. {
  14.  std::cout << i << ' ' << _etiquette << std::endl;
  15. };
  18. };
  20. int main()
  21. {
  22. parcours( 10, Affiche("bananes" ) );
  23. return 0;
  24. }


 
Résultat :

Code :
  1. 0 bananes
  2. 1 bananes
  3. 2 bananes
  4. 3 bananes
  5. 4 bananes
  6. 5 bananes
  7. 6 bananes
  8. 7 bananes
  9. 8 bananes
  10. 9 bananes


 
 

Message cité 1 fois
Reply

Marsh Posté le 18-11-2006 à 14:00:15    

SkippyleGrandGourou a écrit :

Je dois avoir des problèmes d'expression, ou alors certains gueulent avant de lire...  :sarcastic:  
 
Le problème n'est pas de faire un algo bidon pour parcourir un arbre ou je ne sais trop quoi, mais d'imbriquer un nombre indéfini de boucles for... Je ne parle pas de permutations mais de combinaisons.
 
Bon, j'ai trouvé ça sur le net :
[...]
mais je me demande si ça vaut vraiment le coup de passer par une telle fonction, qui me semble un peu longue et donc peut-être moins efficace que l'appel récursif... non ?


 
Désolé de me répéter, mais cette fonction est infâme. Par contre, si elle est bien codée (je ne veux même pas chercher à comprendre comment elle fonctionne) elle sera normalement plus efficace que la récursion. Par "principe", en C++ au moins, itératif > récursif pour l'efficacité.  
 
Mais 1) si la récursion n'est pas limitante dans le cadre de tes contraintes de temps de calcul et de taille de la pile d'appel, tu ferais mieux de garder la récursion (comme ça peut-être que quelqu'un repassant un jour sur ton code aura une chance de comprendre quelque chose) et 2) le souci que tu exprimais dans ton premier post était de passer des arguments supplémentaires au parcours récursif et il y a au moins 1 solution.
 

Reply

Marsh Posté le 18-11-2006 à 14:00:15   

Reply

Marsh Posté le 20-11-2006 à 11:55:30    

franceso a écrit :

Je ne sais pas si tu as lu le lien que je t'ai donné, mais il y a de grandes similitudes entre le problème posé dans ce topic et le tien. En particulier, tous deux admettent des solutions récursives presque triviales, qu'on cherche à rendre itératives.
Tu pourras aussi remarquer que la solution que j'ai proposée dans le topic mentionné est basée sur la notion d'incrément permettant de passer d'une combinaison à la suivante, ce qui est exactement le rôle joué par la fonction next_combination que tu as trouvé sur le web. Tant que tu raisonnes en termes de "nombre indéfini de boucles for imbriquées", tu ne débouches que sur des solutions récursives ; c'est la notion d'incrément qui te permet de changer de point de vue et de rendre l'algorithme itératif.

Ok, suivant ton conseil j'ai repris ce sur quoi j'étais parti au tout début (avant la méthode récursive) et que je pensais non utilisable, et j'ai réussi à le faire fonctionner :

Code :
  1. for(int i=0;i<M;++i) k[i]=i;
  2. for(int i=M-1;i>=0;--i)
  3. {
  4. ++k[i];
  5. if(k[i]<=N-M+i)
  6. {
  7.  for(int j=i+1;j<M;++j) k[j]=k[j-1]+1; // C'est ici que j'avais mal réfléchi...
  8.  break;
  9. }
  10. else if(i==0) done=true;
  11. }


 

boulgakov a écrit :

  • Ma procédure récursive a une profondeur égale à n, et la complexité du programme que j'écris explose avec n pour des raisons qui n'ont rien à voir avec les combinaisons. Il est de toutes façons hors de question d'utiliser ce programme pour n > 3. Donc, en tenant compte des contraintes d'utilisation du programme, ma procédure récursive n'est pas limitante, ni en temps de calcul ni en risque de se manger un stack overflow. Comme la récursion est "élégante" et compréhensible, je l'ai gardée.


Dans mon cas, l'utilisation des combinaisons à la place des permutations qu'il y avait avant va faire qu'il sera possible de l'utiliser pour n>3, justement...  :D  

boulgakov a écrit :

  • J'ai besoin d'itérer un grand nombre de fois sur l'ensemble des combinaisons. Il serait catastrophique pour les temps de calcul que je les recalcule à chaque fois. J'ai donc utilisé ma procédure récursive une seule fois pour me générer toutes les combinaisons.

Ça ne fonctionnera pas (en tout cas pas simplement) pour moi, car le programme ne passe pas forcément par les N combinaisons : si l'utilisateur demande N=5, le programme va d'abord tester N=1, puis 2, jusqu'à 5, et il s'arrête dès qu'il est content.


Je pense que tant pour la lisibilité que pour l'efficacité, dans mon cas, la méthode itérative est préférable à la méthode récursive. Mais merci quand même pour les infos sur les functors, ça peut toujours servir. ;)

Message cité 1 fois
Message édité par SkippyleGrandGourou le 20-11-2006 à 11:56:33
Reply

Marsh Posté le 21-11-2006 à 13:41:04    

SkippyleGrandGourou a écrit :

Ok, suivant ton conseil j'ai repris ce sur quoi j'étais parti au tout début (avant la méthode récursive) et que je pensais non utilisable, et j'ai réussi à le faire fonctionner :

Code :
  1. for(int i=0;i<M;++i) k[i]=i;
  2. for(int i=M-1;i>=0;--i)
  3. {
  4. ++k[i];
  5. if(k[i]<=N-M+i)
  6. {
  7.  for(int j=i+1;j<M;++j) k[j]=k[j-1]+1; // C'est ici que j'avais mal réfléchi...
  8.  break;
  9. }
  10. else if(i==0) done=true;
  11. }


 
Dans mon cas, l'utilisation des combinaisons à la place des permutations qu'il y avait avant va faire qu'il sera possible de l'utiliser pour n>3, justement...  :D  
Ça ne fonctionnera pas (en tout cas pas simplement) pour moi, car le programme ne passe pas forcément par les N combinaisons : si l'utilisateur demande N=5, le programme va d'abord tester N=1, puis 2, jusqu'à 5, et il s'arrête dès qu'il est content.
 
Je pense que tant pour la lisibilité que pour l'efficacité, dans mon cas, la méthode itérative est préférable à la méthode récursive. Mais merci quand même pour les infos sur les functors, ça peut toujours servir. ;)


 
Ironie du sort : je viens de coder l'algo itératif pour les combinaisons avec répétitions... Mon raisonnement sur le récursif "élégant et qui suffit" n'a pas résisté à la deuxième utilisation que j'en ai eu !
 

Message cité 1 fois
Reply

Marsh Posté le 26-11-2006 à 05:05:56    

boulgakov a écrit :

Ironie du sort : je viens de coder l'algo itératif pour les combinaisons avec répétitions... Mon raisonnement sur le récursif "élégant et qui suffit" n'a pas résisté à la deuxième utilisation que j'en ai eu !


 
Hum...
 
Si quelqu'un avait une meilleure idée que cette chose. Il faut trouver tous les n-uplets d'entiers positifs tels que somme(n{i}) = k.  
 

Code :
  1. /** Fait passer d'une combinaison avec répétition à une autre, pour le parcours de toutes
  2. *les combinaisons avec répétitions.
  3. *param k nombre de tirages
  4.         *@param comb combinaison initiale. Le premier appel doit être fait avec (0,...,k).
  5. *@return true s'il reste des combinaisons, false sinon.
  6. */
  7. bool Utils::parcoursCombsRepets( const int k,
  8.         std::vector<int> &comb,
  9.        )
  10. {
  11. bool retour = false;
  13. if ( comb[0] == k )
  14. {
  15.  retour = true;
  16. }
  17. else
  18. {
  19.  const int n = comb.size();
  20.  if ( comb[n-1] != 0 )
  21.  {
  22.   --comb[n-1];
  23.   ++comb[n-2];
  25.  }
  26.  else
  27.  {
  28.   int i = n-2;
  29.   while(true)
  30.   {
  31.    if( comb[i] != 0 )
  32.    {
  33.     ++comb[i-1];
  34.     comb[n-1] = comb[i]-1;
  35.     comb[i] = 0;
  36.     break;
  37.    }
  38.    --i;
  39.   }
  40.  }
  41. }
  43. return retour;
  44. }


 
Pffff... Je l'ai écrite en observant les motifs qui se répétaient dans ma fonction récursive. Ca marche, mais je ne comprends pas mon code !  
 
Quelqu'un pourrait m'orienter vers qqchose de mieux ?

Reply

Sujets relatifs:

Leave a Replay

Make sure you enter the(*)required information where indicate.HTML code is not allowed