Peer-Review demandée de ma Génération par récursivité de toutes les combinaisons possibles de quatre lettres

a marqué ce sujet comme résolu.

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 le return à 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_unique alors 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 !

+0 -0

Ça fait des lustres que je ne fais plus de PHP (mais parait que c’est comme le vélo ?) Ceci dit, je ne vois en effet pas pourquoi tu as besoin du global… Il faut que tu initialises simplement ta variable (il me semble que ce n’est pas obligatoire mais c’est mon habitude) localement…

	$outputs = [];

…et non globalement !

//$outputs = [];

Ensuite, ta fonction doit toujours renvoyer cette variable en sortie

			return $outputs;

Bon, ceci dit, je n’ai pas testé et je crois voir le souci : ma proposition naïve va réinitialiser ta déclaration à chaque appel re-entrant (d’où la variable globale…) Du coup, ce que je ferait c’est de retirer l’initialisation locale

	//$outputs = [];

…puis je passerai cela plutôt en paramètre

function generateCombinations(array $data, array $buildingSubSet, array $buildingResults, int $currentLevel, array $outputs=[])

(par contre, je ne sais plus passage par adresse ou par valeur ?) pour le passer dans les rappels

		generateCombinations($data, $buildingSubSet, $buildingResults, $currentLevel + 1, $outputs);

Je ferai le test dès que je serai de retour sur mon poste.

+0 -0

Salut,

Avant même d’écrire la moindre ligne de code, le plus important est toujours de formuler le problème à résoudre d’une façon claire. Là tu dis que :

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] ].

Ben déjà, c’est pas super clair comme formulation. En maths, les combinaisons sont les façons non-ordonnées de piocher nn éléments distincts dans un ensemble de taille mm. Ça colle déjà pas parce que tu as des répétitions (avec 4 fois 'd'), et que tu as des tableaux de différentes tailles. Si on regarde la sortie de ton programme, tu as aussi des ordres différents qui sont considérés différents, comme ['a', 'b'] et ['b', 'a']. Donc en termes mathématiques, il semblerait que tu cherches tous les uplets (tuples en anglais) de taille 11 à mm (pourquoi exclure 0?) qui puissent être construits à partir des mm éléments fournis. Bon, ça pour l’instant c’est plus de la terminologie qu’autre chose, ce qui compte surtout est de bien définir l’objectif de manière non-ambiguë. Là par exemple il a fallu que j’aille voir la sortie de ton programme pour savoir si l’ordre est important et si tu veux le 0-uplet ou non. C’est un problème qui ne devrait pas se poser.

En admettant que j’ai bien compris le problème, comme tu veux résoudre ça par récursion il faut le reformuler d’une façon récursive. Avant de faire ça, on peut déjà le découper en deux parties plus simples. Tu veux l’ensemble de tous les uplets de taille 11 à mm qu’on peut construire à partir d’un ensemble de taille mm. Ben on pourrait déjà essayer de construire tous les nn-uplets à partir d’un ensemble de taille mm, puis après il suffira de regrouper tout ce petit monde.

L’ensemble des nn-uplets à partir d’un ensemble SS de taille mm peut se définir d’une manière récursive assez simplement :

  • le 0-uplet est trivialement () ;
  • les nn-uplets peuvent être construits à partir des (n1)(n-1)-uplets en ajoutant à tous chaque élément de SS.

Par exemple en Python, ça donne :

def tuples_in(elems: set, size: int) -> list[tuple]:
    """All size-tuples generated from elems."""
    if size == 0:
        return [()]
    smaller_tuples = tuples_in(elems, size - 1)
    result: list[tuple] = []
    for smaller in smaller_tuples:
        result.extend(smaller + (elem,) for elem in elems)
    return result

L’ensemble que tu cherches devient alors simplement

def solution(elems: set) -> list[tuple]:
    result = []
    for size in range(len(elems)):
        result.extend(tuples_in(elems, size + 1))
    return result

On pourrait aussi facilement modifier tuples_in pour cumuler les nn-uplets avec les n1n-1-uplets, et ainsi s’approcher très près de se qu’on veut (et faire moins de calculs intermédiaires). C’est un tout petit peu moins élégant à écrire par contre parce que tu as besoin de virer manuellement le 0-uplet qui ne t’intéresse pas dans le résultat final (comme il sera en tête de la liste, c’est pas la mer à boire non plus cela-dit).

