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 
>>> mots_dyck(0)
['']
>>> mots_dyck(1)
['()']
>>> mots_dyck(2)
['(())', '()()']
>>> mots_dyck(3)
['((()))', '(()())', '(())()', '()(())', '()()()']
###(Dés-)Active le code après la ligne # Tests (insensible à la casse)
(Ctrl+I)
Entrer ou sortir du mode "deux colonnes"
(Alt+: ; Ctrl pour inverser les colonnes)
Entrer ou sortir du mode "plein écran"
(Esc)
Tronquer ou non le feedback dans les terminaux (sortie standard & stacktrace / relancer le code pour appliquer)
Si activé, le texte copié dans le terminal est joint sur une seule ligne avant d'être copié dans le presse-papier
Évaluations restantes : 10/10
.128013à«[3è4.»nx/R8p)IL0hCD*v7c256g9Nf=buS-T,_l(wOaPké;:ors1qm!yd]ji te+050+0;0:0T0.0P0#0/0z0P0T0#0#0H010:0.0o010406050#0J0(0(0T0!0*040K0Z0P0J160Z0j0/020T0(0o0X0/0m0;1g0!0%0J0;0#050l1d1f1h1j1b0o041H1O051R0l1R1T1O1b0+0.0x0~1012140t0.0D0t0P1+0t0:19050_0I0P0;1$1113011*1,1.1,0:1@1_1=0:0I0Z0+1j1?0!1P0:0t0~1m0#0o0T0j140A011{1(010G0{0;0j1u0;1=2j2l2q1}2t1_2w0(2y040a0/0U0!0Z0o0Z0#0.1p1r0@2h0!0!0;0z2T1H2A0j1P0l2f2)0:2d2c2e0+2C141.0j2v2Q1=1Z1#0 1|2?0.2^0j291!1=0o2Y1P2%2)3a1c2k1r2~2r330!1g0P190/0$2$3e1a3d2B3g1}3i3k3m0A3p2l3r2%2=013w0T3l040/0e3A2(1b3D3u143G3I0/0g3M3C3e3E3S3m0B3W3O3Y3Q3F0Z3j3H3m0C3%3s3f1%3v3,3x3J0y3;3P3@3R3_3.3J0n3}3)3 3+3-3T0E453t473!040$0s4c3?2 483`0$3o1I3q3(4d4l4f0$3z4q3B4s4k3h413I0$3L4y3N3=3Z4D190$3V4H3X4t4C494M3$4P4A4K4T4g3:4W4J3*4v3|4$3~4u4L4g444+464-4Z0$4b4;4R3^4Z0A4i4`4B4|3`0A4p3c1U381H2|2,0+2:3E0z292I0?1!1P370;393q3W055f0@5n4{140V190@0G5p4,2r0R3m5A4=3h0G190(0Z0:0#0O2a0z0V5F5u0118040Q5S513R190j5Y3E5V0p0Y3%0/5-0/4%4e190P1q0D1E0J0!3W5/5B1}0Z190H5|5:4l0(0.194x3a5}5G5 190w635~5!045$4W5.6b5T0j5J5L1G4P6n5Z016004626t642r5V0d0,5,5.6B3v190o2u6g6c146x6z6a6I146D5X4P6T010#2o0401015%3*5V0N6N5T66194 3c6h5U196,6A6?6/046;5o6?5)6F6l6H6?5w040R1*1_6-6v0j0I5=2v6)475V6W6=6O3F6K6M6X70190p7b3E6x020D0:0X7u3*6|6~3B6Y5V5+736m5-6Y6p045K0:7h4l6+7B5;040Z0J0x0!2l0:1F7R6C6^7U4u190G0;3-0j7$6s6S6?6Q7+3h7o7a7q7m6x0h7(6J042P0o826U190Q7t7J7K6Y760.5z6`7m7d7f6k7l5T7j877n7O5L8q5)7`6d6y6R3q6u3Z5=5@5_5{7~8o197I3a067K8N8B4(6q5M8q808q7N0T0o0o2v0+8u898V8R8$048b8L8O8P47760;0|0;8*8K4r8.6m8e198g8w6i7X7Z7#7%8i5T7w0P7z908r8m6 7m7H6G8{8d6?7N6L7}8n6v8U8H7c198X8Z0j8#9r5(897k9e6o8)969p190=9b6!19010Q6(9y6*7*9F8C7W7Y7!7;957@7 9H9b6|559C6v7T9S8Q047.7:7=8*0p8,8`9i8/4l8f8h9Z9D9U939X7?8A6Y6x0L9b7N9/1ga29b7w7y7A9,477D8^9h9_7L9k7|8@9P479q9o9T9u8!8*0Q9B7Fao8s7Qah4l6x9IaF2r9K6$0p9Oau9Q046_9~9sa09W9;ar7S9RaT9Taa94a33B9`2raH9$674g9=9@4z8|75192Y0:5`9da*7M8Ra)3N064X3*0z0$19030/0M1F8S503E761|7/aEa#9-7P5N5P5RaY7)5W8qajbq1}8vaJ8x0H8za~7r040d8qaL6%8*728L8}04bh0!bja4aCbm5O0*5Qaybta/9(aB9f7sad61bB2(a+bw19bFbv14bH8aaO9)9z04bK4rbMbObQbC8j7e040#3,7$9xaP7i8%b:8rbTbobXcb6|69b^aQ9?b(8y9b6DbG6#9M8aaN8*aSbR7mb=0pb?bJ4jbf9t12bia8c2c4bP0;c7cjc9bscb7NcdbVbpc8aZcQcW2r6|4GcZb-8+a=b+a5b)cob.cq9Lazctcucb9+bk47b=8actb@b#8IaR9Jcraz9?cBc^a!cx5Tczd5c@c%88d2byb;d4cAdlc 2(7G19b{4z1H5r5m1Q580l5a1H0:5cdA2.2*282a2,0T1^dvdy5j1N5t6v2Y0(0O0G0T0V0;0O0t0e191z1B1D1F0/8_7F1U3r1O0S1r1o0{0.0#1`100/0(0W2f5g0/372O2Q0W1`0+2l0}1_0/1d0-0^81d-dO0q0P0/bc0/0T0J120.e02Q2RdK0/2V0!0Wc40J0+2Y0~0^ej0k7/0z0.0z1`2v0/d=1.0#7#eM2^0/0G1q2!0.1q0/ew0z5`2R0x1`7I1X5i2}471 1-1/1;dP3E2E2v2x192K0K0z0!170:2L0*d~a}do5ldP3b5odue?3*765y8q5D3J8V5IaDbncUcfdf9c9=d+3Na@7mfe0;9}cO4lfh5/cRfkcT5Q0O2Y0zfofz7{6jcva89Efpc_daaU92aW9YfLc(cwc09 a%acd88+fs1a8.bM8 di3Fc22FfKd0aU7P9=cmbAa.68cm6ff:7Nf5fccPf+8M9_a fl8T19eefp8W8Yaxf)aAdobS8tf)c*f,8ObM8=d^ak8cf-a^04f/c`7,aVa(cm0299aggBfMg4dp04g7amfu9 fF0VfH2Zf@gl8j5#fOg2fQfT7v9#f:b=dng5cXf!c+aCfVgEf:a-f:9%g!gJ83f%aXfRb%gwgrgygAg%9-g=f(g|6P19a7g#9.7/abg h6as197x9ag_a/7EgXd1gOgPangYflbUfGfIgWg-gKg{hjgCf`g@g)ha6ZcrdefYdgg/fig;9Vg?h0dhhKa9hghUhFa,hJh#1}g`go3%g8hvgR6rf|c.bEdrft74hwgSgUfJgj8(fNf)hQb,dj9Lg,gMi26YbuhVi86{hpf{8cbMa`a|fPgb4$0lfbdwdL5adO0r1`330(0IeB2Vbmeu1`0vcUiB0/0_0{e96Y1h2S0t1g7$0k19090Q0j09gpej0#f10+1q0j0We01h0/iJ6?iL2fiO0;iQ04iSiUgp0L0.0f2H5/0T0/0t2Y0G1)230o0#0Y0l0l0G0!0h0R0.0V17cM0.0T0h3,0D0ljdjf0l0F0Ziw2Y5OdX0u0T0_10g3jsixe51`jxjz2l1H0T040h0/d:eq5`7!0/0bi*0;5`e02N2P0}2-0`7$0!i*00i:eGeI1`05i~j0fxj30:j5j70l0;0L0j2R0h0D2S100I0heX57jy0.d(jq0A0l0n0g0Ej|0I0O0zjy3H2l0O0$1I0Jec0:0l191d1!7#jJ2)e+0@iH0|4K7$193O1e1B1j0U110/d(iB0}2k2Y7;0t0fd^0}0)2$kI1Ld.04bb0z0t0jk81E2H7;0N0/0{iXf1jZese92V0+0W2tk+j(1_0}iA2ViD5Qejd;16eOeQ0+00em2-d)kj7!2!0f2Y0}kO0@kQ1h2v2fkVd)0QkReE1A0ok`d)k|lz0TeJk.5M0/e(0!e8i~0ceu2N2S1`0i0/7XlI7/e81`lN0tle0/lS2PjW2Y37exlr7/jU0}lC10lFlr0}ll0_7;ea7X0}lNd`1Z0T0D1q3He5000JeS0De 0Pe90i0plT0Je01nl:1`2k0.lliFlhlE0:lklulwj+1vlAlpkSlskWejiZlg2Nk)0^0#0peee+dy0^0`0|3rmNkC0#04.
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).