Probleme – Les mots bien parenthésés, et pourquoi ils sont si peu nombreux

1. Les deux versions.

(* FORCE BRUTE : on écrit les 2^(2n) mots, et l'on teste à la fin.
   Renvoie le nombre de mots de Dyck. Précondition : n >= 0. *)
let dyck_brute n =
  let mot = Bytes.create (2 * n) and bons = ref 0 in
  let est_bon () =
    let s = ref 0 and ok = ref true in
    Bytes.iter (fun c ->
      s := !s + (if c = '(' then 1 else -1); if !s < 0 then ok := false) mot;
    !ok && !s = 0 in
  let rec brute k =
    if k = 2*n then (if est_bon () then incr bons)
    else begin
      Bytes.set mot k '('; brute (k + 1);
      Bytes.set mot k ')'; brute (k + 1) end
  in brute 0; !bons

(* RETOUR SUR TRACE : on refuse d'écrire ce qui est déjà perdu.
   ouvertes = nombre d'ouvrantes posées ; k - ouvertes = nombre de fermantes. *)
let dyck n traiter =
  let mot = Bytes.create (2 * n) in
  let rec explorer k ouvertes =
    if k = 2*n then traiter (Bytes.to_string mot)
    else begin
      if ouvertes < n then begin                  (* reste-t-il des ouvrantes ? *)
        Bytes.set mot k '('; explorer (k + 1) (ouvertes + 1) end;
      if k - ouvertes < ouvertes then begin       (* y a-t-il de quoi fermer ? *)
        Bytes.set mot k ')'; explorer (k + 1) ouvertes end
    end
  in explorer 0 0

2. La preuve que l'élagage ne perd rien. Un mot de Dyck vérifie, en tout préfixe, $\mathtt{fermantes}\le \mathtt{ouvertes}$ et $\mathtt{ouvertes}\le n$. Ces deux conditions sont exactement les deux tests. Il faut voir qu'elles sont héréditaires : si un préfixe les viole, aucun prolongement ne peut être un mot de Dyck, puisque les compteurs ne décroissent jamais. Élaguer sur une condition héréditaire ne supprime que des branches sans solution. Réciproquement, tout mot de Dyck a tous ses préfixes conformes, donc survit à l'élagage. Les deux versions énumèrent le même ensemble.

C'est le critère général : un test d'acceptabilité est correct s'il est nécessaire pour toute solution complète et héréditaire le long des branches. Un test seulement nécessaire à la fin — comme est_bon — n'élague rien.

3. La mesure.

Pour $n=3$, les cinq mots sont ((())) (()()) (())() ()(()) ()()().

La colonne des solutions est la suite $1,2,5,14,42,132,429,1430$ : ce sont les nombres de Catalan, $C_n=\frac{1}{n+1}\left(\genfrac{}{}{0ex}{}{2n}{n}\right)$. Ils ont été retrouvés indépendamment par la récurrence $C_n={\sum }_{j=0}^{n-1}{C}_j{C}_{n-1-j}$, qui traduit la décomposition d'un mot de Dyck en $(w_1)w_2$.

Ce que ce problème illustre. $C_n\sim 4^n/(n^{3/2}\sqrt{\pi })$ : les mots de Dyck sont exponentiellement nombreux, mais exponentiellement moins que les $2^{2n}=4^n$ mots quelconques — d'un facteur $n^{3/2}$ seulement. C'est pourquoi le rapport de la dernière colonne croît si lentement : l'élagage ne peut pas faire mieux que le rapport entre le nombre de solutions et le nombre de candidats. Ici ce rapport est polynomial, et l'exploration reste exponentielle. Là où l'élagage est spectaculaire — les $n$ reines, le sudoku —, c'est que les solutions sont exponentiellement rares.

Ces mêmes mots sont ceux qu'engendre la grammaire $S\to \epsilon \mid (S)S$ du chapitre chap:grammaires, et ce sont eux qu'un analyseur syntaxique reconnaît avec une pile (chapitre chap:sequentielles) — en temps linéaire, sans rien énumérer du tout.