последовательность де Брейна

Не путать с последовательностью Мозера-де Брюйна , целочисленной последовательностью из теории чисел .

Последовательность де Брейна для размера алфавита k = 2 и длины подстроки n = 2 . Вообще существует множество последовательностей для конкретных n и k, но в данном примере они уникальны, с точностью до цикличности.

В комбинаторной математике последовательность де Брейна порядка n размера k в алфавите A представляет собой циклическую последовательность , в которой каждая возможная длины n строка в A встречается ровно один раз как подстрока (т. е. как непрерывная подпоследовательность ). Такая последовательность обозначается B ( k , n ) и имеет длину k ^н , что также является количеством различных строк длины n в A . Каждая из этих отдельных строк, взятая как подстрока B ( k , n ) , должна начинаться с другой позиции, поскольку подстроки, начинающиеся с одной и той же позиции, не различны. Следовательно, B ( k , n ) должно иметь не менее k ^н символы. А поскольку B ( k , n ) имеет ровно k ^н символов, последовательности де Брейна оптимально коротки с точки зрения свойства содержать каждую строку длины n хотя бы один раз.

Число различных последовательностей де Брейна B ( k , n ) равно

${\dfrac {\left(k!\right)^{k^{n-1}}}{k^{n}}}.$

Последовательности названы в честь голландского математика Николааса Говерта де Брейна , написавшего о них в 1946 году. Как он позже писал, существование последовательностей де Брейна для каждого порядка вместе с указанными выше свойствами было впервые доказано для случая алфавитов с двумя элементами Камиллой Флай Сент-Мари ( 1894 ). Обобщение на более крупные алфавиты принадлежит Татьяне ван Аарденн-Эренфест и де Брюйну ( 1951 ). Автоматы , распознающие эти последовательности, называются автоматами де Брейна.

В большинстве приложений A = {0,1}.

История

Самый ранний известный пример последовательности де Брёйна взят из санскритской просодии , где, начиная с работы Пингалы , каждому возможному трехсложному образцу длинных и коротких слогов дается имя, например «y» для короткого-долгого-долгого и «y». м' долго-долго-долго. Чтобы запомнить эти имена, используется мнемоника яматараджабханасалагам , в которой каждая трехсложная модель начинается с ее имени: «ямата» имеет образец «короткий-длинный-длинный», «матара» имеет образец «длинный-длинный-длинный», и так дальше, пока не произойдет «салагам», который имеет структуру «короткий-короткий-длинный». Эта мнемоника, эквивалентная последовательности де Брейна на двоичных тройках, имеет неизвестную древность, но по крайней мере так же стара, как книга Чарльза Филипа Брауна по санскритской просодии 1869 года, в которой она упоминается и считается «древней строкой, написанной Панини ».

В 1894 году А. де Ривьер в номере французского проблемного журнала L'Intermédiaire des Mathématiciens поднял вопрос о существовании кругового расположения нулей и единиц размера $2^{n}$ который содержит все $2^{n}$ двоичные последовательности длины $n$. Задача была решена (положительно) вместе с подсчетом $2^{2^{n-1}-n}$ отдельные решения Камиллы Флай Сент-Мари в том же году. Об этом в значительной степени забыли, и Мартин (1934) доказал существование таких циклов для общего размера алфавита вместо 2 с алгоритмом их построения. Наконец, когда в 1944 году Кес Постумус предположил, что счет $2^{2^{n-1}-n}$ для двоичных последовательностей де Брейн доказал эту гипотезу в 1946 году, благодаря чему проблема стала широко известна.

Карл Поппер независимо описывает эти объекты в своей «Логике научных открытий» (1934), называя их «кратчайшими случайными последовательностями».

Примеры

• Если взять A = {0, 1}, то получится два различных числа B (2, 3): 00010111 и 11101000, одно из которых является обратным или отрицанием другого.
• Две из 16 возможных букв B (2, 4) в одном алфавите — это 0000100110101111 и 0000111101100101.
• Две из 2048 возможных букв B (2, 5) в одном алфавите — это 00000100011001010011101011011111 и 00000101001000111110111001101011.