Bref, tu l’auras compris, la clé est surtout de trouver une formulation récursive de ce qu’on cherche, et le code s’écrit ensuite quasiment tout seul. C’est pour ça qu’en pratique, on n’utilise la récursion que lorsque la formulation récursive du problème est déjà naturelle, et qu’on sait qu’on ne va pas traiter des problèmes qui vont se heurter à des limites de profondeur de récursion. Par exemple ça marche très bien pour écrire une solution exhaustive au problème du sac à dos (en s’en tenant à des petits nombres d’éléments bien sûr).

EDIT: un truc sur lequel je pense qu’il est bon d’enfoncer le clou. Quand on en est à avoir la moitié des arguments de la fonction récursive qui sont juste des helpers pour la récursion (ou à se reposer sur des variables globales), c’est qu’on n’a pas la bonne formulation du problème (ou qu’on est en train d’utiliser la récursion pour un problème qui ne s’y prête pas). Ce genre de code est difficile à lire, comprendre, et débugger. Quand on bricole un truc récursif en ajoutant des arguments au besoin en cours de route, il est grand temps d’arrêter les frais et mieux réfléchir au problème.

+2 -0

Bon, je reviens pas sur ce qu’à dit déjà adri1 à propos du problème mal posé.

Mais je voudrais insisté sur le fait que ce n’est pas particulièrement un problème de récursivité.
La récursivité est puissante lorsqu’elle permet de faire autre chose qu’une simple boucle for.

def solution(alpha: set, sequence_size: int) -> list[tuple]:
    baseSeq = [(a,) for a in alpha]
    totalSeq = baseSeq

    for _ in range(1, sequence_size):
        nextBase = []
        for e in baseSeq:
            nextBase.extend([(a,) + e for a in alpha])
        totalSeq.extend(nextBase)
        baseSeq = nextBase

    return totalSeq

Si tu souhaites t’entraîner à la récursivité je t’invite utiliser les exercices de France-IOI (le site semble inaccessible pour l’instant).

+0 -0

Cela dit, quitte à implémenter ça de façon impérative, autant utiliser le fait que générer les nn-uplets revient juste à compter en base mm jusqu’à mn1m^n-1 en utilisant les éléments du set de taille mm comme chiffres… :-°

+1 -0

Cela dit, quitte à implémenter ça de façon impérative, autant utiliser le fait que générer les nn-uplets revient juste à compter en base mm jusqu’à mn1m^n-1 en utilisant les éléments du set de taille mm comme chiffres… :-°

adri1

?

C’est exactement la même chose. Vu qu’il n’y a pas d’intérêt à effectivement faire une conversion de base 2 vers la base m à part si l’on ne veut qu’une partie des tuples possibles.
Tu me reproches donc d’utiliser [(a,) + e for a in alpha] plutôt que [e + (a,) for a in alpha] ? 🙄

+0 -0

Je ne comprends pas du tout le lien entre ton message et le mien (ni ce que tu essaies de dire tout court, d’ailleurs). C’est le fait de construire ce genre d’ensembles explicitement que je critique. Si on sort du cadre de s’en servir pour s’entraîner à la récursion, on a autant d’utiliser la description exacte disponible pour générer les éléments.

Par exemple, si je devais implémenter une solution au problème, je partirai sûrement d’un truc du genre :

@dataclass(frozen=True)
class NTuples:
    """The `size`-tuples generated from `elems`."""
    elems: Sequence
    size: int

    def __getitem__(self, i: int) -> tuple:
        assert i >= 0
        # i written in base `len(elems)`, with exactly `size` digits
        # (overflow results in IndexError)
        digits = list(0 for _ in range(self.size))
        idig = 0
        while i > 0:
            i, digits[idig] = divmod(i, len(self.elems))
            idig += 1
        return tuple(self.elems[idx] for idx in digits)

et NTuples(range(2), 5) par exemple devient juste un compteur binaire fancy à 5 chiffres. Il manque plein de méthodes et wrappeurs utiles qu’on peut imaginer pour produire la solution de diverses façons (tout en mémoire vs générateur par exemple), mais le cœur du problème est réglé. NTuples("abcd", 4) nous donne accès à tous les tuples de taille quatre dans la solution. Python offrant __iter__ si on implémente __getitem__, on peut même déjà appeler list(NTuples("abcd", 4)). Donc si on a vraiment besoin de la liste complète en mémoire comme décrite dans l’OP, c’est trivial à obtenir en composant avec NTuples. Aucune idée de ce qu’offre PHP en terme d’itérateurs, mais si je devais le faire, je partirai aussi d’une fonction qui est capable de prendre le set, la taille de tuple, et un index pour générer un seul élément directement.

+0 -0

C’est le fait de construire ce genre d’ensembles explicitement que je critique.

