Каждого Полимин порядка п +-может быть получен путем добавления квадрата к Полимину порядка п. Это приводит к алгоритмам индуктивной индукции полиминонов.
Проще всего, учитывая список полиоминонов порядка n, квадраты могут быть добавлены рядом с каждым полиомино в каждом возможном положении, а полученный полиомино порядка n + 1 добавлен в список, если не дубликат одного уже найденного ; уточнения в упорядочении перечисления и маркировки смежных квадратов, которые не следует рассматривать, уменьшают количество случаев, которые необходимо проверить для дубликатов. [9] Этот метод может быть использован для перечисления свободных или фиксированных полиоминолов.
Более сложный метод, описанный Редельмайером, использовался многими авторами как способ не только подсчета полиоминосов (без необходимости хранить все полиоминоны порядка n, чтобы перечислять последовательности порядка n + 1), но и доказывает верхние оценки их числа. Основная идея состоит в том, что мы начинаем с одного квадрата, а оттуда рекурсивно добавляем квадраты. В зависимости от деталей он может подсчитывать каждый n-omino n раз, один раз начиная с каждого из своих n квадратов, или может быть организован для подсчета только один раз.
Простейшая реализация включает в себя добавление одного квадрата за раз. Начиная с начального квадрата, смещайте соседние квадраты по часовой стрелке сверху, 1, 2, 3 и 4. Теперь выберите число от 1 до 4 и добавьте квадрат в этом месте. Выделите числа с нумерованными соседними квадратами, начиная с 5. Затем выберите число, большее, чем ранее выбранное число, и добавьте этот квадрат. Продолжайте выбирать число, большее, чем число текущего квадрата, добавляя этот квадрат, а затем нумерацию новых смежных квадратов. Когда n квадратов были созданы, было создано n-omino.
Этот метод гарантирует, что каждый фиксированный полиомино считается ровно n раз, один раз для каждого стартового квадрата. Он может быть оптимизирован так, что он будет считать каждый полиомино только один раз, а не n раз. Начиная с начального квадрата, объявите его нижним левым квадратом полиомино. Просто не наберите квадрат, который находится на нижней строке, или слева от квадрата в той же строке. Это версия, описанная Redelmeier.
Если вы хотите сосчитать бесплатные полиоминозы, то после создания каждого n-omino можно проверить симметрии. Тем не менее, быстрее [10] генерировать симметричные полиоминоны отдельно (по вариации этого метода) [11] и таким образом определять количество свободных полиоминонов по лемме Бернсайда.
Самый современный алгоритм для перечисления фиксированных полиоминолов был обнаружен Иваном Дженсеном.[12] Совершенствование метода Эндрю Конвей [13] является экспоненциально быстрее, чем предыдущие методы (однако его время работы по-прежнему экспоненциально по n).
Оба варианта метода трансфер-матрицы в Конуэй и Йенсена включают подсчет количества полиномино, имеющих определенную ширину. Вычисление числа для всех ширин дает общее количество полиоминосов. Основная идея метода заключается в том, что рассматриваются возможные начальные строки, а затем для определения минимального количества квадратов, необходимых для завершения полимино данной ширины. В сочетании с использованием генерирующих функций этот метод позволяет считать сразу несколько полиминонов, что позволяет ему работать во много раз быстрее, чем методы, которые должны генерировать каждый полиомино.
Несмотря на отличное время работы, компромисс заключается в том, что этот алгоритм использует экспоненциальные объемы памяти (требуется много гигабайт памяти для n выше 50), гораздо сложнее программировать, чем другие методы, и в настоящее время не может для подсчета свободных полиоминолов.
Для меня этого достаточно. Тем не менее, я действительно хочу рассчитать количество свободных полиамино, но, похоже, нет простого решения. Если меня спросят об этом в интервью, я просто дам алгоритм, упомянутый выше, для расчета числа фиксированных полиоминоз, а затем удалите дубликаты для подсчета свободных полиоминолов.
@TagirValeev Они дубликаты. – laike9m
@TagirValeev Да, я исправил свою проблему. – laike9m
Справедливо следующее утверждение: части p1 и p2 эквивалентны тогда и только тогда, когда p2 является вращением p1? – piotrekg2