Probleme – Engendrer toutes les parties d'un ensemble

1. La fonction.

(* parties l renvoie la liste de toutes les sous-listes de l, l'ordre
   des elements etant conserve dans chacune.
   Precondition : aucune. Postcondition : le resultat a 2^|l| elements. *)
let rec parties = function
  | [] -> [[]]                       (* l'ensemble vide a UNE partie : lui-meme *)
  | x :: r ->
      let p = parties r in
      List.map (fun s -> x :: s) p @ p    (* avec x, puis sans x *)

Mesuré : parties [1;2;3] rend les huit listes [1;2;3], [1;2], [1;3], [1], [2;3], [2], [3], [].

Le cas de base est le piège de l'exercice. Écrire [] -> [] donnerait la liste vide de parties, et par propagation la fonction rendrait toujours []. L'ensemble vide a exactement une partie, l'ensemble vide : le cas de base est [[]], une liste contenant une liste vide.

2. Correction et compte. Par récurrence sur $|l|$. Pour $l$ vide, la seule partie est $\varnothing$. Pour $l=x::r$, toute partie de $l$ contient $x$ ou ne le contient pas ; celles qui ne le contiennent pas sont exactement les parties de $r$ ; celles qui le contiennent sont exactement les $x::s$ pour $s$ partie de $r$. La réunion est donc complète et sans doublon, et

$$|\mathcal{P}(l)|=2|\mathcal{P}(r)|=2\times 2^{|r|}=2^{|l|}.$$

Mesuré : $1,2,4,8,16$ parties pour $n=0\dots 4$, et $65536$ pour $n=16$.

3. La place et la pile. La somme des tailles des parties est

$$\sum _{k=0}^{n}k\left(\genfrac{}{}{0ex}{}{n}{k}\right)=n{2}^{n-1},$$

mesuré : $5120$ pour $n=10$ et $524288$ pour $n=16$, conformes. Le résultat occupe donc $\Theta (n{2}^n)$ maillons — mais le partage de queue en économise une partie, puisque @ p réutilise $p$ tel quel.

La profondeur de pile, elle, n'est que $\Theta (n)$ : un seul appel récursif par niveau, $n$ niveaux. Encore une fois, temps exponentiel et espace de pile linéaire.

4. Énumérer sans stocker. On passe une fonction à appliquer à chaque partie, et l'on construit la partie courante dans un accumulateur :

(* pour_chaque_partie f l applique f a chaque sous-liste de l.
   Espace : Theta(n) au lieu de Theta(n 2^n). *)
let pour_chaque_partie f l =
  let rec aux acc = function
    | [] -> f (List.rev acc)
    | x :: r -> aux (x :: acc) r; aux acc r
  in aux [] l

Vérifié : elle énumère bien $2^n$ parties, $1024$ pour $n=10$ et $65536$ pour $n=16$, dans le même ordre que la précédente. Le gain est massif : pour $n=30$, la première version demanderait $30\times 2^{29}$ maillons, soit plus de $16$ milliards de maillons, tandis que celle-ci se contente de $30$ cases de pile — le temps reste $\Theta (2^n)$, incompressible puisqu'il y a $2^n$ objets à produire.

C'est le schéma du retour sur trace, qui structurera l'exploration du chapitre chap:exploration : à chaque étape, un choix binaire ; on descend, on remonte, on essaie l'autre branche.