Quiero hablaros ahora sobre las secuencias de De Bruijn. Las introduje en un vídeo largo hace poco, relacionándolas con la música india y con algunas aplicaciones de las telecomunicaciones modernas. Y son un tema con tantos detalles que me gustaría ampliar algunos de ellos en esta entrada. ¡Al lío!
¿Qué es una secuencia de De Bruijn?
Nada mejor que empezar con un ejemplo sencillo. Considera la secuencia numérica
0011221020.
Esta secuencia contiene todas las parejas posibles formadas por los números \{0,1,2\}. En algún punto puedes encontrar la pareja 00, la 20 o la 12. Todas las parejas aparecen y, lo que es más importante, aparecen una sola vez.
Además, como la secuencia empieza y termina con el mismo número, podemos cerrarla en forma de ciclo.
La misma idea se puede aplicar a los tríos. La siguiente secuencia tiene todos los tríos formados por los números \{0,1,2\}, solapados y sin repeticiones:
00011122212110220210120100200.
Por dar algunas palabras técnicas: En el mundillo decimos que una pareja es una cadena de longitud dos, y un trío, una cadena de longitud tres.
En general, una secuencia de De Bruijn es una secuencia numérica que contiene todas las cadenas de longitud \ell formadas por los números \{0,1,2, ..., n-1\} superpuestas entre sí y sin repeticiones. Además, estas secuencias se pueden cerrar en forma de ciclo.
En el resto del artículo, escribiré las secuencias en formato lineal (dibujarlas en forma de ciclo, como la animación de arriba, es bastante laborioso). Estas secuencias se leen de forma cíclica, es decir, al llegar al último dígito se debe continuar la lectura por el principio. Por ejemplo, he aquí una secuencia de De Bruijn que contiene todos los cuartetos (\ell=4) formados por los números \{0,1\}. El cuarteto 1000 está formado por el último dígito y los tres primeros.
0000111100101101
¿Cómo se forma una secuencia de De Bruijn?
Para números pequeños es fácil encontrar secuencias de De Bruijn probando con lápiz y papel. Según aumentas el tamaño o añades más números, la cosa se complica. Por eso, quiero (re)enseñar aquí el método que propuso I. J. Good en 1946 para resolver el problema mediante teoría de grafos.
Un ejemplo
Vamos a buscar la secuencia de De Bruijn que contiene todos los tríos (\ell=3) formados por los números \{0,1\}. Para ello, construiremos un grafo dirigido. Un grafo dirigido es como un grafo normal (o sea: un conjunto de puntos y de líneas que unen los puntos), donde las líneas, o «arcos», tienen una dirección. Salen de un punto y llegan a otro, y el sentido en que lo hacen es importante.
Nuestro grafo dirigido estará formado por puntos y arcos que siguen estas reglas:
- Habrá cuatro puntos, y cada uno tendrá el nombre de una pareja distinta de ceros y unos. Solo hay cuatro opciones: 00, 01,10,11.
- Habrá ocho arcos, cada uno con el nombre de un trío distinto de ceros y unos:
000, 001, 010, 011, 100, 101, 110, 111
- Los arcos unirán los puntos según su nombre: las dos primeras cifras del arco indicarán de qué punto sale, y las dos últimas, a qué punto llega.
\text{Arco:}~~~~~~\rlap{$\underbrace{\phantom{1 ~~ 1 }}_{\text{Sale}}$}1~~
\overbrace{1~~ 0}^\text{Llega} Así, en este caso, el grafo resultante tendría este aspecto:
Como se aprecia a simple vista, todos los puntos tienen dos arcos de entrada y dos arcos de salida. Según el teorema de Euler, podemos recorrer todos los arcos sin repeticiones siguiendo una ruta circular. El teorema de Euler dice, resumidamente, que si todos los puntos de un grafo dirigido conexo tienen tantos arcos de entrada como arcos de salida, entonces el grafo se puede recorrer con una ruta circular que no repita ningún arco. Esta sería una manera de hacerlo:
Si anotamos los arcos de la ruta, en el orden en que los recorremos, tendremos una lista con los ochos tríos posibles de ceros y unos, sin repeticiones.
000, 001, 011,111,110,101,010,100
Estos tríos se pueden superponer. Es decir, las dos últimas cifras de un arco coinciden con las dos primeras cifras del siguiente. Esto es consecuencia de las reglas con las que hemos construido el grafo: Las últimas cifras de un arco indican a qué punto llega, y las dos primeras de qué punto sale. Cuando la ruta atraviesa un punto, el arco por el que entra y el arco por el que sale tienen en común el nombre del punto que atraviesan.
En resumen: podemos solapar los tríos de la lista y llegar a la secuencia 0001110100. Como la ruta es circular (empieza y acaba en el mismo punto), la secuencia empieza y termina con la misma pareja de cifras. Podemos cerrarla en forma de ciclo (o, más bien, leerla de forma cíclica):
00011101
Esta secuencia tiene todos los tríos formados por los números \{0,1\}, solapados y sin repeticiones. ¡Es una secuencia de De Bruijn!
Otro ejemplo
Vale. Vamos a buscar ahora la secuencia de De Bruijn que contiene los tríos formados por los números \{0,1,2\}. En este caso, habrá un punto por cada pareja (00,01,...,22) y tantos arcos como tríos (unos veintisiete, en total). La regla para colocar los arcos es la misma de antes. En este caso, el grafo resultante tiene este aspecto:
Este grafo es un poco más chungo, lo admito. Pero aprovecho para remarcar algo: técnicamente esto no es un grafo, sino la representación gráfica de un grafo, valga la redundancia. Los matemáticos no siempre representan los grafos con los que trabajan; a veces les basta con saber qué puntos tienen y cómo se distribuyen los arcos. Hacer el dibujo no siempre es útil.
¡Aunque en este caso lo es! Así podemos ver que cada punto tiene tres arcos de entrada y tres arcos de salida. El teorema de Euler asegura que podemos recorrer todos los arcos siguiendo una ruta circular que los visite todos y no repita ninguno. Esta es una posibilidad:
Si anotamos arcos de la ruta en una lista y los superponemos, y lo leemos en forma de ciclo, conseguimos una secuencia con todos los tríos, solapados y sin repeticiones. Esta es una secuencia de De Bruijn.
000211102221001011212202012
En general
El método propuesto por Good funciona con cadenas de cualquier longitud \ell y con cualquier conjunto de números \{0,1,2,...,n-1\}. El método es fácil: Construye un grafo que tenga, como puntos, todas las cadenas de longitud \ell-1, y añade un arco por cada cadena de longitud \ell. Los arcos unen puntos según la regla de antes: las primeras \ell-1 cifras indican de qué punto sale el arco y las \ell-1 últimas a qué punto llega.
\text{Arco:}~~~~~~\rlap{$\underbrace{\phantom{a_0 ~~ a_1~~ a_2~~....~~a_{n-1} }}_{\text{Sale}}$}a_0~~
\overbrace{a_1~~ a_2~~....~~a_{\ell-1}~~a_\ell}^\text{Llega} Lo importante es que, siguiendo esta regla, cada punto de grafo tendrá n arcos de entrada y n arcos de salida. ¿Cómo lo sabemos? Bueno, plantéalo así: ¿Qué arcos salen de un punto determinado?
\text{Arco:}~~~~~~\underbrace{a_0 ~~ a_1~~ a_2~~....~~a_{\ell-1} }_{\text{Nombre del punto}}~~b_\ellLas primeras cifras indican el nombre del punto del que sale el arco. Todos los arcos que empiecen por esa combinación de cifras deben salir de ese punto. Esos arcos solo se diferencian en el último dígito, b_\ell, que debe ser uno del conjunto \{0,1,2,...,n-1\}. En total, hay n posibilidades para la última cifra, luego ese es el número de arcos de salida de cada punto.
El mismo argumento sirve para ver que hay n puentes de entrada.
En resumen: este tipo de grafos, conocidos como grafos de De Bruijn, siempre tienen el mismo número de arcos de entrada que de salida en cada punto y, gracias al teorema de Euler, podemos asegurar que puedes recorrer todos los arcos siguiendo una ruta circular sin repeticiones. Esa ruta te indica el orden de los números que forman la secuencia de De Bruijn.
Un problema de grafos, sin grafos
La explicación de los grafos es muy resultona en un vídeo, muy visual, pero quizá no sea del todo práctica. Depende de para qué la uses.
En teoría
Un par de meses después de la publicación de Good, el matemático neerlandés N. G. de Bruijn utilizó el enfoque de los grafos para calcular el número de secuencias distintas que había en el caso binario. O sea, el número de secuencias de De Bruijn que contienen las cadenas de longitud \ell empleando los números \{0,1\}. Resultó que la cantidad de secuencias distintas era de 2 elevado a la potencia de 2^{\ell-1}-\ell:
2^{2^{\ell-1}-\ell}.En el caso de tríos de ceros y unos, la fórmula nos dice que existen dos ciclos distintos:
00011101~~~~~~11100010
(Estas secuencias deben imaginarse en forma de ciclo)
En realidad, estas secuencias corresponden a las dos maneras distintas que tenemos de recorrer el grafo de De Bruijn del primer ejemplo. Es decir, la fórmula de De Bruijn solo está contando cuántas rutas distintas recorren un grafo. Porque he aquí el resultado principal de esta historia: cualquier secuencia de De Bruijn es una ruta circular en un grafo de De Bruijn.
En general, el número de secuencias de De Bruijn para el conjunto \{0,1, ..., n-1\} es de:
\frac{(n!)^{n^{\ell-1}}}{n^\ell} .En la práctica
En la práctica, hay algoritmos diseñados para encontrar secuencias de De Bruijn que no nacen de un planteamiento con grafos. Y oye, son mucho más cómodos si solo quieres encontrar la secuencia y dejarte de movidas. He aquí el método propuesto por M. H. Martin en 1934.
Veamos el caso de los tríos formados por las cifras \{0,1,2\}. Hacemos una lista con los veintisiete tríos posibles y empezamos a escribir aquellos compuestos por tres dígitos iguales:
000111222
Tachamos de la lista todos los tríos que aparecen en la secuencia. Por ejemplo, el 000, el 001 o el 122. Ahora buscamos, en la lista, cuál es el trío más grande que no aparece todavía en la secuencia y que empieza por 22; este resulta ser 221, así que añadimos un 1 a la secuencia y tachamos el trío de la lista. Ahora buscamos el mayor trío que empiece por 21; este resulta ser 212, así que añadimos un 2 a la secuencia y lo tachamos de la lista.
El éxito de este algoritmo (añadir siempre el trío más grande disponible) está garantizado: no se atasca en ningún sitio y desemboca en una secuencia de De Bruijn. En este caso, da lugar a la secuencia
000111222121102202101201002
Dicen que toda buena historia tiene presentación, nudo y desenlace. Ahora mismo no se me ocurre ninguna frase de conclusión para este artículo, y el desenlace llega súbita e inesperadamente con estas palabras. Fin.
A combinatorial problem. N . G. DE BRUIJN – 1946
Circuits and Trees in Oriented Linear Graphs. By Ehrenfest y De Bruijn
Normal Recurring Decimals. I. J. Good, 1946.
A problem in Arrangements. M. H. Martin, 1934