Discussion :

[obwil]

Bonjour à tous,

Je travaille sur un algorithme qui me permet de générer toutes les distributions de valeurs possibles pour une combinaison, en fonction du nombre de valeurs et de la longueur de la combinaison.

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
/**
 * @param int $nb_tiroirs     Le nombre de tiroirs qu'il reste à placer entre les chaussettes.
 * @param int $nb_chaussettes Le nombre de chaussettes qui ne sont pas encore dans un tiroir.
 * @param array $tiroirs      Les nombres de chaussettes dans chacun des tiroirs déjà placés.
 * @return                    Les combinaisons possibles.
 */
function create_combinaisons($nb_tiroirs, $nb_chaussettes, $tiroirs = array()) {
  if ($nb_tiroirs == 1) {
    $tiroirs[] = $nb_chaussettes;
    return array($tiroirs);
  }
 
  $combinaisons = array();
 
  // $tiroir est le nombre de chaussettes dans le tiroir suivant
  for ($tiroir = 0; $tiroir <= $nb_chaussettes; $tiroir++) {
    $combinaisons = array_merge($combinaisons, create_combinaisons(
      $nb_tiroirs - 1,
      $nb_chaussettes - $tiroir,
      array_merge($tiroirs, array($tiroir))));
  }
 
  return $combinaisons;
}
 
// Utilisation pour 3 entrées parmi 5 valeurs
$combinaisons = create_combinaisons(5, 3);
 
// Affichage
foreach ($combinaisons as $combinaison) {
  var_dump($combinaison);
}

Cette fonction donne toutes les distributions possibles, pour n valeurs possibles et une combinaison de longueur x.

Par exemple :

Code :

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

1
2
3
4
5
6
7
8
9
10
11
12
13
distributions_possibles(3,3);
 
// Output :
003
012
021
030
102
111
120
201
210
300

Aujourd'hui je cherche à générer toutes les distributions possibles à partir d'une distribution et du nombre de valeurs en commun avec elle.

Par exemple :

- 012 et 2 valeurs donnera les solutions suivantes : 011, 002

- 0211 et 2 valeurs donnera : 0110, 0200, 0011, 0101

- 03110 et 3 valeurs donnera : 03000, 01110, 02100, 02010

- 03110 et 2 valeurs donnera : 02000, 01100, 00110, 01010

Ne maitrisant pas bien la récursivité de ma fonction (j'ai été aidé), je n'arrive pas à l'adapter pour obtenir cette nouvelle génération.

Si vous avez des pistes je suis preneur.

[obwil]

J'ai trouvé une solution mais qui n'est pas la plus performante, car elle crée beaucoup de solutions en trop qu'il faut supprimer par la suite.
La voici :

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
 
function distributions_possibles($n_valeurs, $x_entrees, $combi_presences = array()) {
    if ($n_valeurs == 1) {
        $combi_presences[] = $x_entrees;
        return array($combi_presences);
    }
 
    $combinaisons = array();
 
    // on fait appel à une fonction récursive pour générer les distributions
    for ($y = 0; $y <= $x_entrees; $y++) {
        $combinaisons = array_merge($combinaisons, distributions_possibles(
            $n_valeurs - 1,
            $x_entrees - $y,
            array_merge($combi_presences, array($y))));
    }
    return $combinaisons;
}
 
function check_possibilites($distribution, $similitude){
    $all_distri = distributions_possibles(count($distribution), $similitude);
    $possibilites = [];
    foreach($all_distri as $key => $distri){
        $verif = true;
        for($x = 0; $x < count($distri); $x++){
            if($distri[$x] > $distribution[$x]){
                $verif = false;
            }
        }
        if($verif){
            $possibilites[] = $distri;
        }
    }
    return $possibilites;
}