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