Тор де Брёйна - De Bruijn torus

Тор Де Брейна. Каждую двоичную матрицу 2 на 2 можно найти в ней ровно один раз.

В комбинаторный математика, Тор де Брёйна, названный в честь Николаас Говерт де Брёйн, является массив символов из алфавита (часто только 0 и 1), который содержит каждый м-от-п матрица ровно один раз. Это тор потому что края считаются охватывающими с целью поиска матриц. Его название происходит от Последовательность де Брюйна, который можно рассматривать как частный случай, когда п равно 1 (одно измерение).

Один из основных открытых вопросов, касающихся торов Де Брейна, заключается в том, можно ли построить тор Де Брейна для определенного размера алфавита для данного м ип. Известно, что они всегда существуют, когда п = 1, с тех пор мы просто получаем последовательности Де Брейна, которые существуют всегда. Также известно, что «квадратные» торы существуют всякий раз, когдам = п и даже (в нечетном случае получающиеся торы не могут быть квадратными).[1][2][3]

Наименьший возможный двоичный "квадратный" тор де Брейна, изображенный справа вверху, обозначается как (4,4;2,2)2 тор де Брейна (или просто как B2), содержит все 2×2 бинарные матрицы.

B2

Помимо «перевода», «инверсии» (обмен 0s и 1с) и «поворот» (на 90 градусов), никакие другие (4,4;2,2)2 Возможны торы де Брёйна - это можно показать при полном рассмотрении всех 216 двоичные матрицы (или подмножество, выполняющее ограничения, такие как равное количество 0s и 1с).[4]

Более крупный пример: B4

B4 как двоичная квадратная матрица
Сетка выделяет некоторые из матриц 4 × 4, в том числе нулей и из единиц на верхнем поле.

Пример следующего возможного двоичного «квадратного» тора де Брейна, (256,256;4,4)2 (сокращенно B4), был построен явно.[5]

На изображении справа показан пример (256,256;4,4)2 Тор / массив де Брейна, где нули закодированы как белые, а единицы как красные пиксели соответственно.

Двоичные торы де Брейна большего размера

Статья, в которой приведен пример (256,256;4,4)2 Тор де Брейна был построен из более чем 10 страниц двоичного кода, несмотря на его уменьшенный размер шрифта, требующий трех строк на строку массива.

Последующий возможный двоичный тор де Брейна, содержащий все двоичные 6×6 матрицы, имели бы 236 = 68,719,476,736 записи, в результате чего получается квадратный массив размерности 262,144x262,144, обозначенный (262144,262144;6,6)2 тор де Брейна или просто B6. Это можно было бы легко сохранить на компьютере - при печати с пикселями со стороной 0,1 мм такая матрица потребовала бы площади примерно 26 × 26. квадратный метр.

Предмет B8, содержащий все двоичные 8×8 матрицы и обозначены (4294967296,4294967296;8,8)2, имеет в общей сложности 264 ≈ 18.447×1018 записей: для хранения такой матрицы потребуется 18,5 эксабита, или 2,3 Эксабайт хранилища, что на порядок превосходит даже современные центры обработки данных.

Смотрите также

Рекомендации

  1. ^ Fan, C. T .; Fan, S.M .; Ma, S. L .; Сиу, М. К. (1985). «О массивах де Брёйна». Ars Combinatoria A. 19: 205–213.
  2. ^ Chung, F .; Diaconis, P .; Грэм, Р. (1992). «Универсальные циклы для комбинаторных структур». Дискретная математика. 110 (1): 43–59. Дои:10.1016 / 0012-365x (92) 90699-г.
  3. ^ Джексон, Брэд; Стивенс, Бретт; Херлберт, Гленн (сентябрь 2009 г.). «Проблемы исследования кодов Грея и универсальных циклов». Дискретная математика. 309 (17): 5341–5348. Дои:10.1016 / j.disc.2009.04.002.
  4. ^ Эгген, Бернд Р. (1990). «Бинаторикс В2». Частное общение.
  5. ^ Шиу, Вай-Чи (1997). «Расшифровка массивов де Брейна, построенных методом FFMS». Ars Combinatoria. 47 (17): 33–48.

внешняя ссылка