Исследование свойств диагональных латинских квадратов в проектах добровольных распределенных вычислений и не только...
Поиск обобщенных симметрий в ЛК
Напомню, что обобщенная симметрия — это такая симметрия, которая описывается тройкой перестановок Px, Py и Pv, применяя которые к ЛК (в том числе к ДЛК, которые являются одним из видов ЛК) можно получить его автоморфное отображение самого в себя. При этом ячейка [x,y]=v отображается в ячейку [x',y']=v', причем x'=Px(x), y'=Py(y) и v'=Pv(v). Другими словами, тройка перестановок описывает один из автоморфизмов ЛК (преобразование, переводящее квадрат сам в себя). Интерес к данным симметриям вызван тем, что, как показывают вычислительные эксперименты, обычно чем больше подобных симметрий у квадрата, тем более интересными свойствами он обладает (имеет много ОЛК/ОДЛК, трансверсалей, входит в состав редких комбинаторных структур и т.п.).
Простейшим способом отыскания искомых перестановок по заданному ЛК является их полный перебор с проверкой того, что квадрат отображается сам в себя. Однако данный способ очень неэффективен, т.к. перестановок порядка N существует N!, мощность перебора в данном случае будет составлять (N!)^3, что, например, для N=10 — огромное число, так не пойдет, поэтому искать нужно как-то иначе...
Прежде всего, можно заметить, что перебирать можно только перестановки Px и Py, далее их можно применить к заданному исходному квадрату A с получением квадрата A', элементы [x',y'] которого подчиняются приведенным выше формулам и равны [Px(x),Py(y)]. Например, для квадрата A
0 1 2 3 4 5 6 7 8 9
1 2 3 4 0 9 5 6 7 8
4 0 1 7 3 6 2 8 9 5
8 7 6 5 9 0 4 3 2 1
7 6 5 0 8 1 9 4 3 2
9 8 7 6 5 4 3 2 1 0
5 9 8 2 6 3 7 1 0 4
3 5 0 8 7 2 1 9 4 6
2 3 4 9 1 8 0 5 6 7
6 4 9 1 2 7 8 0 5 3
и перестановок Px=[0,1,2,3,4,5,6,7,8,9], Py = [9,8,7,6,5,4,3,2,1,0], описывающих плоскостную (горизонтальную) симметрию, получается квадрат A'
9 8 7 6 5 4 3 2 1 0
8 7 6 5 9 0 4 3 2 1
5 9 8 2 6 3 7 1 0 4
1 2 3 4 0 9 5 6 7 8
2 3 4 9 1 8 0 5 6 7
0 1 2 3 4 5 6 7 8 9
4 0 1 7 3 6 2 8 9 5
6 4 9 1 2 7 8 0 5 3
7 6 5 0 8 1 9 4 3 2
3 5 0 8 7 2 1 9 4 6
Сопоставляя, например, значения в первой строке квадратов A и A', можно заметить, что вместо 0 в ячейке [0,0] стоит 9, вместо 1 — 8 и т.д., а значит Pv=[9,8,7,6,5,4,3,2,1,0].
Подобное "вытаскивание" перестановки Pv из пары квадратов A и A' сокращает мощность перебора с (N!)^3 до (N!)^2, но величина все равно остается огромной, ее необходимо как-то дополнительно снизить...
Заметим, что перестановка строк и столбцов ЛК не должна менять как свойств самого ЛК (разумеется, инвариантных к данному преобразованию), так и свойств самого элемента, который до преобразования имел координаты [x,y], а после стал [x',y']. К инвариантным свойствам ЛК в данном случае относятся, например, число трансверсалей, число интеркалятов, число ОДЛК, число циклов и т.п. Заметим, что число диагональных трансверсалей в данном случае инвариантом не является, т.к. диагональные элементы ДЛК могут соскочить с диагоналей и наоборот — недиагональные попасть на диагонали (напомню, что данное число диагональных трансверсалей является инвариантом только относительно некоторых перестановок строк и столбцов ДЛК, именуемых M-перестановками).
Также заметим, что каждый элемент [x,y] привязан к "своим" строке и столбцу, и перестановка строк или столбцов ЛК не может оторвать его от них (оторвать элемент от "своих" строки и столбца могут некоторые CMS схемы, но они сейчас в явном виде не применяются, хотя можно показать, что паре перестановок Px и Py можно взаимно однозначно сопоставить CMS схему и наоборот).
Исходя из замеченных особенностей, можно утверждать, что после отображения элемента [x,y] в [x',y'] свойства как самих элементов, так и "привязанных" к ним пар строка/столбец должны остаться теми же самыми, иначе автоморфизм ЛК не получится. Осталось лишь понять, что это за свойства...
При поиске автоморфизмов в неориентированных графах простейшим свойством-инвариантом является степень вершины: если, например, у какой-то вершины a[i] было 3 смежных с ней, то после автоморфного отображения a[i']=P(a[i]) 3 смежных должно остаться. Для квадрата необходимо найти какие-то числовые характеристики, которыми можно взвесить как сами элементы, так и привязанные к ним строки и столбцы, и которые кроме того относительно быстро посчитать.
Для этого рассмотрим матрицу покрытия элементов квадрата, например, трансверсалями. Приведенный выше квадрат A имеет 4224 трансверсали. Посчитаем, в какое число трансверсалей входит каждый элемент квадрата и выведем полученные числа в виде матрицы:
400 416 416 432 448 448 432 416 416 400
400 400 448 448 416 416 448 448 400 400
416 432 448 400 416 416 400 448 432 416
400 400 448 448 416 416 448 448 400 400
496 416 352 416 432 432 416 352 416 496
400 416 416 432 448 448 432 416 416 400
416 432 448 400 416 416 400 448 432 416
400 448 448 416 400 400 416 448 448 400
496 416 352 416 432 432 416 352 416 496
400 448 448 416 400 400 416 448 448 400
Это и есть матрица покрытия элементов квадрата трансверсалями. Элемент [0,0] входит в 400 различных трансверсалей, элемент [0,1] — в 416 трансверсалей и т.д. Анализ полученной матрицы позволяет сделать вывод о том, что, например, элемент [0,0] потенциально может быть отображен в элементы [0,9], [1,0], [1,1] и т.д., т.к. у них то же самое число вхождений в трансверсали, и не может быть отображен в элементы [0,1], [0,3], [0,4], т.к. у них число вхождений в трансверсали другое. Несложно заметить, что без рассмотрения взвешивающих свойств элементов ДЛК нужно было находить соответствия среди N^2 элементов, а теперь элементы распались на группы по значениям небольшой мощности и число соответствий будет существенно меньше, а значит и мощность перебора тоже. Аналогичные матрицы могут быть построены, например, для интеркалятов:
1 1 1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1 1 1
и коротких циклов:
5 5 5 5 5 5 5 5 5 5
5 5 5 5 5 5 5 5 5 5
5 5 5 5 5 5 5 5 5 5
5 5 5 5 5 5 5 5 5 5
5 5 5 5 5 5 5 5 5 5
5 5 5 5 5 5 5 5 5 5
5 5 5 5 5 5 5 5 5 5
5 5 5 5 5 5 5 5 5 5
5 5 5 5 5 5 5 5 5 5
5 5 5 5 5 5 5 5 5 5
Последние две матрицы получились однородными: все значения в них совпадают, а это значит, что в данном примере они не помогут снизить мощность перебора. Это в общем-то известная проблема при проверке изоморфизма однородных графов. Так бывает не всегда, но бывает. Приведем другой пример. Например, для квадрата
0 1 2 3 4 5 6 7 8 9
1 2 0 4 5 3 9 8 6 7
3 5 6 1 8 7 4 0 9 2
9 4 7 8 3 2 1 6 0 5
2 7 3 0 9 8 5 1 4 6
6 8 5 9 2 4 7 3 1 0
4 6 9 7 0 1 3 2 5 8
7 0 4 6 1 9 8 5 2 3
8 3 1 5 6 0 2 9 7 4
5 9 8 2 7 6 0 4 3 1
получаются вполне себе разнородные матрицы покрытия интеркалятами:
1 3 0 0 2 0 0 2 1 1
2 0 0 0 1 1 2 0 2 0
1 1 0 4 0 2 4 3 1 2
1 0 0 0 0 0 1 0 0 0
0 2 0 1 2 0 1 2 0 0
1 1 0 1 1 2 1 0 4 1
3 0 0 2 1 1 2 1 2 2
0 1 0 0 1 0 1 2 2 1
1 0 0 1 0 1 1 0 1 3
0 2 0 1 2 1 1 2 1 2
и короткими циклами:
7 7 7 6 6 5 6 5 6 3
7 7 7 6 5 6 3 6 6 5
6 5 6 7 6 5 6 7 3 7
3 6 5 6 6 7 7 6 7 5
7 5 6 7 3 6 5 7 6 6
6 6 5 3 7 6 5 6 7 7
6 6 3 5 7 7 6 7 5 6
5 7 6 6 7 3 6 5 7 6
6 6 7 5 6 7 7 3 5 6
5 3 6 7 5 6 7 6 6 7
Можно заметить, что элементы, не различаемые одной числовой характеристикой, могут быть отделены друг от друга другой, а числовые характеристики необходимо рассматривать в виде соответствующего взвешивающего кортежа. В приведенном примере элементы [0,0], [0,1] и [0,2] входят в 7 коротких циклов каждый (не различаются), но в то же самое время они входят в 1, 3 и 0 интеркалятов соответственно, т.е. могут быть различимы.
Как уже было упомянуть выше, при постановке какого-то элемента в другое место путем перестановки строк и столбцов он "тянет за собой" свою строку и столбец. А это значит, что между парами строк и столбцов можно также найти соответствия, с использованием которых можно сказать, какие пары строк/столбцов потенциально можно переставлять на место друг друга, а какие — нельзя. Для этого взвесим строки и столбцы мультимножествами значений из одной из матриц покрытия. Например, для приведенного выше квадрата A и матрицы покрытия элементов трансверсалей получается, что строкам соответствуют мультимножества
0: {400:2, 416:4, 432:2, 448:2}
1: {400:4, 416:2, 448:4}
2: {400:2, 416:4, 432:2, 448:2}
3: {400:4, 416:2, 448:4}
4: {352:2, 416:4, 432:2, 496:2}
5: {400:2, 416:4, 432:2, 448:2}
6: {400:2, 416:4, 432:2, 448:2}
7: {400:4, 416:2, 448:4}
8: {352:2, 416:4, 432:2, 496:2}
9: {400:4, 416:2, 448:4}
а столбцам:
0: {400:6, 416:2, 496:2}
1: {400:2, 416:4, 432:2, 448:2}
2: {352:2, 416:2, 448:6}
3: {400:2, 416:4, 432:2, 448:2}
4: {400:2, 416:4, 432:2, 448:2}
5: {400:2, 416:4, 432:2, 448:2}
6: {400:2, 416:4, 432:2, 448:2}
7: {352:2, 416:2, 448:6}
8: {400:2, 416:4, 432:2, 448:2}
9: {400:6, 416:2, 496:2}
Например, для строк можно сказать, что строка 0 может претендовать на перемещение на место строки 5 и 6. Аналогично для столбцов: столбец 0 может "встать" только на место столбца 9, столбец 1 — на место столбцов 3, 4, 5, 6, 8 и т.д. Невооруженным глазом видно, что от исходной сложности никаких (N!)^2 не осталось, т.к. лишь малое число соответствий оказываются возможными.
Ну а далее вырисовывается следующий алгоритм поиска обобщенных симметрий. Сперва необходимо построить матрицы покрытия, затем взвесить строки и столбцы ЛК соответствующими мультимножествами. Далее осуществляется перебор перестановок Px (не всех подряд, а только с учетом соответствий по мультимножествам), затем для найденной подходящей перестановки Px делается аналогичный перебор подходящих перестановок Py. Ну а далее, если искомая пара перестановок Px и Py найдена, из них, как было показано выше, вытаскивается перестановка Pv, три найденные перестановки проверяются на предмет того, что они и правда описывают обобщенную симметрию (автоморфизм) и если все получилось (так бывает не всегда), найденная тройка перестановок запоминается в качестве ключевой информации, описывающей обобщенную симметрию.
В таком виде алгоритм работает, но для некоторых квадратов с однородными матрицами покрытия трансверсалями он все равно работает долго.
квадрат 1: 0123456789123409567840173628958765904321765081943298765432105982637104350872194623491805676491278053 (горизонтально симметричный квадрат порядка 10, 4 обобщенные симметрии) — около 1 минуты
квадрат 2: 0123456789120453986735618740929478321605273098514668592473104697013258704619852383156029745982760431 (произвольный случайный квадрат, 1 тривиальная симметрия) — 0,05 с
квадрат 3: 0123456789120487956375429183062781035694863950742194582610375097643812631578294038601942754976320158 (звезда 1:10, 2 обобщенных симметрии) — 0,06 с
квадрат 4: 0123456789104523896723016745983267019845451089237654891076236732980154769832540189547610329876543210 (ЛК порядка 10 с кучей автоморфизмов от whitefox'а из примера к avtoizor'у) — очень долго (оценка — ~10! секунд)
квадрат 5: 012345678784061235431287560167534082540872316823106754356728401608453127275610843 (ДЛК порядка 9 с максимальным числом трансверсалей) — очень долго
Дополнительно сократить вычислительные затраты можно, если каким-либо образом ввести отсечения и на ранних стадиях отбрасывать неперспективные комбинации перестановок Px и Py. В данном случае можно заметить, что для "неправильных комбинаций" Px и Py перестановку Pv однозначно вытащить нельзя, т.к. на одни и те же позиции в ее составе претендуют разные значения (другими словами, например, в одном месте квадрата значение 0 отобразилось в 1, а в другом другой 0 должен быть отображен в 2, что недопустимо по сформулированным в самом начале условиям описания обобщенной симметрии). Причем, отсечение удается сделать для не полностью сформированных перестановок (точнее, по алгоритму получается так, что Px сформирована полностью, а Py — частично). Например, для приведенного выше квадрата A и перестановок
Px=[0,1,2,3,4,5,6,7,8,9]
Py=[0,3,?,?,?,?,?,?,?,?]
в результате их применения получается частично заполненный квадрат A'
0 - - 1 - - - - - -
1 - - 2 - - - - - -
4 - - 0 - - - - - -
8 - - 7 - - - - - -
7 - - 6 - - - - - -
9 - - 8 - - - - - -
5 - - 9 - - - - - -
3 - - 5 - - - - - -
2 - - 3 - - - - - -
6 - - 4 - - - - - -
из которого перестановку Pv уже (без дальнейшего спуска в глубь рекурсии и дозаполнения перестановки Py значениями) однозначно вытащить нельзя, а значит обобщенной симметрии уже нет и вычислительное время можно не тратить, производя комбинаторный возврат и переход к следующему кандидату на начальное заполнение перестановки Py. С использованием отсечений для тяжелых квадратов с однородными матрицами покрытий и большим числом обобщенных симметрий затраты времени сокращаются до приемлемых значений:
квадрат 1: 1 минута -> 0,14 с
квадрат 4: до ~10 минут (2000 различных обобщенных симметрий)
квадрат 5: до 74 с (3888 различных обобщенных симметрий)
Таким образом, получена вполне себе работающая программная реализация, с использованием которой можно заняться классификацией и исследованием обобщенных симметрий в перспективе.
PS. Ну и пару слов про avtoizor, разработанный ранее whitefox'ом... Очень интересная программная реализаций той же идеи, работает по другим принципам и быстрее, но... По ее исходникам сложно понять, _как_ она работает (тут у меня в принципе есть сомнения, что в этом разбирается кто-то кроме ее автора). Описание идей, на которых она построена, к большому сожалению утеряно вместе с железом, украденным из ИППИ, и надежд на его восстановление, как и на наказание виновных в этом практически нет. Она работает только для порядка N=10, а свойства обобщенных симметрий было бы интересно пощупать и для других порядков. Предложенная программная реализация работает по понятным принципам (по крайней мере, для меня :), полученные результаты совпадают с avtoizor'ом, в перспективе можно заняться оптимизацией кода. Будем пользовать в предстоящих экспериментах... 🙂
Загруженные файлы:
ДЛК порядка 12
0 1 2 3 4 5 6 7 8 9 10 11
1 2 0 4 5 3 8 9 10 11 6 7
2 0 1 5 3 4 10 11 6 7 8 9
11 7 9 8 10 6 5 1 3 2 4 0
10 6 8 7 9 11 0 5 1 3 2 4
9 11 7 6 8 10 4 0 5 1 3 2
5 3 4 2 0 1 7 8 9 10 11 6
4 5 3 1 2 0 11 6 7 8 9 10
3 4 5 0 1 2 9 10 11 6 7 8
6 8 10 9 11 7 1 3 2 4 0 5
7 9 11 10 6 8 3 2 4 0 5 1
8 10 6 11 7 9 2 4 0 5 1 3
имеет 1228403532 ОДЛК, что позволяет ему занять 4-е место сверху в соответствующем спектре числа ОДЛК порядка 12, который в настоящий момент включает в своем составе 4594 элементов:
http://evatutin.narod.ru/spectra/spectrum_dls_odls_n12_xxxx_known_items.txt
Расчет выполнен в проекте RakeSearch (https://rake.boincfast.ru/rakesearch/).
#ODLS
Загруженные файлы: