Discussion :

[Adesfire]

Bonjour à tous,
suite à mon précédent problème (résolu avec brio par badaze) je me hurte à un nouveau problème.

Je dispose du tableau suivant :

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
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
 
Array
(
    [01/01/2001] => Array
        (
            [0] => Array
                (
                    [A] => joe
                    [B] => pierre
                    [C] =>  
                    [D] =>  
                    [E] =>  
                )
 
            [1] => Array
                (
                    [A] => joe
                    [B] =>  
                    [C] => pierre
                    [D] =>  
                    [E] =>  
                )
 
            [2] => Array
                (
                    [A] => joe
                    [B] =>  
                    [C] =>  
                    [D] => pierre
                    [E] =>  
                )
 
        )
 
    [02/01/2001] => Array
        (
            [0] => Array
                (
                    [A] => joe
                    [B] => pierre
                    [C] => betty
                    [D] =>  
                    [E] =>  
                )
 
            [1] => Array
                (
                    [A] => joe
                    [B] => pierre
                    [C] =>  
                    [D] => betty
                    [E] =>  
                )
 
            [2] => Array
                (
                    [A] => joe
                    [B] =>  
                    [C] => pierre
                    [D] => betty
                    [E] =>  
                )
 
            [3] => Array
                (
                    [A] => joe
                    [B] =>  
                    [C] => betty
                    [D] => pierre
                    [E] =>  
                )
 
        )
...

Comme vous pourrez le voir, le premier niveau contient des dates, le second des tableaux de répartition de personnes à des emplacements (le nombre de tableau de répartition varie d'une date à l'autre).

Voici comment je pourrais énoncer le problème :

• On ne peut choisir qu'une seule répartition par date
• Sur l'ensemble des dates, la répartition doit être la plus équitable possible

L'objectif étant que sur une semaine, l'écart d'apparition entre pierre, betty et joe soit le plus limité possible afin d'être équitable.

Pour y parvenir, j'avais pensé :

• Parcourir de facçon recursive les dates
• Puis leurs compositions
• Calculer pour chaque composition le nombre d'apparition par personne
• et recommencer la parcours des dates suivantes...

Une fois terminé (avec un très grand nombre de combinaisons) déterminer l'écart minimum entre le plus représenté et le moins représenté, et en déduire la combinaison la plus équitable.

Je bloque cependant sur le parcours récursif, car il est particulier....je dois entrer dans une date, boucler sur les propositions puis reboucler sur les dates et propositions sans rependre la date en cours

Le moins que l'on puisse dire, c'est que j'ai du mal

Il existe peut être une meilleure méthode, je suis preneur dans ce cas !

Quoi qu'il en soit merci pour votre aide éventuelle !

[badaze]

Je n'ai rien compris. Dans tous les cas pour une même date, l'algorithme de ta précédente discussion fait que toutes les personnes apparaissent au final un même nombre de fois.

Cependant. A vue de nez. Tu n'as pas besoin de toutes les permutations => Joe, Pierre, Betty doit être équivalent à Betty, Pierre, Joe ou Betty, Joe, Pierre, etc... Correct ou pas ?

Les exemples que tu donnes ne permettent pas de se faire une idée.

• Est-ce que le nombre de places peux varier d'un jour sur l'autre ?
• Pour la même date peux-tu avoir par exemple 7 personnes pour 5 emplacements?
• Est-ce que par exemple tu peux avoir pour le lundi 5 personnes pour 5 places et pour le mardi 5 autres personnes pour les mêmes 5 places ?
• Est-ce qu'au final toutes les personnes doivent être placées ?

Voilà. C'est tout pour le moment.

[Adesfire]

Je n'ai rien compris. Dans tous les cas pour une même date, l'algorithme de ta précédente discussion fait que toutes les personnes apparaissent au final un même nombre de fois.

Cependant. A vue de nez. Tu n'as pas besoin de toutes les permutations => Joe, Pierre, Betty doit être équivalent à Betty, Pierre, Joe ou Betty, Joe, Pierre, etc... Correct ou pas ?

Les exemples que tu donnes ne permettent pas de se faire une idée.

• Est-ce que le nombre de places peux varier d'un jour sur l'autre ?
• Pour la même date peux-tu avoir par exemple 7 personnes pour 5 emplacements?
• Est-ce que par exemple tu peux avoir pour le lundi 5 personnes pour 5 places et pour le mardi 5 autres personnes pour les mêmes 5 places ?
• Est-ce qu'au final toutes les personnes doivent être placées ?

Voilà. C'est tout pour le moment.

Bonjour Badaze, merci pour ton commentaire.

Effectivement, j'ai voulu faire le plus concis possible, à tord
Pour répondre à tes questions :

• Une personne ne peut occuper que certaines positions, pas toutes (lié à certains attributs de la personne)
• Le nombre de place par jour est fixe (ouf !)
• Il est possible d'avoir plus de personne que de place pour une même date, et comme on souhaite que toutes ces personnes aient le même nombre d'attribution sur la semaine (ou avec le moins d'écart possible)
• Oui on peut avoir 5 personnes pour 5 places le lundi et la même chose le mardi
• Non, toutes les personnes ne doivent pas être placées, simplement que l'écart d'attribution soit le plus serrés possible pour que tout le monde soit content

En fait, je pense avoir trouvé en faisant un produit cartésien, sur mes tests ça fonctionne très bien et le résultat attendu est proche de ce qu'on a pu faire manuellement :

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
 
// Produit cartesien utilisé pour les propositions
    function cartesian($input) {
	    // filter out empty values
	    $input = array_filter($input);
 
	    $result = array(array());
 
	    foreach ($input as $key => $values) {
	        $append = array();
 
	        foreach($result as $product) {
	            foreach($values as $item) {
	                $product[$key] = $item;
	                $append[] = $product;
	            }
	        }
 
	        $result = $append;
	    }
 
	    return $result;
	}

Je te laisse répondre mais je pense que je vais pouvoir classer cette question "résolue". Mon problème à présent : à partir d'un certains nombre de personnes / disponibilités, l'execution du script explose la mémoire disponible.
Je n'ai pas des contraintes de temps, le script peut tourner pendant 3 jours pour trouver la réponse ça m'est égal, mais actuellement soit la mémoire sature et le script s'arrête, soit le serveur se fige si je pousse trop la memory_limit de mon php.ini.

C'est vrai que ce language n'est pas fait pour ce genre de "gros" calcul, mais si tu connais une solution qui me permette de faire tourner le script jusqu'à résolution peut importe le temps....ce serait top car je pense pas être en mesure de reprogrammer sous un autre language

[badaze]

Je crois qu'il y a beaucoup plus simple (attention je ne suis pas un matheux).

Imaginons que pour une journée tu aies 6 personnes pour 5 places. Cela te donne 720 permutations. Chaque personne apparaîtra autant de fois que les autres et dans ce cas elle apparaîtra 600 fois. C'est la que je dis que je dis que je ne suis pas un matheux. En faisant deux ou trois exemples sur ma TI 89 Titanium. J'arrive à calculer que 600 = 720 - (6-1)!.

Donc (si ma formule est juste), tu calcules le nombre de permutations auquel tu retranches la factorielle du nombre de personnes moins un. Si elle est fausse je pense que c'est néanmoins dans ce sens qu'il faut aller.

Après il y a le problème des places "attribuées" ... et je te le laisse (je pense que tu peux tout de même utiliser des formules mathématiques - je me souviens que je faisais ça à l'école mais c'est loin).

Si lundi tu as 'seb','pierre','jean','michel','jules' et 'patrice' à caser dans 5 places chacun aura un score de 600. ( nPr(6,5) - (6-1)! )
Si mardi tu as 'seb','pierre','jean','michel','jules' et 'paul' à caser dans 4 places chacun aura un score de 240. ( nPr(6,4) - (6-1)! )

etc... Peut-être faudrait il aussi considérer les combinaisons si tu n'as pas de notion d'ordre.

[Adesfire]

En fait, je suis une vraie chèvre en math

Mais comme quand on a pas de tête on a des jambes, quand on est nul en math on a de la ram !
C'est donc armé de 30 Gigas de ram qui j'ai pu résoudre mon problème, en environ 10 minutes !


PS : l'ordre à bien une importance !!

Pour le moment ça me suffit amplement, merci encore Badaze !