Permutations

Exercice · OCaml (option informatique), chapitre 11 — Récursivité et retour sur trace

Énoncé

Écrire permutations (à l'aide de insere_partout et aplatis) et compter celles de [1; 2; 3].

Corrigé

let rec insere_partout x l =
  match l with
  | [] -> [[x]]
  | t :: reste ->
      (x :: l) :: List.map (fun p -> t :: p) (insere_partout x reste)

let rec permutations l =
  match l with
  | [] -> [[]]
  | x :: reste ->
      aplatis (List.map (insere_partout x) (permutations reste))

permutations [1;2;3] en compte $3! = 6$ . Pour chaque permutation du reste, on glisse x aux k+1 positions possibles, d'où la multiplication par la longueur croissante.

Les autres exercices de ce chapitre Le cours du chapitre

Un blocage sur cet exercice ? Le tuteur d'Adloun guide par questions, sans donner la réponse.