# Suite de de Bruijn

En mathématiques, et notamment en combinatoire et en informatique théorique, une suite de de Bruijn ou un mot de de Bruijn est un mot circulaire ou collier particulier qui a la propriété de contenir toutes les sous-suites consécutives (ou facteurs) d'une longueur donnée une et une seule fois. Les suites sont nommées d'après le mathématicien néerlandais Nicolaas Govert de Bruijn qui a contribué à leur étude.

## Définition

Formellement une suite de de Bruijn d'ordre n sur k symboles est un mot circulaire ou collier sur un alphabet A à k symboles qui contient toutes les suites de longueur n sur A une et une seule fois. Une telle suite de de Bruijn est de longueur k$^n$. Il existe
    ${\dfrac {\left(k!\right)^{k^{n-1}}}{k^{n}}}$
suites de de Bruijn distinctes sur k symboles et d'ordre n. Comme la suite est considérée circulairement, les quatre mots
    0011 0110 1100 1001
définissent la même suite de de Bruijn.

## Exemples

* Pour un alphabet à deux symboles 0 et 1, il existe deux suites de de Bruijn d'ordre 3, qui sont :
    00010111 et 11101000. La deuxième est l'opposée (0 ↔ 1) de la première (et aussi sa retournée). On ne distingue pas des suites qui se déduisent l'une de l'autre par permutation circulaire. Leur nombre est celui donné par la formule énoncée ci-dessus.
* Toujours pour deux symboles, il y a 2048 suites d'ordre 5, parmi lesquelles :
    00000100011001010011101011011111 et 00000101001000111110111001101011.

## Historique

D'après un rapport interne de Nicolaas Govert de Bruijn, l'existence de suites de de Bruijn de tout ordre a été démontré d'abord par Camille Flye Sainte-Marie en 1894 pour un alphabet binaire, et dans le cas général par Tatiana van Aardenne-Ehrenfest et lui-même en 1951.
Knuth, dans son volume 4A, mentionne de très anciens emplois de suites de de Bruijn en Inde. Plus près de nous, en 1894, A. de Rivière posait la question de l'existence d'une suite de de Bruijn binaire dans le journal L'Intermédiaire des Mathématiciens, un journal de mathématiques pour amateurs éclairés, et Camille Flye Sainte-Marie résolvait le problème la même année avec la formule d'énumération $2^{2^{n-1}-n}$. Ce résultat a été oublié, et Martin 1934 a démontré l'existence de tels mots circulaires sur un alphabet général, avec un algorithme de construction. Enfin, Kees Posthumus (en) a posé le problème en 1944 et a aussi conjecturé la formule $2^{2^{n-1}-n}$ pour des suites binaires. De Bruijn enfin a démontré la conjecture en 1946, et c'est grâce à lui que le problème est devenu universellement connu.
Karl Popper a décrit les mêmes objets indépendamment dans un livre paru en 1934 où il les appelle shortest random-like sequences (« plus courtes séquences pseudo-aléatoires »).

## Constructions

Les suites de de Bruijn peuvent être construites en suivant une chaîne hamiltonienne dans un graphe de de Bruijn d'ordre n sur k symboles ou, de manière équivalente, un cycle eulérien dans un graphe de de Bruijn d'ordre n-1. Pour la construction avec le cycle eulérien, on note alors les étiquettes des arêtes traversées.
Une autre construction, plus surprenante, consiste à concaténer en ordre lexicographique tous les mots de Lyndon dont la longueur divise n. Ainsi, pour n=4, la concaténation des mots de Lyndon
    0 0001 0011 01 0111 1
donne le mot de de Bruijn 0000100110101111. Cette construction est linéaire en temps et logarithmique en place parce qu'il existe un algorithme efficace, linéaire en temps et en place, pour engendrer les mots de Lyndon.
Encore une autre construction est au moyen de registres à décalage et basée sur les corps finis. Knuth consacre une partie de la section 7.2.1.1 de son volume 4A à des techniques de construction de suites de de Bruijn.

### Exemple détaillé

Pour construire une suite de de Bruijn binaire d'ordre 4, de longueur 2$^4$ = 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.

### Variantes

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 :

#### Algorithme « prefer one »

* Commencer avec une suite de n zéros
* 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.
* 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 (101 déjà vu, mais 100 est nouveau)
* fin (001 et 000 sont déjà vus).

#### Algorithme « prefer opposite »

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)

### Un autre algorithme simple

L'algorithme suivant est basé sur une fonction f qui associe, à un mot binaire $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 ») :
    $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 $c_{1}c_{2}\cdots c_{n}$ est minimal 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.

### Extensions

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 :
   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.

## Applications

Parmi les « applications », on peut citer la méthode qui permet de trouver un digicode ; s'il est composé de 4 chiffres par exemple, il faudrait en principe tester toutes les 10 000 combinaisons, de longueur totale 40 000. En utilisant une suite de de Bruijn, il suffit de taper au plus 10 003 chiffres (les 3 derniers pour facteur qui chevauche le début).
Les suites de de Bruijn ont trouvé des applications dans des expériences en neurosciences et en psychologie, dans l'étude des stimuli de système nerveux et peuvent être adaptées pour l'usage dans l'imagerie par résonance magnétique fonctionnelle.
Les symboles d'une suite de de Bruijn écrits en cercle autour d'un objet circulaire (comme un disque) peuvent servir à identifier un angle en examinant n symboles consécutifs faisant face à un point donné. Des codes de Gray peuvent être utilisés également dans ce cas.
Une suite de de Bruijn peut être employée pour trouver rapidement le bit de poids faible ou le bit de poids fort dans un mot en utilisant des opérations bit à bit$^,$.

## Generalisations
### Tore de de Bruijn

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é $O(n\log n)$ existent pour certaines suites particulières construites par récurrence et s'étendent au cas bidimensionnel.

### Suite généralisée

Une suite de de Bruijn généralisée avec les paramètres $(n,l,k)$ est une suite cyclique de $n$ bits telle que chaque facteur de longueur $l$ figure au plus $k$ fois. Une telle suite est dite équilibrée si elle contient autant de 0 que de 1.
Une suite de de Bruijn usuelle d'ordre $m$ est une suite de de Bruijn généralisée avec les paramètres $(2m,m,1)$. Une telle suite est toujours équilibrée. Le résultat principal de Baker et al. 2023 caractérise les paramètres $(n,l,k)$ pour lesquels il existe une suite de Bruijn généralisée équilibrée avec des paramètres $(n,l,k)$. Les auteurs prouvent que, pour des entiers positifs $n,l$ et $k$, il existe une suite de Bruijn généralisée équilibrée avec les paramètres $(n,l,k)$ si et seulement si $n$ est pair et $k>n/2^{l}$