¿Por qué la búsqueda de una secuencia de Bruijn no cíclica siempre da como resultado una secuencia de Bruijn cíclica?

Question

Estoy estudiando un código para producir secuencias cíclicas binarias de De Bruijn. Si $n$ es la longitud de la subsecuencia que no debe repetirse más de una vez, busca una secuencia de Bruijn no cíclica de longitud $2^n + n - 1$ y devuelve el primer $2^n$ bits como la secuencia cíclica.

Esto parece dar siempre una secuencia cíclica de De Bruijn, pero no entiendo por qué. entiendo por qué. ¿Por qué los últimos $n-1$ bits del no cíclico de longitud $2^n+n-1$ siempre el mismo que el primero $n-1$ ¿Bits?

Aquí está el código en Python.

def debruijn(x):
  if x.find(x[-n:]) < len(x)-n:  # check if last n chars occur earlier in the string
    return
  if len(x) == N+n-1:
    print(x[:N])
    return
  debruijn(x+"0")
  debruijn(x+"1")

n = 4
x = "0"*n
N = 2**n
debruijn(x)

Este es el resultado de $n=4$ .

0000100110101111
0000100111101011
0000101001101111
0000101001111011
[...]

(Publicado originalmente en https://stackoverflow.com/questions/57731516/why-does-this-de-bruijn-code-always-return-0s-for-the-last-few-bits pero trasladado aquí a petición).

Answer 1

Sea $x_1x_2\dots x_n$ ser el primero $n$ bits de la secuencia. En este algoritmo, en realidad todos se inicializan a $0$ pero eso no nos importa.

En la secuencia de longitud $2^n + n - 1$ cada $n$ -bit ocurre exactamente una vez: tiene $2^n$ subcadenas y ninguna de ellas se repite. En concreto, las $n$ -subcadenas de bits $0x_1 x_2 \dots x_{n-1}$ y $1x_1 x_2 \dots x_{n-1}$ tienen que ocurrir en alguna parte.

Si ninguno de ellos se produce al final de la secuencia, entonces el siguiente $n$ -bit después de ellas (compartiendo $n-1$ de sus bits) son $x_1x_2 \dots x_{n-1} y$ y $x_1 x_2 \dots x_{n-1}z$ para algunos $y$ y $z$ . Pero entonces, entre las tres subcadenas

• $x_1 x_2 \dots x_{n-1} x_n$ (se encuentra al principio)
• $x_1 x_2 \dots x_{n-1} y\phantom{{}_n}$ (encontrado después de $0x_1 x_2\dots x_{n-1}$ )
• $x_1 x_2 \dots x_{n-1} z\phantom{{}_n}$ (encontrado después de $1x_1 x_2\dots x_{n-1}$ )

dos tienen que ser iguales, porque al menos dos de los bits $\{x_n, y, z\}$ deben ser iguales. El algoritmo no puede producirlo: cuando encuentra una repetición, retrocede.

La única opción que queda es que una de las subcadenas $0x_1x_2\dots x_{n-1}$ y $1x_1x_2\dots x_{n-1}$ se encuentra al final de la secuencia, y no viene nada después. Por lo tanto, el último $n-1$ bits son $x_1 x_2 \dots x_{n-1}$ y la secuencia es realmente cíclica.

---

Si profundizamos en la teoría, existe una versión más sencilla de la prueba anterior.

Una secuencia de Bruijn de longitud $2^n + n - 1$ es un recorrido de Euler en la $(n-1)$ -binario dimensional Gráfico de Bruijn . Una secuencia cíclica de Bruijn de longitud $2^n$ es un recorrido de Euler cerrado en este grafo.

En un grafo dirigido en el que todos los grados de entrada son iguales a los de salida, como éste, todos los recorridos de Euler se ven obligados automáticamente a ser cerrados: de lo contrario, saldríamos del vértice inicial más veces de las que entramos en él, y entonces no podríamos utilizar todas sus aristas.