29 novembre 2021
Ce texte fait partie d’une petite collection de notes mise à disposition selon les termes de la Licence Creative Commons Attribution - Pas d’Utilisation Commerciale - Partage dans les Mêmes Conditions 2.0 France.
Dernières corrections : 29 novembre 2021.
Les mots de Dyck correspondent aux systèmes bien formés de parenthèses. On peut les voir comme des mots sur un alphabet à deux lettres
Exemple aabbabaabb
est un mot de Dyck, de longueur 10.
Il existe des techniques bien connues pour énumérer ces mots :
Notre objectif est de montrer ici comment, dans un programme C, énumérer tous les mots de Dyck d’une taille fixée, en nous basant sur la grammaire context-free bien connue qui les engendre.
Rappel les mots de Dyck sont générés par la grammaire context-free d’axiome :
(le mot vide)
Conséquence sur les mots d’une taille donnée : en remarquant que
Donc on peut obtenir tout mot de taille (non nulle) par une unique combinaison de 2 mots plus petits.
Pour générer au hasard un mot de Dyck de taille , l’entier étant fixé on peut utiliser l’algorithme récursif non déterministe suivant :
Ce algorithme est susceptible de fournir tous les mots de taille , sans exception.
On peut aussi le voir comme un algorithme à backtracking, si on s’autorise à revenir en arrière dans les étapes pour trouver une autre solution.
Notre but est d’obtenir des fonctions C qui permettent de traiter tous les mots de taille .
Ici nous essayons de coller au maximum à la définition récursive pour générer les mots.
La fonction que nous présentons combine génération et traitement de chacun des mots de Dyck d’une taille donnée.
int main()
{"Enumeration des mots de Dyck de taille 6\n");
printf(int n = 0;
6, print_dyck_word_with_counter, &n);
gen( }
Le premier paramètre indique la taille voulue, le second est une fonction à appliquer à chaque solution dans un certain contexte (3ième paramètre).
La fonction print_dyck_word_with_counter
est un exemple d’utilisation, dans lequel le contexte est l’adresse d’un entier qui sert de compteur :
void print_dyck_word_with_counter(int n, char t[], void *context) {
int *counter = context;
1;
*counter += "%d : ", *counter);
printf(for (int i=0; i<n; i++) {
"%c", t[i]);
printf(
}"\n");
printf( }
l’affichage produit est le suivant :
Enumeration des mots de Dyck de taille 6
1 : aaabbb
2 : aababb
3 : aabbab
4 : abaabb
5 : ababab
gen()
typedef void (*ACTION)(int n, char t[], void *context);
void gen(int n, ACTION action, void *context) {
int t[n];
0, n, action, context);
gen1(n, t, }
La fonction gen
reçoit comme paramètres
Elle alloue un tableau t
, et effectue un appel à gen1
qui signifie
t
de taille n
,0
à n
(non compris) de toutes les façons possibles,gen1()
La fonction gen1()
visite successivement toutes les manières de remplir la tranche d’indices begin
à end-1
, et leur applique une action.
ctx
) qu’il faudra ensuite
void gen1(int n, char t[], int begin, int end, ACTION action, void *contexte)
{if (begin == end) {
action(n, t, contexte);else {
} 'a';
t[begin] = for (int middle = end; middle > begin; middle -=2) {
1] = 'b';
t[middle-struct ContinuationContext ctx = {
.begin = middle,
.end = end,
.action = action,
.context = contexte
};1, middle -1, &gen2, &ctx);
gen1(n, t, begin+
}
} }
La boucle for
est en ordre descendant pour fournir les solutions dans l’ordre lexicographique (en supposant que a
précède b
).
gen2()
La fonction gen2
récupère les éléments du contexte d’origine, et rappelle gen1
pour remplir la partie droite du mot :
struct ContinuationContext {
int middle, end;
ACTION action;void *context;
};
void gen2(int n, char t[], void *ctx)
{struct ContinuationContext *context = ctx;
gen1(n, t, context->middle, context->end, context->action, context->context); }
On effectue donc ici un parcours récursif de l’espace des solutions, avec application d’un traitement passé en paramètre.
En l’état actuel des choses (2021), le langage C ne propose pas de “lambdas”, ce traitement est décrit par transmission d’un pointeur de fonction et un pointeur vers un contexte.
def gen(size, process):
buffer = ['x'] * size
buffer, 0, size, process)
gen1(
def gen1(buffer, begin, end, process) :
if begin == end:
buffer)
process(else:
buffer[begin] = 'a'
for middle in range(end, begin, -2) :
buffer[middle-1] = 'b'
buffer, begin+1, middle-1,
gen1(lambda b: gen1(buffer, middle, end, process))
6, lambda l : print(l)) gen(
Exécution
['a', 'a', 'a', 'b', 'b', 'b']
['a', 'a', 'b', 'a', 'b', 'b']
['a', 'a', 'b', 'b', 'a', 'b']
['a', 'b', 'a', 'a', 'b', 'b']
['a', 'b', 'a', 'b', 'a', 'b']