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.

[cladoo]

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.

Ah d'accord, ben j'ai utilisé ce principe dans une autre partie de mon programme sans le savoir, mais je n'avais pas envisagé une faille dans mon raisonnement et certains cas n'étaient pas solvables, d'où des boucles infinies au moment de ce fameux 'backtracking'

En fait mon problème est encore plus complexe que prévu, en effet dans certains cas (exemple C(3,6)=20) on ne peut pas diviser le nombre de possibles par k (20/3) donc il n'existe pas de solution, et dans ces cas là les arrangements A(k,p) et leur explosion du nombre de lignes sont la seule solution.

Le truc de faire varier la séquence des Zk pour obtenir l'équilibre ne fonctionne que si C(k,p) est multiple de p (autant dire peu de cas, donc C(3,5)=10 fait partie de ces exceptions).
Je vais donc les lister, déterminer la séquence des Zi optimale et la stocker afin de l'appeler si l'utilisateur demande ces cas particuliers, dans les autres cas j'utiliserai les arrangement. Quelle galère...

[pseudocode]

En fait mon problème est encore plus complexe que prévu, en effet dans certains cas (exemple C(3,6)=20) on ne peut pas diviser le nombre de possibles par k (20/3) donc il n'existe pas de solution, et dans ces cas là les arrangements A(k,p) et leur explosion du nombre de lignes sont la seule solution.

Le truc de faire varier la séquence des Zk pour obtenir l'équilibre ne fonctionne que si C(k,p) est multiple de p (autant dire peu de cas, donc C(3,5)=10 fait partie de ces exceptions).

C'est pas grave. La contrainte sur les colonnes peut être approximative ou meme dynamique du genre min<Zi<max ou alors variance(Z1,Z2,Z3,...)<seuil.

L'important c'est d'avoir une contrainte qui permette de savoir si on peut continuer a avancer dans la résolution, ou alors s'il faut revenir en arrière.

[cladoo]

Donc tu penses que c'est jouable?

[pseudocode]

Donc tu penses que c'est jouable?

et bien ton cas le plus grand doit être C(10,5)=252 lignes, ce qui n'est pas si énorme. En plus, si tu ne cherches pas une solution exacte, ca doit limiter les essais possibles.

[cladoo]

Bon ben y'a plus qu'à
Si j'arrive à mes fins, je posterai histoire de suivre le problème.

[thinkbig]

Très bonne explication merci, juste une idée comme ça :
Est il possible de fractionner le problème en deux, en premier lieu trouver la position d’insertion des Zi, dans l’exemple il s’agira au départ de former une matrice de tel sorte que sur les lignes on aura :
Somme des Zi = C avec i = 1 à k
et sur les colonnes :
Somme des Zj = C ! avec j = 1 à C(c,k)
Où Z [0,1]

Excuse moi pour le formalisme qui crève les yeux je ne sais pas encor comment on écrit des équations sur le forum.
Cela nous donne un programme linéaire, et il est intéressant de voir le résultat car l’existence de plusieurs solutions « dans la plus part des cas » est évidente.
En deuxième lieu, il s’agira de résoudre un problème d’affectation, les algorithmes traitant ce sujet sont nombreux.

[cladoo]

Alors voici la solution que j'ai retenue (et à mettre en place d'un point de vue algorithmique):

Suivant les bornes données, j'ai 36 cas

- pour les combinaisons où l'équilibre est réalisable pour un nombre l multiple de C(k,p) et de p, je distribue les Zi de manière circulaire et je stocke la structure dans une BDD pour la rappeler le cas échéant (24 cas)

- pour les autres cas où l'équilibre n'est pas possible sur l= C(k,p) j'utilise les arrangements, donc je distribue mes permutations de k éléments parmi mes combinaisons de C(k,p) (12 cas)

Du coup j'ai plusieurs cas où je gagne un nombre conséquent de lignes (point 1) et les autres cas où mes lignes explosent. Je vais tout de même intégrer une option permettant de demander l'équilibre ou non.