Aller au contenu

Mots de Dyck⚓︎

On cherche dans cet exercice à générer l'ensemble des mots de Dyck de taille \(n\).

Un mot de Dyck de longueur \(n\) est une expression bien parenthésée comptant \(n\) paires de parenthèses.

Par exemple, (())() est un mot de Dyck de longueur \(3\). ()) n'est pas un mot de Dyck car il y a une parenthèse fermante de trop.

Définition précise

Un mot de Dyck (unilatère) de taille \(n\) compte exactement \(n\) parenthèses ouvrantes '(' et exactement \(n\) parenthèses fermantes ')'.

De plus, à chaque endroit de la chaîne, le nombre de parenthèses ouvrantes déjà rencontrées est toujours supérieur ou égal à celui de parenthèses fermantes.

Il est possible de générer les mots de Dyck de taille \(n\) en utilisant une pile :

  • on empile initialement le mot vide ;
  • tant que la pile est non vide :
    • on dépile un mot ;
    • si ce mot est de la longueur souhaitée, on l'ajoute à la liste de mots de Dyck cherchés ;
    • sinon s'il est possible de lui ajouter une parenthèse ouvrante, on l'ajoute et l'on empile le nouveau mot ;
    • enfin s'il est possible de lui ajouter une parenthèse fermante, on l'ajoute et l'on empile le nouveau mot.

Ce procédé est illustré ci-dessous dans le cas de la construction de mot de taille \(n=3\).

graph LR
    R{ } --> N1{"("}
    N1 --> N2{"(("}
    N1 --> N3{"()"}
    N2 --> N4{"((("}
    N2 --> N5{"(()"}
    N3 --> N6{"()("}
    N4 --> N7{"((()"}
    N5 --> N8{"(()("}
    N5 --> N9{"(())"}
    N6 --> N10{"()(("}
    N6 --> N11{"()()"}
    N7 --> N12{"((())"}
    N8 --> N13{"(()()"}
    N9 --> N14{"(())("}
    N10 --> N15{"()(()"}
    N11 --> N16{"()()("}
    N12 --> N17{"((()))"}
    N13 --> N18{"(()())"}
    N14 --> N19{"(())()"}
    N15 --> N20{"()(())"}
    N16 --> N21{"()()()"}

Écrire la fonction mots_dyck prenant en argument un entier n et renvoyant la liste des mots de Dyck de taille n. Ces mots comptent donc n paires de parenthèses.

Il est inutile de trier la liste des résultats.

Exemples

🐍 Console Python
>>> mots_dyck(0)
['']
>>> mots_dyck(1)
['()']
>>> mots_dyck(2)
['(())', '()()']
>>> mots_dyck(3)
['((()))', '(()())', '(())()', '()(())', '()()()']
# Testsbksl-nlassert motspy-unddyck(0) == [""]bksl-nlassert motspy-unddyck(1) == ["()"]bksl-nlassert sorted(motspy-unddyck(2)) == ["(())", "()()"]bksl-nlassert sorted(motspy-unddyck(3)) == ["((()))", "(()())", "(())()", "()(())", "()()()"]bksl-nlbksl-nl# Tests supplémentairesbksl-nldef py-undpy-undmotspy-unddyck(n):bksl-nl longueur = 2 py-str nbksl-nl mots = []bksl-nl pile = [("", 0, 0)]bksl-nl while len(pile) > 0:bksl-nl mot, ouvrantes, fermantes = pile.pop()bksl-nl if len(mot) == longueur:bksl-nl mots.append(mot)bksl-nl else:bksl-nl if ouvrantes < n:bksl-nl pile.append((mot + "(", ouvrantes + 1, fermantes))bksl-nl if ouvrantes - fermantes > 0:bksl-nl pile.append((mot + ")", ouvrantes, fermantes + 1))bksl-nl return motsbksl-nlbksl-nlbksl-nlfor n in range(4, 11):bksl-nl attendus = sorted(py-undpy-undmotspy-unddyck(n))bksl-nl reponse = sorted(motspy-unddyck(n))bksl-nl assert reponse == attendus, f"Erreur avec {n=}"bksl-nlbksl-nl ∞/∞

def motspy-unddyck(n):bksl-nl ...bksl-nlbksl-nlbksl-nl# Testsbksl-nlassert motspy-unddyck(0) == [""]bksl-nlassert motspy-unddyck(1) == ["()"]bksl-nlassert sorted(motspy-unddyck(2)) == ["(())", "()()"]bksl-nlassert sorted(motspy-unddyck(3)) == ["((()))", "(()())", "(())()", "()(())", "()()()"]bksl-nlbksl-nldef motspy-unddyck(n):bksl-nl longueur = 2 py-str nbksl-nl mots = []bksl-nl pile = [("", 0, 0)]bksl-nl while len(pile) > 0:bksl-nl mot, ouvrantes, fermantes = pile.pop()bksl-nl if len(mot) == longueur:bksl-nl mots.append(mot)bksl-nl else:bksl-nl if ouvrantes < n:bksl-nl pile.append((mot + "(", ouvrantes + 1, fermantes))bksl-nl if ouvrantes - fermantes > 0:bksl-nl pile.append((mot + ")", ouvrantes, fermantes + 1))bksl-nl return motsbksl-nlbksl-nlbksl-nl# Testsbksl-nlassert motspy-unddyck(0) == [""]bksl-nlassert motspy-unddyck(1) == ["()"]bksl-nlassert sorted(motspy-unddyck(2)) == ["(())", "()()"]bksl-nlassert sorted(motspy-unddyck(3)) == ["((()))", "(()())", "(())()", "()(())", "()()()"]bksl-nlbksl-nl

A

Commentaires⚓︎

{{ IDE('exo_corr') }}

On utilise la méthode proposée dans le sujet.

Il est aussi possible de résoudre cet exercice en utilisant une fonction récursive :

🐍 Script Python
def mots_dyck(n):
    def mots_dyck_rec(n, mot, ouvrantes, fermantes):
        if len(mot) == 2 * n:
            mots.append(mot)
        else:
            if ouvrantes < n:
                mots_dyck_rec(n, mot + "(", ouvrantes + 1, fermantes)
            if ouvrantes - fermantes > 0:
                mots_dyck_rec(n, mot + ")", ouvrantes, fermantes + 1)

    mots = []
    mots_dyck_rec(n, "", 0, 0)
    return mots

Le nombre de mots de Dyck de taille \(n\) est donné par le \(n\)-ième nombre de Catalan. On pourra à leur propos traiter l'exercice suivant

Pas que des parenthèses !

Techniquement, il est possible de définir les mots de Dyck en utilisant d'autres caractères que des parenthèses (par exemple des déplacements vers la « droite » ou vers le « haut » pour représenter les déplacements restant sous « la diagonale d'une grille ») ou plus de paires de caractères (par exemple des parenthèses et des crochets).

Z

Astuce (1)

Il n'est pas possible d'ajouter une parenthèse ouvrante si le mot en compte déjà n.

Astuce (2)

Il n'est pas possible d'ajouter une parenthèse fermante si le mot compte autant d'ouvrantes que de fermantes.

Astuce (3)

On pourra empiler des tuples du type (mot, nb_ouvrantes, nb_fermantes).

Retour en haut de la page