Discussion :

[cladoo]

Bonjour,

Pour résumer:

je cherche à distribuer k éléments parmi p possibles, chaque élément distribué est noté (Z1, Z2 ... jusqu'à Z(k) ).
Je sais déterminer toutes mes combinaisons pour distribuer mes éléments dans ma matrice, mais le problème c'est que j'ai une contrainte supplémentaire : les éléments distribués doivent être "à l'équilibre", cad autant de Z1,Z2... par colonne pour chaque colonne.
(Pour illustrer simplement ce dont je parle voir le fichier Excel en pièce jointe.)

J'avais prévu de distribuer mes Zi de la manière suivante (exemple 3 éléments)
Z1 Z2 Z3
Z2 Z3 Z1
Z3 Z1 Z2
Z1 Z2 Z3
etc.. en avançant dans le vecteur. Bien évidemment ce n'est pas équilibré

Avez-vous une idée?
Merci d'avance
Cladoo

PS : ça ne change pas grand chose, mais je travaille sous Windev 14 et je pilote Excel via OLE.

[thinkbig]

Si tu peu donnée plus de précision sur la notion d’équilibre « une définition plus rigoureuse », la taille de la matrice ? Y a-t-il une relation avec les Zi, tu parles de contraintes mais elles ne sont pas définies.

[cladoo]

Bonjour,

l'utilisateur choisit :
k (nombre de Zk à placer dans la matrice)
p (nombre de produits ou de colonnes)
k < p (toujours vrai)

Le but est de faire apparaître toutes les combinaisons de colonnes (ou de produits si on préfère) possibles avec les choix de l'utilisateur, il y en a C(k,p). Exemple C(3,5)=10 ou encore C(2,6)=15 http://fr.wikipedia.org/wiki/Combina...%A9matiques%29

Une fois chaque combinaison possible déterminée (ce point est déjà géré) je dois y distribuer mes Zk (si k = 3 alors on doit distribuer Z1, Z2, Z3) de sorte que j'ai autant de Z1 que de Z2, Z3 dans chaque colonne mais également autant de Z1 dans la colonne A que B que C, idem avec Z2 et Z3 etc...
C'est que j'appelle "être à l'équilibre". Aucune distribution de Zk ne doit favoriser telle ou telle colonne en terme de distribution.

Une solution serait de distribuer toutes les permutations possibles dans chaque bloc de combinaisons possibles, exemple :
k=3 et p=5 j'ai donc C(3,5)=10 lignes pour réaliser toutes mes combinaisons possibles. Pour être certain d'être à l'équilibre, je peux distribuer dans ces 10 lignes successivement toutes les permutations possibles de 3 éléments (k=3 et 3!=6) soit 6 permutations, on arrive donc à 10*6=60 lignes (ce qui est égal à A(3,6) http://fr.wikipedia.org/wiki/Arrangement )

Or et c'est là où je suis très très embêté : là où le second algorithme me demande 60 lignes pour "équilibrer ma matrice" je peux en utiliser seulement 10 dans mon cas, en faisant varier la séquence distribuée de Zk de sorte à équilibrer mes colonnes


Donc il est possible dans certains cas de réduire considérablement le nombre de ligne (et c'est un point primordial dans mon cas) et obtenir le même équilibre. En effet je n'ai aucune contrainte quant à la séquence de Zk utilisée, je ne suis absolument pas obligé à faire apparaître toutes les permutations.

Qu'en penses-tu?

[pseudocode]

Cela ressemble à un problème de Sudoku, donc solvable avec des techniques de backtracking ou alors de coloration de graphe. Par contre, ca risque de prendre du temps pour des grandes de valeurs k,p

[cladoo]

Cela ressemble à un problème de Sudoku, donc solvable avec des techniques de backtracking ou alors de coloration de graphe. Par contre, ca risque de prendre du temps pour des grandes de valeurs k,p

EN fait j'ai borné mes k et p :
k : [2,9]
p : [3,10]
k < p

Je ne connais pas le backtracking , c'est quoi le principe?

[pseudocode]

EN fait j'ai borné mes k et p :
k : [2,9]
p : [3,10]
k < p

Je ne connais pas le backtracking , c'est quoi le principe?

C'est un mot compliqué pour dire qu'on revient en arrière si on se trompe.

Dans ton cas C(3,5), il faut placer 30 jetons (10xZ1, 10xZ2, 10xZ3) sur les cases bleus en respectant les contraintes (1 Zi par ligne et 2 Zj par colonne).

On commence par mettre un jeton au hasard sur la 1ere case, on choisit un jeton possible (respectant les contraintes) pour la 2eme case, etc. jusqu'a ce que le remplissage soit complet (gagné !) ou alors qu'on ne puisse plus placer de jeton (perdu !). Dans ce dernier cas, on retire le dernier jeton placé et on le remplace par un autre possible.