Discussion :

[guadock]

Bonjour à tous.
J'ai un petit souci car je ne trouve pas un algorithme qui ne doit pourtant pas etre si compliqué.
Le problème est le suivant:
J'ai un nombre N de variables qui peuvent prendre chacune un certain nombre de valeur.
Par exemple la 1ere variable varie entre Min = 0 et Max = 10 avec un pas de 1. Cette variable va donc prendre 10 valeurs.

Je dois afficher les résultats d'une fonction appliquée sur l'ensemble des N-uplét possibles. IE: s'il existe une combinaison possible de variable alors le résultat de la fonction appliquée à cette combinaison doit etre affiché.

Cela peut parraitre simple. Mais je dois en fait construire un algorithme générique (dynamique) car je ne connais pas par avance le nombre de variable.

J'ai pensé à un algorithme récursif mais je n'ai pas le droit d'en utiliser.


Merci d'avance pour votre aide.

[Franck Dernoncourt]

la 1ere variable varie entre Min = 0 et Max = 10 avec un pas de 1. Cette variable va donc prendre 10 valeurs.

11

Google "combinatorial algorithms".

Un algo intuitif serait de boucler sur i=0 to 11^N, de prendre a[0] = i % 11 pour le premier, a[k] = ((i - a[k-1]) / 11) % 11 avec :

• N ton nombre de variables
• k entre 1 et 11.
• a ton n-uplet

[guadock]

Merci pour ta correction. Effectivement il y a 11 valeurs possibles.
Je vais regarder ce que tu m'as conseillé.
Merci!

[Franck Dernoncourt]

Tiens par hasard je viens de devoir programmer cela en C++, j'ai pris un autre algo qui me passait par la tête (je n'ai pas besoin de l'optimiser), voici le code si intéressé :

Code C++ :

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

1
2
3
4
5
6
7
8
9
10
11
12
std::vector<std::vector<int> > all_tuples;
std::vector<int> a(N);
int number_of_values = Max - Min + 1;
int number_of_tuples = pow(number_of_values,N);
for (int i = 0; i < number_of_tuples; ++i) {
	std::vector<int> a(N);
	std::fill(a.begin(), a.end(), 0);
	for (int cursor = 0; cursor < N; ++cursor) {
		a[cursor] = ((int)(floor(i / pow(number_of_values,cursor))) % number_of_values));
	}
	all_tuples.push_back(a);
}