Suite de de Bruijn

Pour construire une suite de de Bruijn binaire d'ordre 4, de longueur 2⁴ = 16, contenant les 16 mots binaires de longueur 4, on peut utiliser un circuit eulérien dans le graphe de de Bruijn B(2,3) de la figure.

Chaque arc de ce graphe est formé de quatre bits : les trois premiers sont l'étiquette du sommet de départ, les trois derniers ceux du sommet d'arrivée. Voici un chemin eulérien du graphe (écrit sur deux lignes).

000, 000, 001, 011, 111, 111, 110, 101,
011, 110, 100, 001, 010, 101, 010, 100.

Chaque sommet est visité deux fois, puisqu'il y a deux arcs entrants (et aussi deux arcs sortants). En retenant chaque fois le premier bit du code du sommet, on obtient le mot de de Bruijn :

0 0 0 0 1 1 1 1 0 1 1 0 0 1 0 1

On aurait aussi bien pu garder le dernier bit, et alors on obtient :

0 0 1 1 1 1 0 1 1 0 0 1 0 1 0 0

On peut également utiliser un circuit hamiltonien, et on obtient alors une suite de de Bruijn d'ordre 3.

Une méthode simple pour trouver le bon cheminement consiste par exemple à choisir systématiquement l'arc qui porte l'étiquette qui se termine par 1. C'est une des méthodes présentées dans un article du American Mathematical Monthly[10] :

1. Commencer avec une suite de n zéros
2. Essayer d'ajouter un 1 à la suite. Si les n derniers bits n’ont pas été rencontrés auparavant, accepter et répéter l'étape 2, sinon passer à l'étape suivante.
3. Essayer d'ajouter un 0 à la suite. Si les n derniers bits n’ont pas été rencontrés auparavant, accepter et répéter l'étape 2; sinon arrêter.

Pour n = 3, cette méthode produit successivement les suites :

• 000
• 0001 (001 est nouveau)
• 00011 (011 est nouveau)
• 000111 (111 est nouveau)
• 0001110 (111 déjà vu, mais 110 est nouveau)
• 00011101 (101 est nouveau)
• 000111010 (011 déjà vu, mais 010 est nouveau)
• 0001110100 (100 est nouveau)
• fin( 001 et 000 sont déjà vus).

Une autre façon d’engendrer la séquence est l’algorithme « prefer opposite ». Cet algorithme est similaire au précédent, mais au lieu d’essayer d’ajouter le bit 1 à chaque étape, on essaye de continuer par le bit opposé au dernier bit de la suite. En cas d'échec, on essaie d'ajouter le même bit, et si on échoue encore, l’algorithme se termine.

Cette procédure, cependant, ne produit pas le mot formé uniquement de 1. La règle est donc modifiée comme suit : si la suite se termine par n-1 fois 1, et dans ce cas seulement, ajouter 1.

Pour n = 3, cette méthode produit successivement les suites :

• 000
• 0001 (001 est nouveau)
• 00010 (010 est nouveau)
• 000101 (101 est nouveau)
• 0001011 (010 déjà vu mais 011 est nouveau)
• 00010111 (on privilégie 1 pour obtenir 111)
• 000101110 (110 est nouveau)
• 0001011100 (101 déjà vu mais 100 est nouveau)
• fin (001 et 000 déjà vu)

L'algorithme suivant[11] est basé sur une fonction f qui associe, à un mot binaire ${\displaystyle b_{1}b_{2}\cdots b_{n}}$, un autre mot binaire selon la règle (appelée « shift rule » ou « règle de décalage ») :

${\displaystyle f(b_{1}b_{2}\cdots b_{n})={\begin{cases}b_{2}b_{3}\cdots b_{n}{\bar {b}}_{1}&{\text{si}}\ \ b_{2}b_{3}\cdot b_{n}1{\text{ est minimal}}\\b_{2}b_{3}\cdots b_{n}b_{1}&sinon\end{cases}}}$

Ici, un mot binaire ${\displaystyle c_{1}c_{2}\cdots c_{n}}$ est minimal[12] s'il est minimal parmi tous ses permutés circulaires. Par exemple, 0001, 0101, 1111 sont minimaux, 1000, 1010 ne le sont pas. En d'autres termes, un mot minimal est une puissance d'un mot de Lyndon.

La règle de décalage est appliquée itérativement en commençant par un bloc formé de zéros. Pour n=5, on obtient

00000, 00001, 00011, 00111, 01111, 11111, 11110, 11101, 11011, 10111, 01110, 11100, 11001, 10011, 00110, 01100, 11000, 10001, 00010, 00101, 01011, 10110, 01101, 11010, 10101, 01010, 10100, 01001, 10010, 00100, 01000, 10000.

Si l'on prend les premiers bits de chacun des blocs, on obtient la suite de de Bruijn:

00000111110111001100010110101001

et les auteurs prouvent que c'est une suite de de Bruijn dans le cas général.

Peut-on étendre un mot de de Bruijn d'ordre n en un mot d'ordre n+1 ? La réponse est plus subtile que l'on ne pourrait supposer, parce qu'elle fait intervenir la taille de l’alphabet[13] :

Toute suite de de Bruijn binaire d'ordre n peut être étendue en une suite de de Bruijn d'ordre n+2. Toute suite de de Bruijn d'ordre n sur au moins trois symboles peut être étendue en une suite d'ordre n+1.

Il en résulte qu'il existe des suites de de Bruijn infinies ; elles sont définies comme des limites de suites de de Bruijn finies.

Une question similaire est la suivante : peut-on étendre une suite de de Bruijn d'ordre n sur k lettres en un mot d'ordre n sur k+1 lettres ? La réponse est là aussi, positive[14].

Tore de de Bruin. Toute matrice d'ordre 2 x 2 apparaît une fois.

Un tore de de Bruijn (en) est un tableau toroïdal qui a la propriété que toute matrice d'ordre m x n dont les éléments peuvent prendre k valeurs y apparaît exactement une fois.

On peut utiliser un tel dispositif pour coder une matrice par le couple d'indices indiquant sa position dans le tore de de Bruijn.

Le calcul de la position de l'unique occurrence d'un mot ou d'une matrice dans une suite ou dans un tore de de Bruijn est connu sous le nom de problème de décodage de de Bruijn. Des algorithmes efficaces en complexité ${\displaystyle O(n\log n)}$ existent pour certaines suites particulières construites par récurrence[19] et s'étendent au cas bidimensionnel[20].

Une suite de de Bruijn généralisée avec les paramètres ${\displaystyle (n,l,k)}$ est une suite cyclique de ${\displaystyle n}$ bits telle que chaque facteur de longueur ${\displaystyle l}$ figure au plus ${\displaystyle k}$ fois[21]. Une telle suite est dite équilibrée si elle contient autant de 0 que de 1.

Une suite de de Bruijn usuelle d'ordre ${\displaystyle m}$ est une suite de de Bruijn généralisée avec les paramètres ${\displaystyle (2m,m,1)}$. Une telle suite est toujours équilibrée. Le résultat principal de Baker et al. 2023 caractérise les paramètres ${\displaystyle (n,l,k)}$ pour lesquels il existe une suite de Bruijn généralisée équilibrée avec des paramètres ${\displaystyle (n,l,k)}$. Les auteurs prouvent que, pour des entiers positifs ${\displaystyle n,l}$ et ${\displaystyle k}$, il existe une suite de Bruijn généralisée équilibrée avec les paramètres ${\displaystyle (n,l,k)}$ si et seulement si ${\displaystyle n}$ est pair et ${\displaystyle k>n/2^{l}}$