Введение

Перебираем все последовательности длины k.

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

Эти последовательности названы в честь голландского математика Николаса Говерта де Брюйна, который опубликовал работы о них в 1946 году. Как он позже писал, существование последовательностей де Брюйна для каждого порядка вместе с вышеуказанными свойствами было впервые доказано для случая алфавитов с двумя элементами. Обобщение на большие алфавиты было выполнено благодаря автоматам, предназначенным для распознавания этих последовательностей, которые называются автоматами де Брюйна. В большинстве приложений A = {0, 1}.

История

Самый ранний известный пример последовательности де Брюйна происходит из санскритской просодии, где, начиная с работ Пингалы, каждому из возможных трехсложных сочетаний длинных и коротких слогов дается имя, например, 'y' для короткий–длинный–длинный и 'm' для длинный–длинный–длинный. Для запоминания этих имен используется мнемоническое правило yamātārājabhānasalagām, в котором каждое трехсложное сочетание встречается, начиная с его имени: 'yamātā' содержит сочетание короткий–длинный–длинный, 'mātārā' – длинный–длинный–длинный, и так далее, до 'salagām', которое содержит короткий–короткий–длинный. Эта мнемоническая фраза, эквивалентная последовательности де Брюйна на двоичных 3-кортежах, имеет неизвестную древность, но по крайней мере столь же стара, как книга Чарльза Филиппа Брауна 1869 года о санскритской просодии, в которой она упоминается и рассматривается как «древняя строка, написанная Панини». В 1894 году А. де Ривьер поднял вопрос в журнале L'Intermédiaire des Mathématiciens о существовании циклической последовательности нулей и единиц размера *n*, содержащей все двоичные последовательности длины *k*. Проблема была решена (в положительном смысле), вместе с подсчетом различных решений, Камиль Флай Сент-Мари в том же году. Это было в значительной степени забыто, и позже доказал существование таких циклов для общего размера алфавита вместо 2, предложив алгоритм для их построения. Наконец, когда в 1944 году Кис Постхумус выдвинул гипотезу о количестве таких последовательностей для двоичного алфавита, де Брюйн доказал эту гипотезу в 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, в лексикографическом порядке.

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

Применение

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

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

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

f-fold де Брюйена

Последовательность де Брюйна порядка f и основания n является обобщением понятия последовательности де Брюйна основания n, такое что последовательность длины содержит каждую возможную подпоследовательность длины n ровно f раз. Например, для n=2 циклические последовательности 11100010 и 11101000 являются двукратными бинарными последовательностями де Брюйна. Количество двукратных последовательностей де Брюйна для n=3 равно 8, другие известные числа равны 72, 576 и 4608.

Де Брюйн-торус

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

Декодирование де Брюйна

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