Строительство

Граф де Брёйна. Каждая четырехзначная последовательность встречается ровно один раз, если пройти каждое ребро ровно один раз и вернуться в исходную точку (эйлеров цикл). Каждая трехзначная последовательность встречается ровно один раз, если каждую вершину посещают ровно один раз (гамильтонов путь).

взяв гамильтонов путь n Последовательности де Брейна можно построить , -мерного графа де Брейна над k символами (или, что то же самое, эйлеров цикл ( n - 1)-мерного графа де Брейна).

Альтернативная конструкция предполагает объединение в лексикографическом порядке всех слов Линдона , длина которых делит n .

Обратное преобразование Берроуза – Уиллера можно использовать для генерации необходимых слов Линдона в лексикографическом порядке.

Последовательности де Брейна также можно построить с использованием сдвиговых регистров. или через конечные поля .

Пример использования графа де Брёйна

Ориентированные графы двух B (2,3) последовательностей де Брейна и B (2,4) последовательности. В B (2,3) каждая вершина посещается один раз, тогда как в B (2,4) каждое ребро проходится один раз.

Цель: построить B (2, 4) последовательность де Брейна длины 2. ⁴ = 16 с использованием эйлерова ( n - 1 = 4 - 1 = 3) трехмерного цикла графа де Брейна.

Каждое ребро в этом трехмерном графе де Брёйна соответствует последовательности из четырех цифр: три цифры, обозначающие вершину, из которой выходит ребро, за которыми следует цифра, обозначающая ребро. Если пройти ребро, помеченное 1, от 000, то мы придем к 001, тем самым указывая на наличие подпоследовательности 0001 в последовательности де Брёйна. Чтобы пройти каждое ребро ровно один раз, нужно использовать каждую из 16 четырехзначных последовательностей ровно один раз.

Например, предположим, что мы следуем по следующему эйлерову пути через эти вершины:

000, 000, 001, 011, 111, 111, 110, 101, 011,

110, 100, 001, 010, 101, 010, 100, 000.

Это выходные последовательности длины k :

0 0 0 0

_ 0 0 0 1

_ _ 0 0 1 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 ...   ... 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 ...

...и затем мы возвращаемся в исходную точку. Каждая из восьми трехзначных последовательностей (соответствующих восьми вершинам) появляется ровно два раза, а каждая из шестнадцати четырехзначных последовательностей (соответствующих 16 ребрам) появляется ровно один раз.

Пример использования обратного преобразования Берроуза — Уиллера

Математически обратное преобразование Берроуза-Уиллера для слова w генерирует мультимножество классов эквивалентности, состоящее из строк и их вращений. Каждый из этих классов эквивалентности строк содержит слово Линдона в качестве уникального минимального элемента, поэтому можно считать, что обратное преобразование Берроуза-Уиллера генерирует набор слов Линдона. Можно показать, что если мы выполним обратное преобразование Берроуза-Уиллера для слова w, состоящего из алфавита размера k, повторяющегося k ^{п -1} раз (так что получится слово той же длины, что и желаемая последовательность де Брёйна), то результатом будет набор всех слов Линдона, длина которых делит n . Отсюда следует, что расположение этих слов Линдона в лексикографическом порядке даст последовательность де Брейна B ( k , n ), и что это будет первая последовательность де Брейна в лексикографическом порядке. Следующий метод можно использовать для выполнения обратного преобразования Берроуза-Уиллера с использованием его стандартной перестановки :

