Центральна симетрія сітки

Досліджуючи одну задачу оптимізації, зіткнувся з проблемою симетричності конфігурацій при прямому переборі варіантів. Схожа проблема виникає в деяких рішеннях завдання про вісім ферзів. Досліджуючи центральну симетрію прямокутної сітки, я виявив революційний досить цікавий метод визначення і перевірки симетричних конфігурацій з використанням чисел-«перевертнів».

Трохи про симетрії

Центральна симетрія або симетрія з центром в точці — це перетворення простору, що переводить точку в точку X X' так, що центр симетрії буде центром відрізка XX'. Фігура називається симетричною відносно точки A, якщо для кожної точки фігури симетрична їй точка відносно точки A також належить цій фігурі.

Якщо ж ми говоримо про центральної симетрії сітки, що складається з клітин, то тут мова буде йти не про точках, а про клітинах сітки. Наприклад, після центрально-симетричного перетворення шахової дошки клітина A1 стане на місце H8, A2 — на H7, а B1 — на G8.
У цій статті ми будемо використовувати прямокутну сітку. Як і прямокутник, така сітка має дві осі симетрії і один центр, але зосередимося тільки на центральній симетрії.

Суть питання

Є сітка розміром 3 на 6 клітин. Також в наявності список з 14 компонент, кожний з яких може бути поставлений в будь-яку клітину, причому можливі повтори. Кількість варіантів заповнення такої сітки з повторами дорівнює 1418, природно було б непогано їх зменшити в два рази, відкинувши варіанти заповнення, які є центрально-симетричними до вже перевіреним. Для простоти виведення нехай компонентами будуть числами від 0 до 13 включно. Список з 18 компонент генерується функцією product з пакету itertools (якщо бути точним, то функція повертає кортеж-ітератор, який, подібно одометру, на кожній ітерації змінює правостоящий елемент). Цим списком по стовпчиках і заповнюється сітка.

Приклади нульової, першої, другої та 178-ой конфігурації сітки

Завдання: Виключити варіанти заповнення сітки, центрально-симетричні вже перевіреним варіантами.

Реалізація

Пронумеруємо клітинки по стовпчикам, починаючи з лівого верхнього кута, від 0 до 17. Спробуємо для кожної конфігурації знайти номер симетричну їй відносно центру. Нумерація конфігурацій, як зазвичай, з нуля.

Конфігурація 0 (всі клітинки нулями) очевидно симетрична сама собі: 0 -> 0.

Конфігурація 1. Клітина 17 отримує 1, решта з нулями. Симетричною до неї буде конфігурація, в якій клітці 0 коштує «1», інші з нулями. Клітина 17 пройде 14 своїх значень (від 0 до 13) за перші 14 ітерацій. Клітка 16 теж за 14, але на кожну її конфігурацію припадає 14 ітерацій клітини 17, тобто за 142, і т. д. Отже, клітина 0 набере 1 на 1417 ітерації.

Конфігурація 2. Клітка №17 отримує 2, решта з нулями. Симетричною до неї буде конфігурація 2⋅1417, в якій клітці 0 коштує 2, інші нулі.

Конфігурація 3 -> Конфігурація 3⋅1417

Конфігурація 4 -> Конфігурація 4⋅1417 і т. д. до 13 -> 13⋅1417.

Слідуючи цій логіці, варто записати номер варіанта, симетричного першому, як 1⋅1417, а симетричного нульового — як 0⋅1417.

Вже маємо певний список номерів конфігурацій, симетричні один одному:

  • 0 і 0⋅1417
  • 1 і 1⋅1417
  • 2 і 2⋅1417
і т. д. до 13.

Конфігурація 14. 1 знаходиться в передостанній клітці, інші нулі. Симетричною до неї є 1⋅1416.

Конфігурація 15. Одиниці в двох останніх клітка, інші нулі. Симетрична до неї, коли 1 в перших двох клітинках, інші нулі. 1 стає в клітинку №0 на ітерації 1417, а ще через 1416 1 з'явиться і в клітці №1, отже шукана конфігурація буде під номером 1416 + 1417.

Конфігурація 16. Елемент «А» в комірці №16, «B» — в комірці №17. Симетрична до неї, очевидно 1416 + 2⋅1417.

Конфігурація 27 -> 1⋅1416 + 13⋅1417.

Конфігурація 28 -> 2⋅1416.

Конфігурація 29 -> 2⋅1416 + 1417.

Ця історія триває до ітерації 195, яка симетрична 13⋅1416 + 13⋅1417. У ітерації 196 в клітинку №15 ставиться 1, решта порожні. Симетрична до неї ітерація 1415.

У ітерації 197 одиниця ставиться ще й в клітинку №17, тому симетрична до неї — 1415 + 1417, і т. д.

Загальний закон симетрії конфігурацій сітки буде таким:

image

Тут мені здалася знайомою формула ліворуч. Це формула переведення чисел із системи числення з довільною основою в десяткову. І, відповідно image— це цифра в системі числення з підставою 14.

Неважко помітити, що в правій частині записано число з лівої частини в зворотному порядку — якщо в лівій частині ми «пишемо» число справа наліво, то в лівій — тими ж цифрами, але зліва направо. Простіше кажучи, число праворуч — це «перевертиш» числа зліва, причому обидва записані в системі числення з підставою 14 і мають довжину 18.

Критерій та алгоритм валідації

Якщо номер конфігурації довжиною кількість клітин і записаний в системі числення з основою, рівною кількості елементів, менше власного номера-«перевертыша», то конфігурація симетрична даній ще не зустрічалася. Якщо ж вони (номери) рівні, то маємо справу з паліндромом, який зустрічається лише один раз і, отже, підлягає перевірці.

Сам алгоритм валідації такий:

  1. Перевести номер конфігурації в систему числення з основою, рівною кількості елементів
  2. Записати число«перевертень» довжиною 18
  3. Якщо «перевертиш» більше номери конфігурації, то симуляції цієї конфігурації і симетричною до неї ще не проводилися; якщо ні, то проводилася симуляція конфігурації, симетричною цієї, отже — пропустити.
Або у вигляді коду
def validate(number, radix, length):
fingers = '0123456789abcdefghijklmnopqrstuvwxyz'
n = number

# переклад в систему числення з основою radix без розвороту
turn = "
while n > 0:
turn += fingers[n % radix]
n = n // radix

# додамо відсутні нулі до потрібної довжини
turn += '0' * (length - len(turn))

return number <= int(turn, radix)


Висновок

Очевидно, цей алгоритм можна застосувати не тільки для визначення центральної симетрії двовимірної сітки, але і сітки в довільному вимірі, тому що будь-яку таку конфігурацію можливо звести до списку, або списком заповнити сітку, наприклад, по рядках.
Сам алгоритм досить важкий, що викликає питання про застосування його на практиці. Але в разі, коли перевірка кожної конфігурації варто ще більше обчислювальних ресурсів, то, можливо, варто його використовувати.
Джерело: Хабрахабр

0 коментарів

Тільки зареєстровані та авторизовані користувачі можуть залишати коментарі.