Discussion :

[FstDsi]

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.

[FstDsi]

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

[Arzar]

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

[Invité]

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

[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

[Invité]

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

[FstDsi]

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

[Invité]

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

[FstDsi]

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 :

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

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

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.