1. Отсортируйте символы в строке w , получив новую строку w ′
2. Поместите строку w ′ над строкой w и сопоставьте положение каждой буквы в w ′ с ее позицией в w , сохраняя порядок. Этот процесс определяет стандартную перестановку .
3. Запишите эту перестановку в обозначениях циклов, начиная с наименьшей позиции в каждом цикле, а циклы отсортируйте в порядке возрастания.
4. Для каждого цикла замените каждое число соответствующей буквой из строки w ′ в этой позиции.
5. Каждый цикл теперь стал словом Линдона, и они расположены в лексикографическом порядке, поэтому после удаления скобок получается первая последовательность де Брейна.

Например, чтобы построить наименьшую B (2,4) последовательность де Брейна длины 2 ⁴ = 16, повторите алфавит (ab) 8 раз, получив w =ababababababab . Отсортируйте символы в w , получив w ′ =aaaaaaaabbbbbbb . Расположите w ′ над w, как показано, и сопоставьте каждый элемент w ′ соответствующему элементу w , нарисовав линию. Пронумеруйте столбцы, как показано, чтобы мы могли прочитать циклы перестановки:

Начиная слева, циклы обозначений стандартной перестановки: (1) (2 3 5 9) (4 7 13 10) (6 11) (8 15 14 12) (16) . ( Стандартная перестановка )

Затем замена каждого числа соответствующей буквой в w ′ из этого столбца дает: (a)(aaab)(aabb)(ab)(abbb)(b) .

Это все слова Линдона, длина которых делится на 4 в лексикографическом порядке, поэтому удаление скобок дает B (2,4) = aaaabaabbababbbb .

Алгоритм

Следующий код Python вычисляет последовательность де Брёйна по заданным k и n на основе алгоритма из Фрэнка Раски » «Комбинаторной генерации .

from typing import Iterable, Union, Anydef de_bruijn(k: Union[Iterable[str], int], n: int) -> str:    """de Bruijn sequence for alphabet k    and subsequences of length n.    """    # Two kinds of alphabet input: an integer expands    # to a list of integers as the alphabet..    if isinstance(k, int):        alphabet = list(map(str, range(k)))    else:        # While any sort of list becomes used as it is        alphabet = k        k = len(k)    a = [0] * k * n    sequence = []    def db(t, p):        if t > n:            if n % p == 0:                sequence.extend(a[1 : p + 1])        else:            a[t] = a[t - p]            db(t + 1, p)            for j in range(a[t - p] + 1, k):                a[t] = j                db(t + 1, t)    db(1, 1)    return "".join(alphabet[i] for i in sequence)print(de_bruijn(2, 3))print(de_bruijn("abcd", 2))

который печатает

00010111aabacadbbcbdccdd

Обратите внимание, что эти последовательности считаются «зацикливающимися» в цикле. Например, первая последовательность таким образом содержит 110 и 100.

Использование

Циклы де Брейна широко используются в нейробиологических и психологических экспериментах, изучающих влияние порядка стимулов на нервные системы. и может быть специально разработан для использования с функциональной магнитно-резонансной томографией .

Обнаружение угла

Символы последовательности де Брейна, написанные вокруг круглого объекта (например, колеса робота ) , можно использовать для определения его угла , исследуя n последовательных символов, обращенных к фиксированной точке. Эта проблема кодирования угла известна как «проблема вращающегося барабана». Коды Грея могут использоваться в качестве аналогичных механизмов поворотного позиционного кодирования - метод, обычно встречающийся в поворотных энкодерах .

Поиск наименее или наиболее значимого бита в слове

Последовательность де Брюйна можно использовать для быстрого поиска индекса младшего бита набора («самая правая 1») или самого старшего бита набора («самая левая 1») в слове с использованием поразрядных операций и умножения. В следующем примере используется последовательность де Брейна для определения индекса младшего значащего установленного бита (эквивалентно подсчету количества конечных нулевых битов) в 32-битном беззнаковом целом числе:

