Generar todas las secuencias de De Bruijn

Question

Existen varios métodos para generar una secuencia de De Bruijn. ¿Existe un algoritmo general para crear todas las secuencias de De Bruijn únicas (las rotaciones se cuentan como iguales) para un alfabeto binario de longitud $n$ o $B(2, n)$ ?

Por ejemplo, una secuencia de este tipo para $B(2, 5)$ es $00000111011010111110011000101001$ .

Answer 1

Sí. El enfoque que encuentra un ciclo euleriano de un $(n-1)$ -se adapta fácilmente para encontrar todos los ciclos eulerianos que comienzan en un vértice dado. Dado que rotar una secuencia corresponde a trazar el mismo ciclo euleriano pero empezando en un vértice diferente, esta adaptación genera exactamente un representante para cada clase de equivalencia de secuencias. De hecho, incluso se puede hacer fácilmente que las enumere en orden lexicográfico.

Answer 2

Para los pequeños $n$ Una búsqueda en profundidad utilizando una lista o un conjunto de subsecuencias "ya vistas" es suficiente.

Answer 3

Las secuencias de De Bruijn son un subconjunto de todas las permutaciones. Por lo tanto, generar todas las permutaciones en orden, y comprobar si cumplen los requisitos de de Bruijn. Eso por sí solo generará todos los ejemplos B(k,n) para cualquier k y n. El perfil de tiempo para la detención del algoritmo es una cuestión completamente diferente.