En matemática combinatoria , una secuencia de De Bruijn de orden n en un alfabeto A de tamaño- k es una secuencia cíclica en la que cada cadena de longitud n posible en A ocurre exactamente una vez como una subcadena (es decir, como una subsecuencia contigua ). Tal secuencia se denota por B ( k , n ) y tiene una longitud k n , que también es el número de cadenas distintas de longitud n en A . Cada una de estas cadenas distintas, cuando se toma como una subcadena de B ( k , n ) , debe comenzar en una posición diferente, porque las subcadenas que comienzan en la misma posición no son distintas. Por lo tanto, B ( k , n ) debe tener al menos k n símbolos. Y dado que B ( k , n ) tiene exactamente k n símbolos, las secuencias de De Bruijn son óptimamente cortas con respecto a la propiedad de contener cada cadena de longitud n al menos una vez.
El número de distintas secuencias de De Bruijn B ( k , n ) es
Las secuencias llevan el nombre del matemático holandés Nicolaas Govert de Bruijn , quien escribió sobre ellas en 1946 . Como escribió más tarde, [1] la existencia de secuencias de De Bruijn para cada orden junto con las propiedades anteriores fue probada por primera vez, para el caso de alfabetos con dos elementos, por Camille Flye Sainte-Marie ( 1894 ). La generalización a alfabetos más grandes se debe a Tatyana van Aardenne-Ehrenfest y de Bruijn ( 1951 ). Los autómatas para reconocer estas secuencias se denominan autómatas de Bruijn y son similares topológicamente a algunas redes neuronales de retardo de tiempo . [2]
En la mayoría de las aplicaciones, A = {0,1}.
Historia
El ejemplo más antiguo conocido de una secuencia de De Bruijn proviene de la prosodia sánscrita donde, desde el trabajo de Pingala , cada posible patrón de tres sílabas de sílabas largas y cortas recibe un nombre, como 'y' para corto-largo-largo y ' m 'de largo-largo-largo. Para recordar estos nombres, se utiliza el mnemónico yamātārājabhānasalagām , en el que cada patrón de tres sílabas se produce comenzando por su nombre: 'yamātā' tiene un patrón corto-largo-largo, 'mātārā' tiene un patrón largo-largo-largo, y en adelante, hasta 'salagām' que tiene un patrón corto-corto-largo. Este mnemónico, equivalente a una secuencia de Bruijn en 3 tuplas binarias, es de antigüedad desconocida, pero es al menos tan antiguo como el libro de 1869 de Charles Philip Brown sobre prosodia sánscrita que lo menciona y lo considera "una línea antigua, escrita por Pāṇini ". [3]
En 1894, A. de Rivière planteó la cuestión en un número de la revista francesa de problemas L'Intermédiaire des Mathématiciens , de la existencia de una disposición circular de ceros y unos de tamaño. que contiene todo secuencias binarias de longitud . El problema fue resuelto (en caso afirmativo), junto con el recuento desoluciones distintas, por Camille Flye Sainte-Marie en el mismo año. [1] Esto se olvidó en gran medida, y Martin (1934) demostró la existencia de tales ciclos para el tamaño del alfabeto general en lugar de 2, con un algoritmo para construirlos. Finalmente, cuando en 1944 Kees Posthumus conjeturó el recuentopara las secuencias binarias, De Bruijn demostró la conjetura en 1946, a través de la cual el problema se hizo conocido. [1]
Karl Popper describe de forma independiente estos objetos en su The Logic of Scientific Discovery (1934), llamándolos "secuencias similares al azar más cortas". [4]
Ejemplos de
- Tomando A = {0, 1}, hay dos B (2, 3) distintos: 00010111 y 11101000, siendo uno el reverso o la negación del otro.
- Dos de los 2048 posibles B (2, 5) en el mismo alfabeto son 00000100011001010011101011011111 y 00000101001000111110111001101011.
Construcción
Las secuencias de De Bruijn se pueden construir tomando un camino hamiltoniano de un gráfico de Bruijn n- dimensional sobre k símbolos (o de manera equivalente, un ciclo euleriano de un gráfico de Bruijn ( n - 1) -dimensional). [5]
Una construcción alternativa implica concatenar juntas, en orden lexicográfico, todas las palabras de Lyndon cuya longitud divide n . [6]
Se puede utilizar una transformación Burrows-Wheeler inversa para generar las palabras de Lyndon requeridas en orden lexicográfico. [7]
Las secuencias de De Bruijn también se pueden construir utilizando registros de desplazamiento [8] o mediante campos finitos . [9]
Ejemplo usando el gráfico de Bruijn
Objetivo: construir una secuencia B (2, 4) de Bruijn de longitud 2 4 = 16 usando un ciclo de gráfico Euleriano ( n - 1 = 4 - 1 = 3) 3-D de Bruijn.
Cada borde en este gráfico tridimensional de Bruijn corresponde a una secuencia de cuatro dígitos: los tres dígitos que etiquetan el vértice que deja el borde seguidos por el que etiqueta el borde. Si uno atraviesa el borde etiquetado como 1 desde 000, se llega a 001, lo que indica la presencia de la subsecuencia 0001 en la secuencia de Bruijn. Atravesar cada borde exactamente una vez es usar cada una de las 16 secuencias de cuatro dígitos exactamente una vez.
Por ejemplo, supongamos que seguimos el siguiente camino euleriano a través de estos vértices:
- 000, 000, 001, 011, 111, 111, 110, 101, 011,
- 110, 100, 001, 010, 101, 010, 100, 000.
Estas son las secuencias de salida de longitud k :
- 0 0 0 0
- _ 0 0 0 1
- _ _ 0 0 1 1
Esto corresponde a la siguiente secuencia de De Bruijn:
- 0 0 0 0 1 1 1 1 0 1 1 0 0 1 0 1
Los ocho vértices aparecen en la secuencia de la siguiente manera:
{0 0 0 0} 1 1 1 1 0 1 1 0 0 1 0 1 0 {0 0 0 1} 1 1 1 0 1 1 0 0 1 0 1 0 0 {0 0 1 1} 1 1 0 1 1 0 0 1 0 1 0 0 0 {0 1 1 1} 1 0 1 1 0 0 1 0 1 0 0 0 0 {1 1 1 1} 0 1 1 0 0 1 0 1 0 0 0 0 1 {1 1 1 0} 1 1 0 0 1 0 1 0 0 0 0 1 1 {1 1 0 1} 1 0 0 1 0 1 0 0 0 0 1 1 1 {1 0 1 1} 0 0 1 0 1 0 0 0 0 1 1 1 1 {0 1 1 0} 0 1 0 1 0 0 0 0 1 1 1 1 0 {1 1 0 0} 1 0 1 0 0 0 0 1 1 1 1 0 1 {1 0 0 1} 0 1 0 0 0 0 1 1 1 1 0 1 1 {0 0 1 0} 1 0 0 0 0 1 1 1 1 0 1 1 0 {0 1 0 1} 0} 0 0 0 1 1 1 1 0 1 1 0 0 {1 0 1 ... ... 0 0} 0 0 1 1 1 1 0 1 1 0 0 1 {0 1 ... ... 0 0 0} 0 1 1 1 1 0 1 1 0 0 1 0 {1 ...
... y luego volvemos al punto de partida. Cada una de las ocho secuencias de 3 dígitos (correspondientes a los ocho vértices) aparece exactamente dos veces, y cada una de las dieciséis secuencias de 4 dígitos (correspondientes a los 16 bordes) aparece exactamente una vez.
Ejemplo de utilización de Burrows inversas — Transformada de Wheeler
Matemáticamente, una transformación inversa de Burrows-Wheeler en una palabra w genera un conjunto múltiple de clases de equivalencia que consta de cadenas y sus rotaciones. [7] Cada una de estas clases de equivalencia de cadenas contiene una palabra Lyndon como elemento mínimo único, por lo que se puede considerar que la transformada inversa Burrows-Wheeler genera un conjunto de palabras Lyndon. Se puede demostrar que si realizamos la transformada inversa de Burrows-Wheeler en una palabra w que consta del alfabeto de tamaño k repetido k n-1 veces (de modo que producirá una palabra de la misma longitud que la secuencia de Bruijn deseada), entonces el resultado será el conjunto de todas las palabras de Lyndon cuya longitud divide n. De ello se deduce que ordenar estas palabras de Lyndon en orden lexicográfico producirá una secuencia de De Bruijn B (k, n), y que esta será la primera secuencia de De Bruijn en orden lexicográfico. El siguiente método se puede utilizar para realizar la transformación inversa Burrows-Wheeler, utilizando su permutación estándar :
- Ordene los caracteres en la cadena w , produciendo una nueva cadena w '
- Coloque la cuerda w ' encima de la cuerda w , y asigne la posición de cada letra en w' a su posición en w manteniendo el orden. Este proceso define la permutación estándar .
- Escriba esta permutación en notación de ciclo con la posición más pequeña en cada ciclo primero, y los ciclos ordenados en orden creciente.
- Para cada ciclo, reemplace cada número con la letra correspondiente de la cadena w ' en esa posición.
- Cada ciclo se ha convertido ahora en una palabra de Lyndon, y están organizados en orden lexicográfico, por lo que al eliminar los paréntesis se obtiene la primera secuencia de De Bruijn.
Por ejemplo, para construir la secuencia B (2,4) de Bruijn más pequeña de longitud 2 4 = 16, repita el alfabeto (ab) 8 veces para obtener w = abababababababab. Ordene los caracteres en w , obteniendo w '= aaaaaaaabbbbbbbb. Coloque w ' encima de w como se muestra, y mapee cada elemento en w ' con el elemento correspondiente en w dibujando una línea. Numere las columnas como se muestra para que podamos leer los ciclos de la permutación:
Comenzando por la izquierda, los ciclos de notación de permutación estándar son: (1) (2 3 5 9) (4 7 13 10) (6 11) (8 15 14 12) (16). ( Permutación estándar )
Luego, reemplazando cada número por la letra correspondiente en w 'de esa columna, se obtiene: (a) (aaab) (aabb) (ab) (abbb) (b).
Estas son todas las palabras de Lyndon cuya longitud divide 4, en orden lexicográfico, por lo que eliminar el paréntesis da B (2,4) = aaaabaabbababbbb.
Algoritmo
La siguiente Python código calcula una secuencia de Bruijn, dado k y n , con base en un algoritmo de Frank Ruskey 's combinatoria Generación . [10]
de escribir import Iterable , Union , Any def de_bruijn ( k : Union [ Iterable [ Any ], int ], n : int ) -> str : "" "secuencia de Bruijn para el alfabeto k y subsecuencias de longitud n. " "" # Dos tipos de entrada alfabética: un número entero se expande # a una lista de números enteros como el alfabeto .. if isinstance ( k , int ): alphabet = list ( map ( str , range ( k ))) else : # Mientras que cualquier tipo de lista se usa tal cual alfabeto = k k = len ( k ) a = [ 0 ] * k * n secuencia = [] def db ( t , p ): si t > n : si n % p == 0 : secuencia . extender ( a [ 1 : p + 1 ]) más : a [ t ] = a [ t - p ] db ( t + 1 , p ) para j en el rango ( a [ t - p ] + 1 , k ): a [ t ] = j db ( t + 1 , t ) db ( 1 , 1 ) devuelve "" . unirse ( alfabeto [ i ] para i en secuencia )imprimir ( de_bruijn ( 2 , 3 )) imprimir ( de_bruijn ( "abcd" , 2 ))
que imprime
00010111aabacadbbcbdccdd
Tenga en cuenta que se entiende que estas secuencias se "envuelven" en un ciclo. Por ejemplo, la primera secuencia contiene 110 y 100 de esta manera.
Usos
B {10,3} con dígitos leídos de arriba a abajo y luego de izquierda a derecha; [11] al agregar "00" se obtiene una cadena para forzar bruta una cerradura de combinación de 3 dígitos | |||||||||
0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 |
001 | |||||||||
002 | |||||||||
003 | |||||||||
004 | |||||||||
005 | |||||||||
006 | |||||||||
007 | |||||||||
008 | |||||||||
009 | |||||||||
011 | |||||||||
012 | 112 | ||||||||
013 | 113 | ||||||||
014 | 114 | ||||||||
015 | 115 | ||||||||
016 | 116 | ||||||||
017 | 117 | ||||||||
018 | 118 | ||||||||
019 | 119 | ||||||||
021 | |||||||||
022 | 122 | ||||||||
023 | 123 | 223 | |||||||
024 | 124 | 224 | |||||||
025 | 125 | 225 | |||||||
026 | 126 | 226 | |||||||
027 | 127 | 227 | |||||||
028 | 128 | 228 | |||||||
029 | 129 | 229 | |||||||
031 | |||||||||
032 | 132 | ||||||||
033 | 133 | 233 | |||||||
034 | 134 | 234 | 334 | ||||||
035 | 135 | 235 | 335 | ||||||
036 | 136 | 236 | 336 | ||||||
037 | 137 | 237 | 337 | ||||||
038 | 138 | 238 | 338 | ||||||
039 | 139 | 239 | 339 | ||||||
041 | |||||||||
042 | 142 | ||||||||
043 | 143 | 243 | |||||||
044 | 144 | 244 | 344 | ||||||
045 | 145 | 245 | 345 | 445 | |||||
046 | 146 | 246 | 346 | 446 | |||||
047 | 147 | 247 | 347 | 447 | |||||
048 | 148 | 248 | 348 | 448 | |||||
049 | 149 | 249 | 349 | 449 | |||||
051 | |||||||||
052 | 152 | ||||||||
053 | 153 | 253 | |||||||
054 | 154 | 254 | 354 | ||||||
055 | 155 | 255 | 355 | 455 | |||||
056 | 156 | 256 | 356 | 456 | 556 | ||||
057 | 157 | 257 | 357 | 457 | 557 | ||||
058 | 158 | 258 | 358 | 458 | 558 | ||||
059 | 159 | 259 | 359 | 459 | 559 | ||||
061 | |||||||||
062 | 162 | ||||||||
063 | 163 | 263 | |||||||
064 | 164 | 264 | 364 | ||||||
065 | 165 | 265 | 365 | 465 | |||||
066 | 166 | 266 | 366 | 466 | 566 | ||||
067 | 167 | 267 | 367 | 467 | 567 | 667 | |||
068 | 168 | 268 | 368 | 468 | 568 | 668 | |||
069 | 169 | 269 | 369 | 469 | 569 | 669 | |||
071 | |||||||||
072 | 172 | ||||||||
073 | 173 | 273 | |||||||
074 | 174 | 274 | 374 | ||||||
075 | 175 | 275 | 375 | 475 | |||||
076 | 176 | 276 | 376 | 476 | 576 | ||||
077 | 177 | 277 | 377 | 477 | 577 | 677 | |||
078 | 178 | 278 | 378 | 478 | 578 | 678 | 778 | ||
079 | 179 | 279 | 379 | 479 | 579 | 679 | 779 | ||
081 | |||||||||
082 | 182 | ||||||||
083 | 183 | 283 | |||||||
084 | 184 | 284 | 384 | ||||||
085 | 185 | 285 | 385 | 485 | |||||
086 | 186 | 286 | 386 | 486 | 586 | ||||
087 | 187 | 287 | 387 | 487 | 587 | 687 | |||
088 | 188 | 288 | 388 | 488 | 588 | 688 | 788 | ||
089 | 189 | 289 | 389 | 489 | 589 | 689 | 789 | 889 | |
091 | |||||||||
092 | 192 | ||||||||
093 | 193 | 293 | |||||||
094 | 194 | 294 | 394 | ||||||
095 | 195 | 295 | 395 | 495 | |||||
096 | 196 | 296 | 396 | 496 | 596 | ||||
097 | 197 | 297 | 397 | 497 | 597 | 697 | |||
098 | 198 | 298 | 398 | 498 | 598 | 698 | 798 | ||
099 | 199 | 299 | 399 | 499 | 599 | 699 | 799 | 899 | (00) |
La secuencia se puede utilizar para acortar un ataque de fuerza bruta en un bloqueo de código similar a un PIN que no tiene una tecla "enter" y acepta los últimos n dígitos ingresados. Por ejemplo, una cerradura de puerta digital con un código de 4 dígitos (cada dígito tiene 10 posibilidades, de 0 a 9) tendría soluciones B (10, 4), con longitud10 000 . Por lo tanto, solo como máximo10 000 + 3 =Se necesitan 10 003 (ya que las soluciones son cíclicas) prensas para abrir la cerradura. Probar todos los códigos por separado requeriría 4 ×10 000 =40 000 prensas.
Los símbolos de una secuencia de De Bruijn escritos alrededor de un objeto circular (como la rueda de un robot ) se pueden usar para identificar su ángulo examinando los n símbolos consecutivos que miran hacia un punto fijo. Este problema de codificación de ángulos se conoce como el "problema del tambor giratorio". [12] Los códigos Gray se pueden utilizar como mecanismos de codificación posicional rotativos similares.
Los ciclos de De Bruijn son de uso general en experimentos de neurociencia y psicología que examinan el efecto del orden de los estímulos sobre los sistemas neuronales, [13] y pueden diseñarse especialmente para su uso con imágenes de resonancia magnética funcional . [14]
Se puede usar una secuencia de Bruijn para encontrar rápidamente el índice del bit de conjunto menos significativo ("1 más a la derecha") o el bit de conjunto más significativo ("1 más a la izquierda") en una palabra usando operaciones bit a bit . [15] A continuación se muestra un ejemplo de cómo devolver el índice del bit menos significativo de un entero de 32 bits sin signo utilizando la manipulación y la multiplicación de bits .
unsigned int v ; int r ; static const int MultiplyDeBruijnBitPosition [ 32 ] = { 0 , 1 , 28 , 2 , 29 , 14 , 24 , 3 , 30 , 22 , 20 , 15 , 25 , 17 , 4 , 8 , 31 , 27 , 13 , 23 , 21 , 19 , 16 , 7 , 26 , 12 , 18 , 6 , 11 , 5 , 10 , 9 }; r = MultiplyDeBruijnBitPosition [(( uint32_t ) (( v & - v ) * 0x077CB531U )) >> 27 ];
El índice del LSB en v se almacena en r y si v no tiene bits establecidos, la operación devuelve 0. La constante, 0x077CB531U, en la expresión es la secuencia B (2, 5) 0000 0111 0111 1100 1011 0101 0011 0001 (espacios agregado para mayor claridad).
A continuación se ofrece un ejemplo de cómo devolver el índice del conjunto de bits más significativo de un entero sin signo de 32 bits utilizando la manipulación y la multiplicación de bits .
uint32_t keepHighestBit ( uint32_t n ) { n | = ( n >> 1 ); n | = ( n >> 2 ); n | = ( n >> 4 ); n | = ( n >> 8 ); n | = ( n >> 16 ); devuelve n - ( n >> 1 ); }uint8_t maximumBitIndex ( uint32_t b ) { estática const uint32_t deBruijnMagic = 0x06EB14F9 ; static const uint8_t deBruijnTable [ 32 ] = { 0 , 1 , 16 , 2 , 29 , 17 , 3 , 22 , 30 , 20 , 18 , 11 , 13 , 4 , 7 , 23 , 31 , 15 , 28 , 21 , 19 , 10 , 12 , 6 , 14 , 27 , 9 , 5 , 26 , 8 , 25 , 24 , }; return deBruijnTable [( keepHighestBit ( b ) * deBruijnMagic ) >> 27 ]; }
Secuencias de F-fold de Bruijn
f-fold n-ary de Bruijn sequence ' es una extensión de la noción n- ary de Bruijn secuencia, de modo que la secuencia de la longitudcontiene todas las subsecuencias posibles de la longitud n exactamente f veces. Por ejemplo, paralas secuencias cíclicas 11100010 y 11101000 son secuencias de Bruijn binarias dobles. El número de secuencias de Bruijn dobles, por es , los otros números conocidos [16] son, , y .
De Bruijn torus
Un toro de De Bruijn es una matriz toroidal con la propiedad de que cada matriz k -ary m -by- n ocurre exactamente una vez.
Un patrón de este tipo se puede utilizar para la codificación posicional bidimensional de una manera análoga a la descrita anteriormente para la codificación rotatoria. La posición se puede determinar examinando la matriz m por n directamente adyacente al sensor y calculando su posición en el toro de Bruijn.
Decodificación de De Bruijn
Calcular la posición de una tupla o matriz única particular en una secuencia o toro de De Bruijn se conoce como el problema de decodificación de de Bruijn. Existen algoritmos de decodificación de O (n log n) eficientes para secuencias especiales construidas de forma recursiva [17] y se extienden al caso bidimensional. [18] La decodificación de De Bruijn es de interés, por ejemplo, en los casos en los que se utilizan grandes secuencias o toros para la codificación posicional.
Ver también
- Gráfico de Bruijn
- De Bruijn torus
- Número normal
- Registro de desplazamiento de retroalimentación lineal
- n- secuencia
- MEJOR teorema
Notas
- ↑ a b c de Bruijn (1975) .
- ^ Giles, C. Lee; Horne, Bill G .; Lin, Tsungnan (1995). "Aprendiendo una clase de grandes máquinas de estados finitos con una red neuronal recurrente" (PDF) . Redes neuronales . 8 (9): 1359-1365. doi : 10.1016 / 0893-6080 (95) 00041-0 .
- ↑ Brown (1869) ; Stein (1963) ; Kak (2000) ; Knuth (2006) ; Hall (2008) .
- ^ Popper (2002) .
- ^ Klein (2013) .
- ↑ Según Berstel & Perrin (2007) , la secuencia generada de esta manera fue descrita por primera vez (con un método de generación diferente) por Martin (1934) , y la conexión entre ella y las palabras de Lyndon fue observada por Fredricksen & Maiorana (1978) .
- ↑ a b Higgins (2012) .
- ^ Goresky y Klapper (2012) .
- ^ Ralston (1982) , págs. 136-139.
- ^ "Secuencias de De Bruijn" . Sage . Consultado el 3 de noviembre de 2016 .
- ^ http://hakank.org/comb/debruijn.cgi?k=10&n=3
- ↑ van Lint y Wilson (2001) .
- ^ Aguirre, Mattar y Magis-Weinberg (2011) .
- ^ "Generador de ciclo De Bruijn" .
- ^ Anderson (1997-2009) ; Busch (2009)
- ^ Osipov (2016) .
- ^ Tuliani (2001) .
- ^ Hurlbert e Isaak (1993) .
Referencias
- van Aardenne-Ehrenfest, Tanja ; de Bruijn, Nicolaas Govert (1951). "Circuitos y árboles en grafos lineales orientados" (PDF) . Simon Stevin . 28 : 203–217. Señor 0047311 .
- Aguirre, GK; Mattar, MG; Magis-Weinberg, L. (2011). "Ciclos de Bruijn para decodificación neuronal" . NeuroImage . 56 (3): 1293-1300. doi : 10.1016 / j.neuroimage.2011.02.005 . PMC 3104402 . PMID 21315160 .
- Anderson, Sean Eron (1997-2009). "Bit Twiddling Hacks" . Universidad de Stanford . Consultado el 12 de febrero de 2009 .
- Berstel, Jean ; Perrin, Dominique (2007). "Los orígenes de la combinatoria sobre palabras" (PDF) . Revista europea de combinatoria . 28 (3): 996–1022. doi : 10.1016 / j.ejc.2005.07.019 . Señor 2300777 .
- Brown, CP (1869). Explicación de la prosodia sánscrita y los símbolos numéricos . pag. 28.
- de Bruijn, Nicolaas Govert (1946). "Un problema combinatorio" (PDF) . Proc. Koninklijke Nederlandse Akademie V. Wetenschappen . 49 : 758–764. MR 0018142 , Indagationes Mathematicae 8 : 461–467CS1 maint: posdata ( enlace )
- de Bruijn, Nicolaas Govert (1975). "Reconocimiento de prioridad a C. Flye Sainte-Marie en el recuento de arreglos circulares de 2 n ceros y unos que muestran cada palabra de n letras exactamente una vez" (PDF) . Informe TH 75-WSK-06. Universidad Tecnológica de Eindhoven. Cite journal requiere
|journal=
( ayuda ) - Busch, Philip (2009). "Cómo calcular ceros finales" . Consultado el 29 de enero de 2015 .
- Flye Sainte-Marie, Camille (1894). "Solución a la pregunta nº 48". L'Intermédiaire des Mathématiciens . 1 : 107-110.
- Goresky, Mark ; Klapper, Andrew (2012). "8.2.5 Generación de registro de desplazamiento de secuencias de Bruijn". Secuencias de registro de desplazamiento algebraico . Prensa de la Universidad de Cambridge . págs. 174-175. ISBN 978-1-10701499-2.
- Hall, Rachel W. (2008). "Matemáticas para poetas y bateristas" (PDF) . Horizontes de matemáticas . 15 (3): 10-11. doi : 10.1080 / 10724117.2008.11974752 . S2CID 3637061 . Archivado desde el original (PDF) el 12 de febrero de 2012 . Consultado el 22 de octubre de 2008 .
- Higgins, Peter (noviembre de 2012). "Burrows-Wheeler transforma y de Bruijn palabras" (PDF) . Consultado el 11 de febrero de 2017 .
- Hurlbert, Glenn; Isaak, Garth (1993). "Sobre el problema del toro de Bruijn" . Revista de teoría combinatoria . Serie A. 64 (1): 50–62. doi : 10.1016 / 0097-3165 (93) 90087-O . Señor 1239511 .
- Kak, Subhash (2000). "Yamātārājabhānasalagāṃ un interesante sūtra combinatorio" (PDF) . Revista India de Historia de la Ciencia . 35 (2): 123-127. Archivado desde el original (PDF) el 29 de octubre de 2014.
- Klein, Andreas (2013). Stream Ciphers . Saltador. pag. 59. ISBN 978-1-44715079-4.
- Knuth, Donald Ervin (2006). El arte de la programación informática, fascículo 4: Generación de todos los árboles - Historia de la generación combinatoria . Addison – Wesley . pag. 50. ISBN 978-0-321-33570-8.
- Fredricksen, Harold; Maiorana, James (1978). "Collares de abalorios en k colores y secuencias k -ary de Bruijn". Matemáticas discretas . 23 (3): 207–210. doi : 10.1016 / 0012-365X (78) 90002-X . Señor 0523071 .
- Martin, Monroe H. (1934). "Un problema en los arreglos" (PDF) . Boletín de la American Mathematical Society . 40 (12): 859–864. doi : 10.1090 / S0002-9904-1934-05988-3 . Señor 1562989 .
- Osipov, Vladimir (2016). "Análisis de ondas en secuencias simbólicas y secuencias de Bruijn de dos partes". Revista de física estadística . 164 (1): 142-165. arXiv : 1601.02097 . Código bibliográfico : 2016JSP ... 164..142O . doi : 10.1007 / s10955-016-1537-5 . ISSN 1572-9613 . S2CID 16535836 .
- Popper, Karl (2002) [1934]. La lógica del descubrimiento científico . Routledge. pag. 294. ISBN 978-0-415-27843-0.
- Ralston, Anthony (1982). "Secuencias de Bruijn: un ejemplo modelo de la interacción de las matemáticas discretas y la informática". Revista de Matemáticas . 55 (3): 131–143. doi : 10.2307 / 2690079 . JSTOR 2690079 . Señor 0653429 .
- Stein, Sherman K. (1963). "Yamátárájabhánasalagám". El universo creado por el hombre: una introducción al espíritu de las matemáticas . págs. 110-118.Reimpreso en Wardhaugh, Benjamin, ed. (2012), A Wealth of Numbers: An Anthology of 500 Years of Popular Mathematics Writing , Princeton University Press , págs. 139-144.
- Tuliani, Jonathan (2001). "Secuencias de Bruijn con algoritmos de decodificación eficientes". Matemáticas discretas . 226 (1-3): 313-336. doi : 10.1016 / S0012-365X (00) 00117-5 . Señor 1802599 .
- van Lint, JH ; Wilson, Richard Michael (2001). Un curso de combinatoria . Prensa de la Universidad de Cambridge . pag. 71. ISBN 978-0-52100601-9.
enlaces externos
- Weisstein, Eric W. "de Bruijn Sequence" . MathWorld .
- Secuencia OEIS A166315 (secuencias de Bruijn binarias lexicográficamente más pequeñas)
- Secuencia de De Bruijn
- Generador CGI
- Generador de applets
- Generador y decodificador de Javascript . Implementación del algoritmo de J. Tuliani.
- Cerradura con código de puerta
- Matrices mínimas que contienen todas las combinaciones de submatriz de símbolos: secuencias de De Bruijn y tori