uint8_t lowestBitIndex(uint32_t v){         static const uint8_t BitPositionLookup[32] = // hash table  {    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  };  return BitPositionLookup[((uint32_t)((v & -v) * 0x077CB531U)) >> 27];}

The lowestBitIndex() Функция возвращает индекс младшего установленного бита в v или ноль, если v не имеет установленных битов. Константа 0x077CB531U в выражении представляет собой последовательность B (2, 5) 0000 0111 0111 1100 1011 0101 0011 0001 (пробелы добавлены для ясности). Операция (v & -v) обнуляет все биты, кроме набора наименее значащих битов, в результате чего получается новое значение, которое представляет собой степень 2. Эта степень 2 умножается (арифметика по модулю 2 ³² ) с помощью последовательности де Брейна, создавая таким образом 32-битное произведение, в котором битовая последовательность 5 старших битов уникальна для каждой степени двойки. 5 старших битов сдвигаются в позиции младших битов для создания хэш-кода в диапазоне [0 , 31], который затем используется как индекс в хэш-таблице BitPositionLookup. Выбранное значение хэш-таблицы представляет собой битовый индекс наименее значимого установленного бита в v .

В следующем примере определяется индекс старшего бита, установленного в 32-битном беззнаковом целом:

uint32_t keepHighestBit(uint32_t n){    n |= (n >>  1);    n |= (n >>  2);    n |= (n >>  4);    n |= (n >>  8);    n |= (n >> 16);    return n - (n >> 1);}uint8_t highestBitIndex(uint32_t v){    static const uint8_t BitPositionLookup[32] = { // hash table         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 BitPositionLookup[(keepHighestBit(v) * 0x06EB14F9U) >> 27];}

В приведенном выше примере используется альтернативная последовательность де Брейна (0x06EB14F9U) с соответствующим переупорядочением значений массива. Выбор этой конкретной последовательности де Брейна произволен, но значения хеш-таблицы должны быть упорядочены так, чтобы соответствовать выбранной последовательности де Брейна. keepHighestBit() Функция обнуляет все биты, кроме самого старшего установленного бита, в результате чего получается значение, равное степени 2, которое затем обрабатывается, как в предыдущем примере.

Атаки грубой силы на замки

Одна возможная последовательность B (10, 4). Подстроки 2530 читаются сверху вниз, затем слева направо, и их цифры объединяются. Чтобы получить строку для взлома кодового замка, добавляются последние три цифры в скобках (000). Связана 10003 цифра составляет «0 0001 0002 0003 0004 0005 0006 0007 0008 0009 0011 ... 79 7988 7989 7998 7999 8 8889 8899 89 8999 9 000» (пространства для читаемости).

показывать B{10,3}, цифры читаются сверху вниз. затем слева направо; добавление «00» дает строка для взлома трехзначного кодового замка
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)

Последовательность де Брейна можно использовать для сокращения грубой атаки на PIN -кодовый замок, который не имеет клавиши «ввода» и принимает последние введенные n цифр. Например, цифровой дверной замок с 4-значным кодом (каждая цифра имеет 10 вариантов, от 0 до 9) будет иметь решения B (10, 4) длиной 10 000 . Следовательно, для открытия замка необходимо не более 10 000 + 3 = 10 003 (поскольку решения циклические) нажатий, тогда как для проверки всех кодов по отдельности потребуется 4 × 10 000 = 40 000 нажатий.

Упрощенный принцип работы цифровой ручки Anoto.
Камера определяет матрицу точек размером 6×6, каждая из которых смещена от синей сетки (не напечатана) в одном из 4 направлений.
Комбинации относительных смещений 6-битной последовательности де Брейна между столбцами и между строками дают ее абсолютное положение на цифровой бумаге.

f-кратные последовательности де Брейна

f -кратная n-арная последовательность де Брейна является расширением понятия n -арной последовательности де Брейна, так что последовательность длины $fk^{n}$ содержит все возможные подпоследовательности длины n ровно f раз. Например, для $n=2$ циклические последовательности 11100010 и 11101000 представляют собой двукратные двоичные последовательности де Брейна. Число двукратных последовательностей де Брейна, $N_{n}$ для $n=1$ является $N_{1}=2$, другие известные числа являются $N_{2}=5$, $N_{3}=72$, и $N_{4}=43768$.

тор де Брёйна

STL- модель тора де Брейна (16,32;3,3) ₂ с единицами в виде панелей и нулями в виде отверстий в сетке - при последовательной ориентации каждая матрица 3×3 появляется ровно один раз.

Основная статья: Тор Де Брейна

Тор де Брёйна свойство которого состоит в том, что каждая k -арная матрица m -n — это тороидальный массив , встречается ровно один раз.

Такой шаблон можно использовать для двумерного позиционного кодирования способом, аналогичным описанному выше для ротационного кодирования. Положение можно определить, исследуя матрицу m - n , непосредственно примыкающую к датчику, и вычисляя ее положение на торе де Брёйна.

расшифровка де Брёйна

Вычисление позиции конкретного уникального кортежа или матрицы в последовательности или торе де Брейна известно как проблема декодирования де Брейна . Эффективно ⁠ $\color {Blue}O(n\log n)$⁠ алгоритмы декодирования существуют для специальных рекурсивно построенных последовательностей. и распространяется на двумерный случай. Декодирование де Брейна представляет интерес, например, в тех случаях, когда для позиционного кодирования используются большие последовательности или торы.

См. также

• Нормальный номер
• Регистр сдвига с линейной обратной связью
• n -последовательность
• ЛУЧШАЯ теорема
• Суперперестановка

Ссылки

• ван Аарденне-Эренфест, Таня ; де Брейн, Николаас Говерт (1951). «Схемы и деревья в ориентированных линейных графах» (PDF) . Саймон Стевин . 28 : 203–217. МР   0047311 .
• Агирре, ГК; Маттар, Миннесота; Магис-Вайнберг, Л. (2011). «Циклы де Брейна для нейронного декодирования» . НейроИмидж . 56 (3): 1293–1300. doi : 10.1016/j.neuroimage.2011.02.005 . ПМК   3104402 . ПМИД   21315160 . Архивировано из оригинала 26 января 2016 г. Проверено 4 июня 2015 г.
• Андерсон, Шон Эрон (1997–2009). «Битл-хаки» . Стэнфордский университет . Проверено 12 февраля 2009 г.
• Берстель, Жан ; Перрен, Доминик (2007). «Истоки комбинаторики слов» (PDF) . Европейский журнал комбинаторики . 28 (3): 996–1022. дои : 10.1016/j.ejc.2005.07.019 . МР   2300777 .
• Браун, CP (1869). Объяснение санскритской просодии и числовых символов . п. 28.
• де Брейн, Николаас Говерт (1946). «Комбинаторная задача» (PDF) . Учеб. Королевская Нидерландская академия V. наук . 49 : 758–764. MR   0018142 , Indagationes Mathematicae 8 : 461–467. {{cite journal}}: CS1 maint: постскриптум ( ссылка )
• де Брейн, Николаас Говерт (1975). Подтверждение приоритета К. Флай Сент-Мари при подсчете круговых договоренностей из 2 ^н нули и единицы, которые показывают каждое слово из n букв ровно один раз (PDF) . TH-Отчет 75-WSK-06. Технологический университет Эйндховена.
• Буш, Филип (2009). «Практическое руководство по вычислению конечных нулей» . Архивировано из оригинала 29 января 2015 г. Проверено 29 января 2015 г.
• Флай Сент-Мари, Камилла (1894). «Решение вопроса № 48». Посредник математиков . 1 :107–110.
• Горески, Марк ; Клэппер, Эндрю (2012). «8.2.5 Генерация сдвиговых регистров последовательностей де Брёйна». Алгебраические последовательности регистров сдвига . Издательство Кембриджского университета . стр. 174–175. ISBN  978-1-10701499-2 .
• Холл, Рэйчел В. (2008). «Математика для поэтов и барабанщиков» (PDF) . Математические горизонты . 15 (3): 10–11. дои : 10.1080/10724117.2008.11974752 . S2CID   3637061 . Архивировано из оригинала (PDF) 12 февраля 2012 г. Проверено 22 октября 2008 г.
• Хиггинс, Питер (ноябрь 2012 г.). «Преобразования Берроуза-Уиллера и слова де Брёйна» (PDF) . Проверено 11 февраля 2017 г.
• Херлберт, Гленн; Исаак, Гарт (1993). «О проблеме тора де Брейна» . Журнал комбинаторной теории . Серия А. 64 (1): 50–62. дои : 10.1016/0097-3165(93)90087-О . МР   1239511 .
• Как, Субхаш (2000). «Яматараджабханасалагам - интересная комбинаторная сутра» (PDF) . Индийский журнал истории науки . 35 (2): 123–127. Архивировано из оригинала (PDF) 29 октября 2014 г.
• Кляйн, Андреас (2013). Потоковые шифры . Спрингер. п. 59. ИСБН  978-1-44715079-4 .
• Кнут, Дональд Эрвин (2006). Искусство компьютерного программирования, глава 4: Генерация всех деревьев – история комбинаторной генерации . Аддисон-Уэсли . п. 50. ISBN  978-0-321-33570-8 .
• Фредриксен, Гарольд; Майорана, Джеймс (1978). «Ожерелья из бисера k цветов и k -арных последовательностей де Брейна» . Дискретная математика . 23 (3): 207–210. дои : 10.1016/0012-365X(78)90002-X . МР   0523071 .
• Мартин, Монро Х. (1934). «Проблема в договоренностях» (PDF) . Бюллетень Американского математического общества . 40 (12): 859–864. дои : 10.1090/S0002-9904-1934-05988-3 . МР   1562989 .
• Осипов, Владимир (2016). «Вейвлет-анализ символических последовательностей и двукратных последовательностей де Брейна». Журнал статистической физики . 164 (1): 142–165. arXiv : 1601.02097 . Бибкод : 2016JSP...164..142O . дои : 10.1007/s10955-016-1537-5 . ISSN   1572-9613 . S2CID   16535836 .
• Поппер, Карл (2002) [1934]. Логика научного открытия . Рутледж. п. 294. ИСБН  978-0-415-27843-0 .
• Ралстон, Энтони (1982). «Последовательности де Брейна — образцовый пример взаимодействия дискретной математики и информатики». Журнал «Математика» . 55 (3): 131–143. дои : 10.2307/2690079 . JSTOR   2690079 . МР   0653429 .
• Штейн, Шерман К. (1963). «Яматараджабханасалагам». Рукотворная Вселенная: Введение в дух математики . стр. 110–118. Перепечатано в Wardhaugh, Benjamin, изд. (2012), Богатство чисел: антология популярных произведений по математике за 500 лет , Princeton University Press , стр. 139–144.
• Тулиани, Джонатан (2001). «Последовательности де Брейна с эффективными алгоритмами декодирования». Дискретная математика . 226 (1–3): 313–336. дои : 10.1016/S0012-365X(00)00117-5 . МР   1802599 .
• ван Линт, Дж. Х .; Уилсон, Ричард Майкл (2001). Курс комбинаторики . Издательство Кембриджского университета . п. 71. ИСБН  978-0-52100601-9 .

Внешние ссылки

• Вайсштейн, Эрик В. «Последовательность де Брёйна» . Математический мир .
• Последовательность OEIS A166315 (лексикографически наименьшие двоичные последовательности де Брейна)
• Последовательность Де Брейна
• CGI-генератор
• Генератор апплетов
• Генератор и декодер Javascript . Реализация алгоритма Дж. Тулиани.
• Кодовый замок двери
• Минимальные массивы, содержащие все комбинации символов подмассивов: последовательности де Брейна и торы.
• http://debruijnsequence.org содержит множество типов последовательностей де Брейна.