Bonjour tout le monde,
Cela fait plusieurs années que je n’ai pas eu besoin d’utiliser de récursivité pour construire l’ensemble de toutes les combinaisons (ou permutations, je ne sais plus comment on doit appeler ça…) d’un ensemble de termes. Ni dans mes projets persos, ni pros. Du coup à force de ne plus avoir besoin d’y penser, je me rends compte aujourd’hui que j’éprouve quelques difficultés avec ce concept (je ne parle pas du concept de récursivité, mais bien de la génération de toutes les combinaisons possible d’un tableau d’éléments - qui est il me semble le cas le plus compliqué d’implémentation de la récursivité car il faut jongler avec les retours empilés, les paramètres, le passage par référence, la portée global du moins en PHP, etc.).
Objectif
On se donne un tableau de termes : ['a', 'b', 'c', 'd'] et l’on souhaite obtenir l’ensemble des combinaisons possibles, donc : [ [a], [a,b], [a,b,c], [a, b, c, d], ..., [d, d, d, d] ].
Mon code (PHP)
Remise en question
Mon code fonctionne mais c’est une solution toute pourrie, très moche. En effet :
-
J’ai dû me baser sur
global, or c’est à éviter. J’ai bien essayé de faire un truc en exploitant lereturnà la place, en pensant que le dernier niveau de récursivité peut retourner son travail à son niveau-parent, et si tous font ça, alors que le tout premier niveau est censé récupérer le travail de tous ses niveaux-enfants directs ET tous ses niveaux-enfants indirects. Mais je n’ai pas réussi… -
J’ai dû utiliser un
array_uniquealors que je suis sûr qu’on aurait pu s’en passer, si j’avais utilisé une autre approche !
Sources
Explications : il s’agit d’itérer sur les quatre termes à chaque niveau de récursivité. Pour chaque itération, on vient tout simplement ajouter le terme itéré au tableau en cours de construction. Donc de niveau en niveau, on obtient un tableau qui comporte de plus en plus d’éléments (jusqu’à atteindre la taille de 4 vu qu’on n’a que quatre termes), et comme on change d’élément à chaque itération de chaque niveau de récursivité, bein on obtient bien toutes les combinaisons possibles dans le tout dernier niveau de récursivité. C’est pourquoi, quand on est dans le dernier niveau de récursivité, je range toutes ces combinaisons trouvées dans un tableau contenant les résultats finaux (c’est celui avec la portée global). Par contre y a des doublons (ce sont toutes les combinaisons des niveaux avant le dernier niveau). D’où le array_unique).
<?php
$outputs = [];
function generateCombinations(array $data, array $buildingSubSet, array $buildingResults, int $currentLevel)
{
global $outputs;
if ($currentLevel === count($data)) {
$outputs = [
...$outputs,
...$buildingResults,
];
return;
}
for ($i = 0; $i < count($data); $i++) {
$buildingSubSet[] = $data[$i];
$buildingResults[] = $buildingSubSet;
generateCombinations($data, $buildingSubSet, $buildingResults, $currentLevel + 1);
array_pop($buildingSubSet);
}
}
generateCombinations(['a', 'b', 'c', 'd'], [], [], 0);
$finalOutputs = array_unique($outputs, SORT_REGULAR);
echo count($finalOutputs) . PHP_EOL;
print_r($finalOutputs);
Question
Pourriez-vous, s’il vous plaît, me donner une idée pour faire ça plus proprement ? Notamment en me basant sur la notion de retour d’une fonction, afin de ne pas avoir besoin du global et, si possible, en évitant d’utiliser array_unique ? A noter que si vous donnez un code tout fait, je pourrai le comprendre et ça reviendra au même (attention : ceci n’est ni un projet professionnel, ni un projet personnel, ni un projet universitaire, je cherche uniquement à me rappeler de comment je m’y prenais dans le passé).
Merci beaucoup !
Bonne journée, bon weekend, bonne semaine !
