Mots de De Bruijn

Chaînes circulaires, les plus courtes possibles, contenant tous les mots de longueur n d'un alphabet A.
Ces mots peuvent être, par exemple, des codes d'accès de portes d'immeubles ...

On a un alphabet A de p = |A| lettres et on cherche une chaîne circulaire contenant tous les mots de n lettres écrits dans cet alphabet.

Soit G le graphe orienté dont les sommets sont les p^n-1 mots de n-1 lettres et dont les arcs sont les pⁿ mots de n lettres, l'arc d'origine aX et d'extrémité Xb étant de la forme aXb.
Trouver une suite de de Bruijn revient à trouver un circuit eulérien. Pour tout sommet s, les degrés d^-(s) et d⁺(s), nombres d'arcs entrants et sortants, sont égaux (par symétrie !) et donc un circuit eulérien existe.

Exemple 1 :
Les 25 mots de 2 lettres utilisant les cinq chiffres de 0 à 4 inclus, sont contenus dans la chaîne circulaire 0102030411213142232433440
(00 est obtenu en refermant la chaîne sur elle-même ...3440<->01020...)


Exemple 2 :
L'alphabet est {0, 1}, tous les mots de longueur 5 sont contenus dans la chaîne (circulaire) 01000110010100111010110111110000
Cette chaîne permet de trouver sur le graphe ci-dessous un circuit eulérien de sommets 0100, 1000, 0001, 0011 ... et d'arcs 01000, 10001, 00011, 00110 ...

Le programme JavaScript utilisé ci-dessous arrête sa recherche à la 10ième chaîne solution. Chaque solution est écrite sur une ligne différente.

Netscape n'apprécie pas du tout trop de récursivité ! Si vous augmentez la taille de l'alphabet ou la longueur des mots. essayez un autre navigateur, Konqueror, Mozilla ou Opera conviennent.
Mieux, essayez le parcours eulérien ou compilez le programme C.