Désolé mais ce n’est pas ce qui parait évident depuis ton message où tu ne fais que décrire une manière de voir le problème différemment.

Je suis d’accord avec toi dans le fond « à part si l’on ne veut qu’une partie des tuples possibles. » mais ce n’est plus le but de l’exercice et utiliser cette méthode pour répondre à l’exercice, c’est effectivement perdre du temps en transcription des valeurs en chiffres.

+0 -0

Imaginons que la spécification du problème, c’est

  • la fonction prend en paramètre un ensemble de trucs
  • elle retourne l’ensemble des parties.

Une façon simple d’entamer une solution récursive, c’est de partir d’un exemple.

Si on veut l’ensemble des parties de {11, 22, 33, 44}, comment on fait ?

  • ben, comme on a dit récursivement, on calcule l’ensemble des parties sur 3 éléments (3 = 4 - 1), en laissant de côté un élément (par exemple 11)
  • ça nous donne 8 parties de {22, 33, 44} qui sont aussi (le monde est bien fait) des parties de {11, 22, 33, 44} .
  • et à partir de ces 8, ça nous en fait 16 en leur ajoutant l’élément qu’on avait enlevé (11), ou pas.
  • ça nous fait les parties sur 4 éléments. Hourra.

Revenons à PHP (snif) puisqu’il le faut.

Un test, ça pourrait être

$test = [11, 22, 33, 44];
var_dump(all_subsets($test));

La fonction all_subsets on l’appellera successivement avec [11, 22, 33, 44], [22, 33, 44], [33, 44] etc. Alors on va optimiser en évitant de copier des bouts de tableau : on va passer

  • le tableau initial
  • l’index de la première position à considérer

ça va commencer comme ça

function all_subsets($array, $start = 0) {
    if ($start == count($array)) {
        return [[]];                         // !!!
    }
    $first = $array[$start];
    $subs = all_subsets($array, $start+1);

Attention au piège : l’ensemble vide, il a une partie, le sous-ensemble vide. Donc un retourne un tableau contenant un tableau vide.

La variable $subs, ça va être les parties du tableau sans son premier élément (en commençant à l’index $start+1).

reste plus qu’à concocter le résultat, et le retourner

    $result = $subs;                 // les parties du sous-ensemble
    foreach($subs as $sub) {
        array_push($sub, $first);    // chaque partie, en y ajoutant le premier
        array_push($result, $sub);
    }
    return $result;
}
+0 -0

Au passage, l’idée de travailler sur la liste des sous-ensembles d’une partie de l’ensemble d’origine, ça donne une solution itérative simple

function all_subsets($array) {
    $subsets = [[]];
    foreach ($array as $element) {
        $previous = $subsets;
        foreach ($previous as $s) {
            array_push($s, $element);
            array_push($subsets, $s);
        }
    }
    return $subsets;
}

et de bon goût, qu’on peut aussi voir comme une dérécursivation de la précédente.

C’est basé sur un invariant (assertion) à l’entrée de la boucle : $subsets contient les parties du début d'$array, jusqu’à $element non compris.

Le corps de la boucle y ajoute les parties qui contiennent $element

Pour les parties non-vides (le sujet d’origine), c’est du même genre

function non_empty_subsets($array) {
    $subsets = [];
    foreach ($array as $element) {
        // invariant : $subsets contient les parties
        // du début d'$array, $element non compris
        $previous = $subsets;
        // on y ajoute le singleton        
        array_push($subsets, [$element]);

        // et les parties avec $element
        foreach ($previous as $s) {
            array_push($s, $element);
            array_push($subsets, $s);
        }
    }
    return $subsets;
}
+0 -0

@MichelBillaud : tout ça serait beaucoup plus intéressant si ce n’était pas hors-sujet (voire carrément à contre-courant du problème). L’OP ne veut pas générer l’ensemble des parties, mais l’ensemble des (1 à n)-uplets. La stratégie récursive de générer l’ensemble voulu pour le problème de taille n1n-1 puis le trafiquer pour revenir à l’ensemble de taille nn marche très bien pour l’ensemble des parties, mais se casse la gueule pour le problème posé. Je suspecte même que c’est l’approche dont est parti l’OP pour ensuite se retrouver avec une fonction qui utilise une variable globale et des paramètres helpers. Le nœud du problème ici est que la relation de récursion qui va bien est de générer l’ensemble des nn-uplets à partir de l’ensemble des (n1)(n-1)-uplets plutôt qu’une relation récursive sur l’ensemble solution directement.

