Discussion :

[FstDsi]

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 :

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
 
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

[Invité]

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 :

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
 
// 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 :

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

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

[FstDsi]

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

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
 
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 :

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

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

[Goten]

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

[FstDsi]

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

[Goten]

Voilà :

Code :

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

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;
    }

[Invité]

et pour l'appeler:

Code :

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

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

[Goten]

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

[FstDsi]

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

[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 !

[Invité]

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

[FstDsi]

svp juste une toute dernière question pour fcharton.

Code :

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

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.

[Invité]

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.

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

[FstDsi]

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 :

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

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

[Invité]

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 :

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

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

[FstDsi]

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 :

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

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.

[Invité]

Code :

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

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

[FstDsi]

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 ç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

[thetux]

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

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
 
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).

[koala01]

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