Discussion :

[Adesfire]

Bonjour,
je butte sur le problème suivant :

Je dispose de deux tableaux :

• Le premier représente des emplacements
• Le second des personnes

L'objectif est, dans un premier temps, de lister toutes les possibilités de distribution des personnes sur ces places.

Au niveau des contraintes actuelles :

• Il peut y avoir plus de personnes que d'emplacements
• Il peut y avoir également moins de personnes que d'emplacements
• Les places vides dans le cas ou il y a moins de personnes, sont également considérées (et donc, on doit pouvoir afficher toutes les combinaisons possibles avec un emplacement libre aux différents endroits)

Plus conctétement, avec ces deux tableaux :

Code :

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

1
2
$personnes = array('seb', 'pierre', 'jean');
$places    = array('UNE', 'DEUX', 'TROIS', 'QUATRE', 'CINQ');

J'aimerais obtenir des résultats de ce type :

Code :

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

1
2
3
4
5
6
7
$combinaisons = array(
    'UNE' => 'seb',
    'DEUX' => '',
    'TROIS' => 'jean',
    'QUATRE' => 'pierre',
    'CINQ' => ''
);

puis

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
$combinaisons = array(
    'UNE' => '',
    'DEUX' => 'seb',
    'TROIS' => 'jean',
    'QUATRE' => 'pierre',
    'CINQ' => ''
);
 
// et
 
$combinaisons = array(
    'UNE' => 'seb',
    'DEUX' => 'pierre',
    'TROIS' => 'jean',
    'QUATRE' => '',
    'CINQ' => ''
)

etc. de sorte à avoir toutes les combinaisons possibles !

J'ai bien entendu fait le tour des algo de combinaisons sur Google, mais ils s'avérent trop différent de mon besoin pour que je puisse les adapter, d'autant plus qu'une fois ce soucis résolut, j'ajouterais des difficultés (selon les caractéristiques des personnes, toutes les places ne sont pas permises).

Bref, si un expert en math ou algo passe par ici, je serais heureux d'apprendre à déméler ce problème

Merci !

[badaze]

Bonjour,

Essaie ça.

Code php :

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
 
<?php
function permutation(&$array,$array2,$limite,$niveau,$aa,&$retour,&$arrCtl,$str="") {
 if ($niveau < ($limite-1)) {
  for($l=0;$l<count($array);$l++) {
   $ll = $array[$l];
   if (!in_array($ll,$aa)) {
    $aa[$niveau] = $ll;
    $niveau2     = $niveau;
    $sep         = $niveau == 0 ? '' : '|';
    permutation($array,$array2,$limite,++$niveau2,$aa,$retour,$arrCtl,$str.$sep.$ll);
   }
   unset($aa[$niveau]);     
  } 
    } else {
  for($k=0;$k<count($array);$k++) {
   $kk = $array[$k];
   if (!in_array($kk,$aa)) {
    $aaa      = $str.'|'.$kk;
    $aaa      = preg_replace("/A___\d+/"," ",$aaa);
    $elem     = explode('|',$aaa);
    if (!in_array($aaa,$arrCtl)) {
     $arrCtl[] = $aaa;
     $retour[] = array_combine($array2,$elem);
    }
   }
  }
 }
}
$personnes = array('seb','pierre','jean','michel');
$places    = array('UNE','DEUX','TROIS','QUATRE','CINQ');
if (count($personnes) < count($places)) {
 //---- plus de places que de personnes
 $difference = count($places) - count($personnes);
 for ($i=1;$i<=$difference;$i++) {
  $personnes[] = "A___$i";
 }  
}
 
$aa     = array();
$retour = array();
$arrCtl = array();
permutation($personnes,$places,count($places),0,$aa,$retour,$arrCtl);
var_dump($retour);

[Adesfire]

Bonjour badaze,
et bien il semble que ta proposition corresponde parfaitement.
Je vais la creuser un peu pour véfifier que tout est ok, mais je suis impressionné !

SI tu as l'occasion de m'indiquer la façon dont tu l'as "imaginé" car le code est bien dense.

Quoi qu'il en soit merci beaucoup !

[badaze]

Et encore. Il est plus long car il a fallu intégrer le tableau des places et ne pas prendre en compte les doublons dus aux places vides.

En voyant ton message j'ai recherché sur google mais je n'ai trouvé que des algorithmes qui sortaient toutes les permutations sur tous les éléments d'une liste et pas toutes les permutations sur un nombre limité d'éléments.
Puis je me suis dit que ça ferait un bon exercice car il y avait longtemps que je n'avais pas fait d'algo récursif.
J'ai pas mal galéré (manque d'habitude dans la pensée récursive) mais j'ai trouvé la solution juste avant de m'endormir !!! Comme quoi la nuit porte conseil.

C'est sûrement optimisable et améliorable.

Voici l'algo original.

Code php :

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
 
function _permutations(&$array,$limite,$niveau,$aa,&$permutations,$str="") {
 if ($niveau < ($limite-1)) {
  for($l=0;$l<count($array);$l++) {
   $ll = $array[$l];
   if (!in_array($ll,$aa)) {
    $aa[$niveau] = $ll;
    $niveau2     = $niveau;
    $sep         = $niveau == 0 ? '' : '|';    
    _permutations($array,$limite,++$niveau2,$aa,$permutations,$str.$sep.$ll);
   }
   unset($aa[$niveau]);     
  } 
    } else {
  for($k=0;$k<count($array);$k++) {
   $kk = $array[$k];
   if (!in_array($kk,$aa)) {
    $aaa            = $str.'|'.$kk;
    $permutations[] = explode('|',$aaa);    
   }
  }
 }
}
 
 
function permutations($array,$nbreElements=0) {
 $profondeur   = count($array);
 if ($nbreElements > $profondeur || $nbreElements == 0) {
  $nbreElements = $profondeur;
 }
 $permutations = array(); 
 $aa           = array();
 _permutations($array,$nbreElements,0,$aa,$permutations);
 return $permutations;
}
$liste        = array(1,2,3,4,5);
var_dump(permutations($liste));

[Adesfire]

Et bien merci pour le temps passé sur ce problème. Effectivement, sur Google je ne trouvais pas exactement de solution à ce problème et je n'arrivais surtout pas à comprendre par quel bout prendre le problème pour m'assurer de passer toutes les solutions en revue.

Après avoir testé hier après-midi le code selectionné, il semble qu'il corresponde parfaitement à la demande !

A prèsent je vais implémenter un autre niveau de complexité, pour la petite histoire (je vais tenter de me débrouiller, ceci n'est pas une question) je vais devoir :

• Prendre en compte que certaines personnes ne sont élligibles qu'à certaines places (une ou plusieurs voir toutes)
• Que certaines places doivent être occupées en priorité (et donc par exemple, retirer les répartitions ou ces places ne le sont pas)
• Faire en sorte de selectionner la répartition ou le plus de personnes sont placés.

Le code ainsi produit me permettra de trouver les meilleurs solutions pour une "date" donnée (liste des possibilités avec les bonnes personnes aux bonnes places). Comme le problème final s'étale sur plusieurs dates, il me faudra trouver ensuite, sur 7 jours (et donc sept fois l'algo ci-dessus à différentes dates avec pas toujours les mêmes personnes disponibles) quels sont les meilleures répartitions afin que chacun puisse est positionné sur la semaine, sur un nombre de places équitable en fonction de leur élligibilité

Merci encore badaze !