La clé du problème, c’est d’identifier (outre ce qu’on veut faire) le truc sur lequel va porter la récursion. Ici il y a deux choses,

  • la taille de l’ensemble des items
  • la taille max des n-uplets

il se trouve, (mais ce n’est pas explicite dans la spécification du problème, qui est floue) que les valeurs sont les mêmes, ce qui induit en erreur. C’est pour ça que j’ai pris un exemple différent) :

  • pour montrer l'approche sur un exemple bien défini
  • pour ne pas cramer l’exercice !

mais si on y tient :

Essayer de faire directement le calcul de la liste des n-tuplets de taille t à partir de liste de taille t-1, c’est bien d’essayer, mais c’est pas commode.

C’est plus facile à faire sur une liste de listes de n-uplets, regroupés par taille.

[  [[1], [2], [3]],  
   [[1, 1], [1, 2], [1, 3], [2,1], ... [3,3]],  
   [[1, 1, 1], [1, 1, 2], .....    [3, 3, 3]]
] 

(qu’il n’y aura plus qu’à aplatir à la fin)

Pour aller un cran plus loin dans la récursion ou l’itération, il suffit de prendre la dernière sous-liste, et d’ajouter les divers trucs à la suite de chaque.

Code

Le programme suivant

<?php

function extend_all($array, $others) {
    return array_map(
        function($a) use ($others) { return array_merge($a, $others);},
        $array
    );
}

function singleton($x) {
    return [$x];
}
/*
  retourne un tableau contenant
  - les singletons
  - les doublets
  - les triplets
  - .... les n-uplets jusqu'à taille t
  d'éléments de $array
*/
function tuples_by_size($array, $t)
{
    if ($t == 1) {
        return [ array_map('singleton', $array) ];
    }

    $result = tuples_by_size($array, $t - 1); // n-uplets de taille < t

    // on construit les n-uplets de taille t
    $last = $result[count($result) - 1];      // n-uplets de taille t-1
    $tuples = [];
    foreach($array as $element) {
        $s = singleton($element);
        $tuples = array_merge($tuples, extend_all($last, $s));
    }

    // et on les ajoute
    array_push($result, $tuples);
    return $result;
}

function all_tuples($array) {
    $a = tuples_by_size($array, count($array));
    return array_reduce($a, 'array_merge', []);
}

print_r(all_tuples(['a', 'b', 'c', 'd']));
        

exécution

ça fournit une liste de 340 résultats

Array
(
    [0] => Array
        (
            [0] => a
        )

    [1] => Array
        (
            [0] => b
        )

    [2] => Array
        (
            [0] => c
        )

    [3] => Array
        (
            [0] => d
        )

    [4] => Array
        (
            [0] => a
            [1] => a
        )

...
   [338] => Array
        (
            [0] => c
            [1] => d
            [2] => d
            [3] => d
        )

    [339] => Array
        (
            [0] => d
            [1] => d
            [2] => d
            [3] => d
        )

)

ce qui tombe plutôt bien vu que 41+42+43+44=3404^1 + 4^2 + 4^3 + 4^4 = 340.

moralité

Le truc à calculer par récursion, à part dans les exemples jouets, c’est rare que ça soit le résultat final voulu. C’est plutôt un truc dont on peut extraire le résultat, par un petit calcul à la fin (la fonction all_tuples)

+3 -0

Une autre version de la fonction qui reprend le parcours récursif sur un tuple "de travail" alimenté dans l’ordre lexicographique de @Herbe, implémentée en tant que méthode de classe.

La liste des éléments et la liste des tuples générés sont des variables de la classe (des "propriétés" en php).

Dans cette version également la taille maximum des tuples est indépendante du nombre d’éléments possibles.

<?php
class Tuples
{
    public $elements;
    public $tuples;

    private function set_tuples($order, $tuple = [])
    {
        if ($order > 0) {
            foreach ($this->elements as $element) {
                $tuple[] = $element;
                $this->tuples[] = $tuple;
                $this->set_tuples($order - 1, $tuple);
                array_pop($tuple);
            }
        }
    }

    function __construct($elements, $order)
    {
        $this->elements = $elements;
        $this->tuples = [];
        $this->set_tuples($order);
    }
}

$t = new Tuples(['a', 'b', 'c', 'd'], 4);
print_r($t->tuples);
?>

EDIT - Mise en forme

+0 -0
Connectez-vous pour pouvoir poster un message.
Connexion

Pas encore membre ?

Créez un compte en une minute pour profiter pleinement de toutes les fonctionnalités de Zeste de Savoir. Ici, tout est gratuit et sans publicité.
Créer un compte