transformer un code itératif en récursif

Salut tout le monde,

Je veux développer une fonction qui me rend toutes les combinaisons possibles à partir d'un vecteur d'entier.
Par exemple si j'ai le vecteur v1={1,2,3,4} elle me retourne un string qui contient toutes les combinaisons séparée par un espace{1,12,123,1234,124,13,134,14,2,23,234,24,3,34,4}.Je pense qu'une fonction récursive pourra résoudre mon problème.J'ai raisonné de cette façon mais je n'est pas su comment faire pour rendre ce code récursif:

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 31 32 33 34

vector<int> v1; vector<int>v2; ostringstream oss; string ss;   v1.push_back(1);v1.push_back(2);v1.push_back(3);v1.push_back(4);   for(int i=0;i<v1.size();i++) { oss<<v1[i]<<" "; ss=oss.str(); for(int k=i+1;k<v1.size();k++) { oss<<v1[i]<<v1[k]<<" "; ss=oss.str(); for(int j=k+1;j<v1.size();j++) { oss<<v1[i]<<v1[k]<<v1[j]<<" "; ss=oss.str(); for(int l=j+1;l<v1.size();l++) { oss<<v1[i]<<v1[k]<<v1[j]<<v1[l]<<" "; ss=oss.str(); for(int p=l+1;p<v1.size();p++) { oss<<v1[i]<<v1[k]<<v1[j]<<v1[l]<<v1[p]<<" "; ss=oss.str(); } } } } } cout<<ss;

---

Je serais très reconnaissante si vous pourriez me donner un petit coup de main pour résoudre mon problème.Merci d'avance

L'idée est de parcourir ton vecteur du premier au dernier élément, et à chaque étape d'ajouter 2 "groupes de solutions" : ceux qui incluent l'élément, et celles qui ne l'incluent pas. Donc, tu pourrais avoir une fonction récursive de ce genre...

Code:

---

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21

// tes données vector<int> v;   // w est la solution en cours de construction, //lev la position dans v où l'on se trouve // lev peut être remplacé par un itérateur sur v, // si tu veux absolument faire moderne void recurs(vector<int> &w,int lev) { // on a fini, imprimer le vecteur résultat if(lev==v.size()) print(w); else { //ajouter l'élément en cours vector w1=w; w1.push_back(v[lev]); lev++; recurs(w1,lev); recurs(w,lev); } }

---

Pour énumérer tous les sous ensembles, tu remplis v, tu crées un vecteur w vide, et tu appelles recurs(w,0). Ca devrait t'imprimer le résultat dans le même ordre que ta fonction d'avant... Je n'ai pas testé, donc il se peut qu'il faille modifier un ou deux trucs, mais c'est l'esprit.

Comme souvent avec les fonctions récursives, celle ci sera probablement lente. Une façon plus élégante d'aborder ce problème serait de le considérer comme un problème d'énumération. En gros, tu énumères tous les sous ensembles de v, et pour cela, tu vas, pour chaque élément, avoir deux cas : "avec" et "sans". Ca te fait donc 2^N cas.

Pour N pas trop grand (de toutes façons, si N dépasse la vingtaine, l'énumération dépasse le million de cas, et ca n'a plus beaucoup de sens), tu pourrait avoir une simple boucle, de 0 à 2^N, dans laquelle le compteur de boucle te sert également de masque de bits pour savoir quels éléments de ton vecteur v sont sélectionnés. Pour 4 éléments tu aurais un truc comme

Code:

---

1 2 3 4 5 6

unsigned masks[4]={1,2,4,8}; for(unsigned int i=0;i<16;i++) { for(int j=0;j<4;j++) if( (i&masks[j]) !=0) cout<<v[j]; cout<<" "; }

---

Ca risque d'aller nettement plus vite... (dans un vrai programme, tu remplacerais bien sur 16 et les masques par des paramètres).

