OCaml (option informatique) · Chapitre 11 · Application directe du cours

Les parties

Récursivité et retour sur trace · niveau 1 (application)

Énoncé

Écrire parties et vérifier qu'une liste de $n$ éléments produit $2^{n}$ parties.

Corrigé

let rec parties l =
  match l with
  | [] -> [[]]
  | x :: reste ->
      let sous = parties reste in
      sous @ List.map (fun s -> x :: s) sous

À chaque élément, on double le nombre de parties (celles sans x, et les mêmes avec x en tête). Partant de [[]] ( $1$ partie pour la liste vide), on obtient $2^{n}$ : parties [1; 2; 3] en a $8$ .

Exercices semblables

Les $n$ reines corrigé
Reconstruire le sous-ensemble corrigé
Sortie d'un labyrinthe corrigé
Nombre de coups de Hanoï corrigé
Sous-ensemble de somme donnée corrigé

Le cours du chapitre · Tous les exercices du chapitre