Énumérer les permutations d'un mot à lettres répétées

On trie d'abord les lettres. Deux lettres égales ne doivent alors être posées que dans l'ordre de leurs indices : on refuse la lettre $i$ si sa jumelle $i-1$ est encore libre.

(* Applique traiter à chaque permutation DISTINCTE des lettres de mot.
   Précondition : aucune (les lettres sont triées ici même) ; le test d'élagage
   ci-dessous serait faux sur des lettres non triées. *)
let permutations_distinctes mot traiter =
  let n = String.length mot in
  let lettres = Array.init n (fun i -> mot.[i]) in
  Array.sort compare lettres;                       (* le tri EST la précondition *)
  let utilise = Array.make n false in
  let sortie = Bytes.create n in
  let rec explorer k =
    if k = n then traiter (Bytes.to_string sortie)
    else
      for i = 0 to n - 1 do
        if not utilise.(i)
           (* la jumelle précédente doit avoir DÉJÀ été posée *)
           && not (i > 0 && lettres.(i) = lettres.(i-1) && not utilise.(i-1))
        then begin
          utilise.(i) <- true; Bytes.set sortie k lettres.(i);
          explorer (k + 1);
          utilise.(i) <- false
        end
      done
  in explorer 0

Mesuré : le nombre de feuilles atteintes tombe exactement au nombre de mots distincts.

On retrouve bien $\frac{6!}{3!3!}=20$ et $\frac{6!}{2!2!}=180$.

Pourquoi ce test est correct, et c'est le seul point délicat : parmi les $k!$ façons d'ordonner $k$ lettres identiques, le test n'en accepte qu'une — celle où leurs indices d'origine sont croissants. Il n'en refuse donc aucune classe entière, et n'en accepte aucune deux fois.

Pourquoi on n'utilise pas de table de hachage. Filtrer a posteriori avec une table (chapitre chap:hachage) donnerait le même résultat, mais aurait visité les $720$ feuilles de AAABBB pour n'en garder que $20$ : on paie l'exploration, puis le stockage. L'élagage, lui, ne descend jamais dans la branche redondante. Filtrer à l'arrivée n'est pas élaguer.