Алгоритм идентификации уникального свободного полимино (или хеша полимино)

Короче:Как хешировать бесплатное полимино?

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

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

Я работаю над разными алгоритмами для генерации случайныхполиомино. Я хочу проверить их вывод, чтобы определить, насколько они случайны --, т. е. являются ли определенные экземпляры заданного порядка генерируемыми чаще, чем другие. Визуально очень легко определить различные ориентации свободного полимино, например, на следующей иллюстрации из Википедии показаны все 8 ориентаций пентамино «F» (. Источник):

Как можно присвоить номер этому полимино -, то есть хешировать свободное полимино? Я не хочу зависеть от заранее составленного списка «именных» полимино. Во всяком случае, общепринятое -имя существует только для порядков 4 и 5.

Это не обязательно эквивалентно перечислению всех свободных (, односторонних -или фиксированных )полимино заданного порядка. Я только хочу подсчитать, сколько раз появляется данная конфигурация. Если генерирующий алгоритм никогда не производит определенное полимино, оно просто не будет учитываться.

Основная логика подсчета:

testcount = 10000 // Arbitrary
order = 6         // Create hexominos in this test
hashcounts = new hashtable
for i = 1 to testcount
    poly = GenerateRandomPolyomino(order)
    hash = PolyHash(poly)
    if hashcounts.contains(hash) then  
        hashcounts[hash]++
    else
        hashcounts[hash] = 1 

Я ищу эффективный PolyHashалгоритм.Входные полимино просто определяются как набор координат. Одной из ориентаций Т-тетронимо может быть, например,:

[[1,0], [0,1], [1,1], [2,1]]:

 |012
-+---
0| X
1|XXX

Вы можете предположить, что это входное полимино уже будет нормализовано, чтобы выровняться по осям X и Y и иметь только положительные координаты. Формально каждое множество:

• Будет иметь по крайней мере 1 координату, где значение x равно 0
• Будет иметь по крайней мере 1 координату, где значение y равно 0
• Не будет иметь координат, где x

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

Грубая сила

Решение грубой силы, предложенное здесь и здесь , состоит из хеширования каждого набора как целого числа без знака с использованием каждой координаты в качестве двоичного флага и взятия минимального хэша всех возможных поворотов (и в моем случае flips ), где каждое вращение/флип тоже нужно переводить в начало координат. Это приводит к 23 операциям набора для каждого входного набора, чтобы получить «бесплатный» хэш :

• . Повернуть (6 раз)
• Перевернуть (1x)
• Перевести (7x)
• Хэш (8x)
• Найти минимум вычисленных хэшей (1x)

Где последовательность операций для получения каждого хэша:

1. Хэш
2. Повернуть, перевести, хешировать
3. Повернуть, перевести, хешировать
4. Повернуть, перевести, хешировать
5. Перевернуть, перевести, хешировать
6. Повернуть, перевести, хешировать
7. Повернуть, перевести, хешировать
8. Повернуть, перевести, хешировать