Ceci fonctionne si tu cherches des sous ensembles (donc si v n'a pas d'éléments en doublon), si tu as des répétitions, alors il te faudra d'autres méthodes d'énumération (il y avait autrefois sur le site de Knuth des previews du tome 4 de l'art of computer programming, qui contenait un plein chapitre sur le sujet...)

Francois

Merci pour votre réponse.J'ai essayé ta fonction récursive:

Code:

---

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15

void recurs(vector<int> &w,int lev) { vector<int> v; // on a fini, imprimer le vecteur résultat if(lev==v.size()) PRINT_ELEMENT(w); else { //ajouter l'élément en cours vector <int>w1=w; w1.push_back(v[lev]); lev++; recurs(w1,lev); recurs(w,lev); } }

---

et pour l'appeler:

Code:

---

1 2 3 4

vector<int> v1; v1.push_back(1);v1.push_back(2);v1.push_back(3);v1.push_back(4); recurs(v1,0);

---

pour le niveau 0 ça me ramène le résultat exacte mais à partir du niveau 1 ça me génère le message de débordement de mémoire.Je me demande si on pourrais pas rajouter un clear() dans l'un des vecteurs dans la fonction récursive

sinon y'a std::next_permutation() et std::prev_permutation() hein pour les différentes combinaisons d'un containeur.

svp pourriez vous me donner un petit exemple comment utiliser std::next_permutation() et std::prev_permutation().Merci d'avance

Voilà :

Code:

---

1 2 3 4 5 6 7 8 9

std::vector<int> v1; v1 += 0,1,2,3;   while(std::next_permutation(v1.begin(), v1.end())) { std::copy(v1.begin(), v1.end(), std::ostream_iterator<int>(std::cout, " ")); std::cout << std::endl; }

---

Citation:

---

Envoyé par FstDsi

et pour l'appeler:

Code:

---

1 2 3 4

vector<int> v1; v1.push_back(1);v1.push_back(2);v1.push_back(3);v1.push_back(4); recurs(v1,0);

---

pour le niveau 0 ça me ramène le résultat exacte mais à partir du niveau 1 ça me génère le message de débordement de mémoire.Je me demande si on pourrais pas rajouter un clear() dans l'un des vecteurs dans la fonction récursive

---

Ben forcément .... Dans mon code, le premier parametre de recurs() c'est une référence sur le vecteur contenant le résultat (qu'on imprimera à la fin). Au démarrage, il faut lui passer un vecteur vide. Si tu lui passes la donnée, il va se passer des choses affreuses...

Et dans ta version de mon code, si tu mets v comme variable locale de la fonction recurs() ca va pas marcher non plus...

En fait, tu as deux vecteurs
- v, qui correspond aux données, celui là il ne bouge pas d'un appel à l'autre de la fonction récursive (tu peux le passer en réference constante si tu veux)
- w, le paramètre de recurs() qui contient la solution en cours de construction (puisque chaque appel à recurs() la construit un peu plus)


@goten : les permutations, c'est tout autre chose...
{1,12,123,1234,124,13,134,14,2,23,234,24,3,34,4}, ce ne sont certainement pas les permutations de {1,2,3,4} (les permutations, ce seraient 1234,1243,1342,1432, etc...)... Ce que FstDsi génère, ce sont les sous ensembles (et, au passage, les combinaisons c'est encore autre chose: c'est quand on prend k objets parmi n, les permutations y'en a n!, les sous ensembles 2^n, les combinaisons C(n,k), le coeff binomial, les sous ensembles, ce sont toutes les combinaisons, pour toutes les valeurs de k).

Francois

oups matin toussa toussa ^^. Ca m'apprendra à lire en travers. (btw j'avais pas vu le mots sous-ensemble justement)

Merciiiiiiiii bcp fcharton.En fait je passais de faux paramètres pour la fonction.ça marche mnt.Merci a tous

WoW ! fcharton, la solution qui incrémente un compteur de 0 à 2^N et dont les bits à 1 énumèrent progressivement les sous-ensembles est absolument magnifique !

Citation:

---

Envoyé par Arzar

WoW ! fcharton, la solution qui incrémente un compteur de 0 à 2^N et dont les bits à 1 énumèrent progressivement les sous-ensembles est absolument magnifique !

---

Toi, faut que tu lises Knuth (début du tome 4, mais il y a de très jolies choses sur le sujet au début du chapitre sur l'arithmétique, le second du tome 2)...

Ces méthodes d'énumération sont intéressantes, parce qu'il est assez facile de les adapter à des énumérations sous contraintes, ou des collections plus compliquées. (Par exemple, pour les permutations, tu pourrais considérer que ton indice est écrit dans une "base factorielle": premier chiffre en base N, second en base N-1, etc... l'écriture de ton indice dans cette base est ta permutation...)

Dans ce cas précis, la véritable utilité de la méthode, c'est la fabrication de "sous ensembles au hasard"...

Si tu as un ensemble de N éléments (N grand), et que tu veux tirer des sous ensembles au hasard, tu génère juste un nombre aléatoire entre 0 et 2^N (en fait, une série d'entiers au hasard...), et tu appliques la méthode...

Francois

svp juste une toute dernière question pour fcharton.

Code:

---

1 2 3 4 5

v.push_back(1);v.push_back(2);v.push_back(3);v.push_back(4); recurs(res,0); cout<<res.size()<<endl; PRINT_ELEMENT(res);

---

Tu m'as dit que le vecteur que tu passe en paramètre contient toutes les combinaisons,or que quand j'affiche la taille du vecteur ça me ramène 0 et quand je veux afficher le contenu de res en dehors de la fonction récursive ça ne m'affiche rien du tout.En fait,j'aurais besoin des éléments de ce vecteur pour un traitement ultérieur en dehors de la fonction donc comment les récupérer.Merci d'avance.

Citation:

---

Envoyé par FstDsi

Tu m'as dit que le vecteur que tu passe en paramètre contient toutes les combinaisons,or que quand j'affiche la taille du vecteur ça me ramène 0 et quand je veux afficher le contenu de res en dehors de la fonction récursive ça ne m'affiche rien du tout.

---

Ben non, le vecteur qu'on passe à la fonction récursive, il contient des bouts de solution, pas la solution tout entière... Donc oui, c'est normal, c'est un peu le propre des fonctions récursives en fait.

Citation:

---

Envoyé par FstDsi

En fait,j'aurais besoin des éléments de ce vecteur pour un traitement ultérieur en dehors de la fonction donc comment les récupérer.Merci d'avance.

---

C'est ce pourquoi j'ai mis dans mon code une fonction print... Au lieu d'écrire à l'écran, tu peux copier les solutions dans un vecteur, ou un fichier, ou une chaine...

Francois

Salut tout le monde,
@fcharton:En fait, votre version récursive marche à merveille sauf que le seul inconvénient est qu'elle demande un temps d'exécution assez important donc j'ai opté pour votre deuxième solution puisque vous avez dit qu'elle est rapide:

Code:

---

1 2 3 4 5 6

unsigned masks[4]={1,2,4,8}; for(unsigned int i=0;i<16;i++) { for(int j=0;j<4;j++) if( (i&masks[j]) !=0) cout<<v[j]; cout<<" "; }

---

sauf que celle la me ramène un message de débordement de mémoire.J'aimerais bien, que vous m'expliquer un peu plus cette deuxième solution et est ce que je pourrais l'utiliser aussi pour un autre genre d'énumération.J' m'explique:
En fait dans l'algorithme que je suis en train d'implémenter j'utilise plusieurs sortes d'énumération,la première est celle que j'avais expliqué dans mon ancien post.Ce que je vais faire maintenant,c'est une énumération plus restreinte:je prend en entrée deux paramètres(vecteur,entier).Le vecteur contient les éléments à partir desquels je vais faire les combinaisons et l'entier représente l'élément qui doit être présent dans toutes les combinaisons.Par exemple:si j'ai le vecteur v1={1,2,3,4} et l'entier c'est 2 je dois avoir un résultat:v2{12,23,24,123,124,234,1234}.
Merci d'avance

Pour le débordement de mémoire, faudrait voir ce qu'il y a dans v... (ca doit être un tableau de 4, valeurs v[4]={1,2,3,4}; ou un truc comme ca)

Peut être aussi regarder le i&masks[j], je ne sais plus trop comment les précédences s'organisent ici...

De toutes facons, en exécutant le programme pas à pas, avec un débugueur, l'erreur devrait apparaitre très vite, c'est un tout petit code...

Pour ce qui est des contraintes :

Si l'on veut n'énumérer que les sous ensembles qui contiennent la valeur 2, on a deux choix...

1- enlever 2 de la liste (on a alors les sous ensembles de l'ensemble {1,3,4} et le rajouter à la fin, c'est certainement la solution la plus simple dans ce cas précis
2- ajouter un test au début de la boucle

Code:

---

1 2 3 4 5 6 7

unsigned masks[4]={1,2,4,8}; for(unsigned int i=0;i<16;i++) { if(i&mask[1]==0) continue; // ceci élimine les sous ensemble ne contenant pas le second élément for(int j=0;j<4;j++) if( (i&masks[j]) !=0) cout<<v[j]; cout<<" "; }

---

Francois

Merci pour votre réponse,le prob du débordement mémoire est réglé mais je ne trouve pas exactement le résultat souhaité.Par exemple si je prend un vecteur v={1,2,3,4} et je veux avoir toutes les combinaisons de avec l'entier 2 ça me retourne un résultat {1,2,12,3,13,23,123,4,14,24,124,34,134,234,1234,1}
or que le résultat attendu est {12,23,24,123,124,234,1234}.

Code:

---

1 2 3 4 5 6 7 8 9 10

std::vector<int>v; v.push_back(1);v.push_back(2);v.push_back(3);v.push_back(4); unsigned masks[4]={1,2,4,8}; for(unsigned int i=0;i<16;i++) { //cout<<i<<endl; if(i&masks[1]==0) continue; // J'aimerais comprendre l'utilité de cette ligne for(int j=0;j<4;j++) if( (i&masks[j]) !=0) cout<<v[j]; cout<<" "; }

---

Je vous remercie énormément.

Code:

---

if(i&masks[1]==0) continue;

---

Vérifie normalement si le second bit de i (celui qui indique la présence du second chiffre, donc 2, dans le sous ensemble) est à 1. Je ne veux pas être désobligeant, mais j'ai un peu la sensation que vous ne comprenez pas du tout la méthode...

L'idée est la suivante,

1- pour un ensemble de n éléments, il y a 2^n sous ensembles, que l'on représente par un nombre binaire de n chiffres, un 1 indiquant que l'élément est dans le sous ensemble, un 0 qu'il n'y est pas. Dans notre exemple le nombre binaire (0101 correspond donc au sous ensemble {1,3})
2- si je parcours tous les nombres entre 0 et 2^n-1, je vais donc énumérer tous les sous ensembles, le tableau masks[], qui contient les nombres binaires (0001, 0010,0100,1000) est utilisé pour détecter si un élément particulier est dans le sous ensemble
3- pour énumérer, on parcourt donc tous les chiffres (ici entre 0 et 15), mais on peut ajouter des contraintes, qui s'expriment alors comme des conditions dans la boucle.

Voila

Francois

Citation:

---

Vérifie normalement si le second bit de i (celui qui indique la présence du second chiffre, donc 2, dans le sous ensemble) est à 1.

---

Comment je vérifie ça svp??J'arrive pas a te comprendre fcharton :cry: ça vous parait tellement évident alors que ce n'est pas le cas pour moi, le principe est bien clair mais je ne vois pas comment ça se concrétise dans le prog.Svp juste une dernière fois explique moi en me détaillant les entrées et les sorties du petit prog et montre moi l'exécution manuelle pour au moins une itération.Je voulais faire des affichages pour pouvoir au moins suivre l'exécution mais j'ai mm pas su qu'est ce que je devrais afficher. Merci d'avance pour votre patience

Une suggestion proche de celle de fcharton, qui évite d'écrire en dur des masques, et qui ne nécessite que trois entiers :

Code:

---

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18

val = 2; //En supposant qu'il s'agît de ne jamais générer 0 n = 4; for (int i = 0; i < (1 << n); ++i) { if (! (i & (1 << (val - 1)))) { continue; } for (int j = 0; j < n; ++j) { if (i & (1 << j)) { s << " " << j + 1; } } s << std::endl; }

---

i va servir à déterminer quelles sont les combinaisons possibles. Le bit k de i est à 1 si et seulement si le tirage que l'on veut faire contient le nombre k.
Ex :
i = 5 (cad 1001) ça signifie que 4 et 1 seront tirés

dans la boucle intérieure, on regarde pour toutes les valeurs j entre 0 et n, si le j-ième bit est à 1, si oui on l'affiche, sinon on passe au suivant.

La boucle extérieure elle, permet de générer toutes les combinaisons possible. Elle ne tient pas compte de l'ordre puisque 4 et 1 ou 1 et 4 sont représentés par la même valeur.

Avec cette solution, il faut faire attention aux overflows si jamais on donne de grandes valeurs à n : il faut que i et (1 << j) soient dans des types entiers de minimum n bits.

Voilà si je n'ai pas été assez clair, me demander, j'essaierai de mieux expliquer.

Edit : j'avais oublié de filtrer tous les résultats contenant une valeur précise (nommée val ici).

Salut,

D'un point de vue tout autre que celui que fcharton essaye de t'expliquer, je me demande pour quelle raison tu souhaites transformer un code itératif en un code récursif (ce que fcharton n'est d'ailleurs plus occupé à t'expliquer)...

En effet, bien que la récursivité ait des avantages très sérieux, c'est typiquement le genre de technique qu'il ne faut envisager que lorsqu'il est impossible (ou du moins très difficile) de faire autrement, parce qu'elle souffre par ailleurs de certaines contraintes qui lui sont propres.

C'est la raison pour laquelle j'approuve fcharton de te présenter une optique qui reste itérative mais qui soit en mesure d'améliorer les performances générales ;)

Bonjour tout le monde,

@koala01:j'ai choisi la méthode récursive parce que je pensais qu'elle est plus rapide en temps d'exécution or que ce n'est pas du tout le cas.La version itérative est meilleure.
@fcharton et thetux :un grand merci pour vos réponse c'est bon mnt votre méthode est bien claire.

Merci pour tout les membres de ce forum.

Citation:

---

Avec cette solution, il faut faire attention aux overflows si jamais on donne de grandes valeurs à n : il faut que i et (1 << j) soient dans des types entiers de minimum n bits.

---

Svp aidez moi je dois faire quoi lorsque j'ai n très grand,je me suis rendu compte que j'ai de fausses résultats lorsque n est grand ??je doi le déclarer comment sur n bit??je déclare une structure???svp je n'arrive pas à corriger cela et je me retrouve bloquée.Merci d'avance

Remplacer le type de n de "int" en "long" ou "long long" devrait te permettre d'éviter temporairement l'overflow.

Mais bon, comme fcharton l'a expliqué, l'ensemble des combinaisons d'un vecteur à pour taille 2^N : Quelle que soit la méthode utilisée, il est complètement impossible d'avoir N "très grand', le PC sera mis à genou bien avant.

(Par exemple 2^32 = 4294967296, donc si tu veux avoir la liste des combinaisons de 32 éléments la string finale prendra au minimum du minimum... 4Go de RAM ! )

Et mets unsigned int, au lieu de int... par défaut (je ne sais pas si c'est la norme ou l'habitude) les entiers sont signés...

Pour des valeurs de N dépassant 32, la solution la plus simple est d'imbriquer plusieurs boucles. La boucle du haut gère les 32 premiers termes, la suivante les 32 suivants, etc... Mais là encore, pour 32 éléments, il y a 4 milliards (4e9) de sous ensembles, avec 64 ca va faire 16e18... ca devient vite impossible à gérer...

Enfin bon, si tu as 33 ou 34 éléments : deux boucles imbriquées, ...

Francois

Merci pour vos réponses,
Dans mon programme le n est égal à 68 comment je fait pour faire des boucles imbriquées??
Est il préférable de faire une fonction récursive pour que ça soit plus général?Merci encore

Citation:

---

Envoyé par FstDsi

Merci pour vos réponses,
Dans mon programme le n est égal à 68 comment je fait pour faire des boucles imbriquées??
Est il préférable de faire une fonction récursive pour que ça soit plus général?Merci encore

---

N=68? Tu aurais besoin de 3 boucles imbriquées : 2^32, 2^32 et 2^4...

Mais le nombre de permutations est alors de 2,56e20... Si tu en énumérais 1 milliard par secondes, il te faudrait plus de 8000 ans pour en venir à bout (et à mon avis, tu seras plus proche de un million, donc ce sera plutôt 8 millions d'années).

Francois

Je ne sais pas ce que je vais faire.En tt cas merci énormément pour vos rep

Citation:

---

Envoyé par FstDsi

Je ne sais pas ce que je vais faire.En tt cas merci énormément pour vos rep

---

Peux tu expliquer pourquoi tu veux énumérer ces sous ensembles? Parce que la méthode de comptage, qui permet de représenter un sous ensemble par un nombre, te permet de les accéder sans les énumérer...

C'est comme avec les nombres, pour utiliser le nombre 112354, tu n'as pas besoin de compter tous les nombres qui le précèdent.

Francois

Bjr,

En fait je t'explique ce que je suis en train de faire.Je suis en train de traiter un sujet de fouille de données qui consiste à extraire à partir d'un fichier texte la position des "1" (ligne et colonne):Le fichier texte est de la forme suivante.

1 0 1 0 1 1 1 0
1 0 0 0 1 1 0 1
1 0 1 0 1 1 1 0
1 1 1 0 1 0 0 0
.....

J'aurais donc deux vecteurs l'un contient la position du "1" pour la ligne et l'autre pour la colonne.Dans cet exemple j'aurais:
1 1 1 1 1 2 2 2 3 3 3 3 3 //vecteur relatif aux lignes
1 3 5 6 7 1 5 6 1 3 5 6 7 //vecteur relatif aux colonnes

Ce que je fais c'est que pour chaque couple j'extrait la ligne et la colonne correspondante et je la met dans une structure constituée par deux vecteurs
Par exemple pour le couple (1;1) j'aurais deux vecteurs <1,2,3,4>(relatif aux lignes) et <1,3,5,6,7> (relatifs aux colonnes).Puis je fais toutes les combinaisons du deuxième vecteurs pour des traitements ultérieurs (pas la peine de vous casser la tête avec )
*Pour le couple (1,3) j'aurais les vecteurs <1,3,4> et <1,3,5,6,7> et j'aurais besoin des combinaisons du deuxième vecteurs qui contient 3 (parce que je traite le couple (1,3)) cad 35 36 37 356 357 .....
*Pour le couple (2,5) j'aurais les vecteurs <1,2,3,4> et <1,5,6,8> et j'aurais besoin des combinaisons du deuxième vecteur qui contient 5 cad 56,58 et 568.

Bref, la solution que vous m'avais proposé me donnais des résultats correcte avec de petits fichiers mais quand j'avais testé sur des grands fichiers la taille du deuxième vecteur (à partir duquel j'extrais mes combinaisons) deviens grande et la fonction ne me génère plus de résultats.Je vous donne la version finale de la fonction:

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 31 32 33 34 35 36 37 38 39 40 41 42

string OpContexte::generer_combinaison(const vector<int>& vect,int pos) { string combinaison; ostringstream oss;     //j'ai essayé de changer tous les int de cette fonction en unsigned int ou float float mais ça ne marche tjs pas     int val = pos; int n = vect.size(); //char s; for (int i = 0; i < (1 << n); ++i) {     if (! (i & (1 << (val - 1)))) {   continue; } for (int j = 0; j < n; ++j) { if (i & (1 << j)) { oss.clear(); oss << vect[j]; combinaison = oss.str(); oss<<" ";   }     } oss<<",";   }   return combinaison;   }

---

Code:

---

1 2 3 4 5 6 7 8 9 10 11

int main(int argc, char* argv[]) { .... int jj=0; for(int k=0;k<p.intent.size();k++){ //p.intent représente le deuxième vecteurs à partir duquel j'extrais les combinaisons if(p.intent[k]==attr_courant) //le couple que je traite est (exp_courant,attr_courant) jj=k+1; }//end for str=oc.generer_combinaison(p.intent,jj); return 0; }

---

Je sais que c'est compliqué ce que je vous raconte et vous n'êtes pas censé comprendre tous ces détails mais c'est que je me retrouve bloquée encore une fois :( .En tous les cas je ne vous remercierais jamais assez pour votre aide vous m'avez énormément aidé dans ce forum.