Discussion :

[co2gaz]

Hello all,

Je cherche à trouver toutes les combinaisons possible pour un tableaux 2D avec comme contrainte, toutes les valeurs sont par colonne. Pour exemple:

Entrée :
tableau de lettres
__|4 | 5 | 6
1 | A | C | B
2 | B | D | B
3 | C | B | C

Sortie :

__| 4 | 5 | 6
1 | A | C | B
2 | A | C | B
3 | A | C | B

__| 4 | 5 | 6
1 | A | D | B
2 | A | D | B
3 | A | D | B

__| 4 | 5 | 6
1 | A | B | B
2 | A | B | B
3 | A | B | B

__|4 | 5 | 6
1 | B | C | B
2 | B | C | B
3 | B | C | B

...

__|4 | 5 | 6
1 | A | C | C
2 | A | C | C
3 | A | C | C

.....

Quelqu'un aurait une idée pour faire ça ?

[pseudocode]

Tous tes tableaux ont des lignes identiques. C'est voulu ?
Auquel cas, il suffit de générer la 1ère ligne d'un tableau et de la copier 2 fois.

Si je comprend bien, la 1ère ligne est un élément du produit cartésien {A,B,C}x{B,C,D}x{B,C} (c-'est à dire les éléments uniques de chaque colonne)

[co2gaz]

, Merci @pseudocode

C'est exactement ça,

J’étais parti loin dans mon délire que je n'ai même pas vue que toutes les lignes sont les mêmes .
Il suffit de déterminer l'ensemble des valeurs possibles par colonne et d'en faire un produit cartésien.

[co2gaz]

Et voilà une petite fonction récursive pour la génération du produit cartésien qui prend en entrée un vecteur des ensembles possibles:

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
43
 
		/**
		*/
		template< typename T>
		vector<set<T>> cartesianProduct( vector<set<T>> sets ) 
		{
 
		  vector<set<T>> result;
 
		  if (sets.size() == 0) 
		  {
			return vector<set<T>>();
		  }
		  else if (sets.size() == 1)
		  {
			  return sets;
 
		  }
		  else
		  {
 
			set<T> firstSet = sets[0];
 
			vector<set<T>> remainingSets = cartesianProduct( vector<set<T>>( &sets[1], &sets[sets.size()-1] ) );
 
			for (T elm : firstSet) 
			{
			  for (set<T> remainingSet : remainingSets )
			  {
				set<T> tmpRes;
 
				tmpRes.insert( elm );
				tmpRes.insert( remainingSet.begin(), remainingSet.end() );
				result.push_back( tmpRes);
 
			  }
			}
 
		  }
 
		  return result;
 
		}