Найти сетку NxM, которая содержит все возможные 3х3 битные комбинации
Обновление: это называется тором де Бруджина, но мне все еще нужно выяснить простой алгоритм в C#.
http://en.wikipedia.org/wiki/De_Bruijn_torus
http://datagenetics.com/blog/october22013/index.html
Мне нужно как можно плотнее объединить все значения сетки 3х3 бита. Под сеткой 3x3 я имею в виду сетку 3x3, где каждое место немного похоже на концепцию дырокола в этом вопросе:
Найти все комбинации 3х3 дырокола
Примеры 3x3 битовой сетки:
XXX .X. ...
XXX .X. .X.
XXX .X. ...
Цель
Я хочу упаковать все 512 (фактически 256, потому что центральный бит всегда включен) возможных значений, чтобы они перекрывались в одной сетке NxM.
Неполный пример:
Этот пример упаковывает ~25 возможных значений в сетку 7x7.
.......
.X.XXX.
.......
.X.XXX.
.X.XXX.
.X.XXX.
.......
Вещи уже известны:
- Есть 2^9 (512) уникальных значений.
- Я забочусь только о 2^8 (256) значениях, потому что мне всегда нужен центральный бит.
попытки
Я перепробовал много разных техник вручную, но не смог придумать простой алгоритм.
Итак, я хотел бы написать программу на C# для ее создания, но я также не видел простого пути.
Нет даже очевидного подхода грубой силы, который кажется мне возможным. Кажется, любая попытка грубой силы приблизится к 512! комбинации в худшем случае.
наблюдения
Каждое ребро имеет только 8 возможных значений.
X...X.XXX. //(8+2 bits) Exhausts all values in the same problem with 1-Dimension.
.X.XXX. //(5+2 bits) The above simplifies when the center bit must be on.
Цель
На самом деле это будет использоваться для 2D-игры на основе тайлов.
В игре N возможных основных фигур. Учитывая, что почва может возникнуть в любой ситуации, дизайнеру нужен способ выразить, какая плитка должна быть выбрана для любой конкретной ситуации.
Компактная сетка, содержащая все возможные ситуации, является наиболее эффективным способом указания того, какую плитку использовать в каждой ситуации, и устраняет все избыточности.
Обновить
пример
....
.XX.
.XX.
....
Выше приведен базовый шаблон, который позволяет выражать 4 ситуации, и я изменю его, чтобы использовать другие значения ascii для представления результата, который следует использовать в каждой ситуации:
....
.AG.
.HH.
....
Где A,G,H каждый представляет определенный шаблон, который следует использовать для каждой ситуации.
Итак, если найден следующий шаблон:
...
.XX
.XX
Это соответствует шаблону, который приводит к "A" выше, поэтому "A" будет использоваться в этой ситуации.
???
?A?
???
Цель состоит в том, чтобы иметь исчерпывающее выражение того, к чему приведет каждая возможная ситуация.
На практике
Я смог сделать это и нашел результаты слишком случайными, чтобы хорошо работать для достижения целей. Как человеку, было трудно выбрать правильные значения в каждой ситуации, потому что или дезорганизация. Ручная группировка похожих шаблонов все еще работает лучше.
3 ответа
Упаковка всех шаблонов 3x3 в сетку 3xN с последовательностями Де Брюина
Давайте рассмотрим каждый столбец высоты-3 как одно число от 0 до 7, что мы можем сделать, поскольку существует 8 возможных столбцов высоты-3. Теперь упаковка всех 512 возможных шаблонов 3x3 в минимально возможную сетку размера 3xN эквивалентна нахождению последовательности де Брейна с параметрами B (8, 3). Эта сетка будет иметь размер 3x514: после первых 3x3 каждая дополнительная 3x3 стоит нам только 1 дополнительный столбец, что, очевидно, является наилучшим вариантом для сетки высотой 3.
Основываясь на этой странице Википедии, кажется, что наиболее эффективный способ сделать это состоит в том, чтобы построить последовательность последовательностей де Брейна B(8, 1), B(8, 2), B(8, 3), найдя эйлеровы циклы в граф де Брюйна предыдущей последовательности (поскольку другой предложенный алгоритм включает в себя поиск гамильтонова пути, который является NP-полной задачей, эквивалентной по сложности задаче задачи коммивояжера).
Существуют также де Бруйн тори, двумерные аналоги последовательностей де Брейна, которые более близко подходят к вашей цели упаковки в сетку NxN. Однако на этой странице не ясно, как или даже возможно ли построить тор де Брюйна для шаблонов 3х3 (они только говорят, что известно, что они могут быть созданы для прямоугольных шаблонов четного размера, и что тор для квадрата шаблон нечетного размера сам по себе не может быть квадратным - поэтому предположительно NxN отсутствует), и, кроме того, вполне вероятно, что строгое ограничение уникальности, которое они удовлетворяют, не является необходимым для вашего приложения.
520-битная строка ниже содержит все 3х3 битные комбинации в виде смежных подпоследовательностей:
XXXXXXXXX.XXXXXXX..XXXXXX.X.XXXXXX...XXXXX.XX.XXXXX.X..XXXXX..X.XXXXX....XXXX.XXX.XXXX.XX..XXXX.X.X.XXXX.X...XXXX..XX.XXXX..X..XXXX...X.XXXX.....XXX.XXX..XXX.XX.X.XXX.XX...XXX.X.XX.XXX.X.X..XXX.X..X.XXX.X....XXX..XX..XXX..X.X.XXX..X...XXX...XX.XXX...X..XXX....X.XXX......XX.XX.XX.X..XX.XX..X.XX.XX....XX.X.XX..XX.X.X.X.XX.X.X...XX.X..X..XX.X...X.XX.X.....XX..XX...XX..X.X..XX..X..X.XX..X....XX...X.X.XX...X...XX....X..XX.....X.XX.......X.X.X.X..X.X.X....X.X..X...X.X...X..X.X......X..X..X.....X...X....X.........XXXXXXXX
Или, если хотите, версия j_random_hacker:
............X..X..X..X...........X..X..X..X...........X..X..X..X...........X..X..X..X.X..X..X..XX.XX.XX.XX.X..X..X..XX.XX.XX.XX.X..X..X..XX.XX.XX.XX.X..X..X..XX.XX.XX.XX.........X..X..X..X........X..X..X..X........X..X..X..X.X..X..XX.XX.XX.XX.X..X..XX.XX.XX.XX.X..X..XX.XX.XX.XX.X..X..XX.XX.XX.XX......X..X..X..X.....X..X..X..X.X..XX.XX.XX.XX.X..XX.XX.XX.XX.X..XX.XX.XX.XX.X..XX.XX.XX.XX...X..X..X..X.XX.XX.XX.XX.XX.XX.XX.XX.XX.XX.XX.XX.XX.XX.XX.XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX..
......X..X........X..X.....X..X........X..X.X..XX.XX.X..X..XX.XX.X..XX.XX.X..X..XX.XX.....X..X........X..X.....X..X........X..X.X..XX.XX.X..X..XX.XX.X..XX.XX.X..X..XX.XX...X..X........X..X.XX.XX.X..X..XX.XX.XX.XX.X..X..XX.XX..X..X........X..X..X..X........X..X.XX.XX.X..X..XX.XX.XX.XX.X..X..XX.XXXXXXXX.XX.XXXXXXXXXXX.XX.XXXXXXX.XX..X..X.XX.XX.XX..X..X.XX.XXXXXX.XX.XXXXXXXXXXX.XX.XXXXXXXXX.XX.XXXXXXX..X..X.XX.XX..X..X.XX.XXX.XX.XXXXXXXX.XX.XXXXXX......X..X.....X..X.X..XX.XX.X..XX.XX...X..X.XX.XX.XX.XXXXXXXXXX..
...X.....X.....X.....X.XX.X..XX.X..XX.X..XX..X.....X.....X.....X.XX.X..XX.X..XX.X..XX..X.....X.....X.....X.XX.X..XX.X..XX.X..XX..X.....X.....X.....X.XX.X..XX.X..XX.X..XXXXX.XXXXX.XXXXX.XXXX..X.XX..X.XX..X.XXX.XXXXX.XXXXX.XXXX..X.XX..X.XX..X.XXX.XXXXX.XXXXX.XXXX..X.XX..X.XX..X.XXX.XXXXX.XXXXX.XXX...X.....X.....X.XX.X..XX.X..XX..X.....X.....X.XX.X..XX.X..XX..X.....X.....X.XX.X..XX.X..XXXXX.XXXXX.XXXX..X.XX..X.XXX.XXXXX.XXXX..X.XX..X.XXX.XXXXX.XXX...X.....X.XX.X..XX..X.....X.XX.X..XXXXX.XXXX..X.XXX.XXX...X.XXX..
Или вы можете сэкономить место и просто использовать числа от 0 до 511, которые для большинства компьютеров являются 9-разрядными.
"Компактная сетка, которая содержит все возможные ситуации, - это самый эффективный способ указать, какую плитку использовать в каждой ситуации, и исключает любую избыточность".
Я склонен не согласиться.
Независимо от того, как выглядит результат вашего упражнения на свертывание, его индексация для получения заданного шаблона 3х3 потребует 8-битных индексов, поскольку существует ровно 256 ситуаций смежности тайлов. Если ваше компактное представление содержит более 256 шаблонов - то есть, если в них включены нежелательные или избыточные шаблоны - тогда вам потребуется более восьми битов для индексации.
Однако 8-битный байт уже может представлять все возможные ситуации смежности, если вы рассматриваете его как битовую маску и каким-то образом сопоставляете восемь битов с восемью внешними фрагментами сетки 3x3. Это означает, что сложенная мастер-сетка - в стиле де Брюйна или иным образом - является излишней и может обойтись без.