Метод точных попарно ортогональных покрытий массива

[whitefox]

Nataly-Mak в сообщении #1032369 писал(а):

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

Вот я и предложил алгоритм проверки найденной пары точных покрытий на возможность построения идеального квадрата.

Nataly-Mak в сообщении #1032369 писал(а):

А вы посчитали, сколько существует пар точных ортогональных покрытий массива из 81 чесел?

Nataly-Mak в сообщении #1032369 писал(а):

Вы можете найти все пары точных ортогональных покрытий (чтобы потом их проверить на предмет построения идеального квадрата)?

Это уже немного другая задача.

[Nataly-Mak]

whitefox в сообщении #1032370 писал(а):

Nataly-Mak в сообщении #1032369 писал(а):

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

Вот я и предложил алгоритм проверки найденной пары точных покрытий на возможность построения идеального квадрата.

Так, стоп. Я пока ничего не понимаю.

Вы предложили алгоритм проверки пары точных ортогональных покрытий массива на предмет построения идеального квадрата. Это я поняла.
Но пара-то такая у нас, наверное, не одна. Подозреваю, что пар таких будет много-много.
О чём и спросила.
Прежде чем пару ортогональных покрытий проверять, её надо найти. И найти надо их все и все проверить, чтобы решить задачу полностью.

А теперь скажите, что именно я не так понимаю?

[whitefox]

Вы поняли совершенно правильно — предложенный алгоритм решает только частную задачу. Именно ту, для решения которой Вы ищете к уже найденной паре ортогональных покрытий ещё пару. И решает эту задачу менее чем за секунду (если моя оценка сложности верна), а не за часы.

Общую же задачу считаю безнадёжной для полного перебора, имхо.

[Nataly-Mak]

whitefox в сообщении #1032375 писал(а):

Вы поняли совершенно правильно — предложенный алгоритм решает только частную задачу. Именно ту, для решения которой Вы ищете к уже найденной паре ортогональных покрытий ещё пару. И решает эту задачу менее чем за секунду (если моя оценка сложности верна), а не за часы.

Всё дело в том, что для известных мне пар комплект 4-х точных попарно ортогональных покрытий не находится ни за секунды, ни за часы.
Нет ещё ни одного такого комплекта!
Ну, реализуете вы ваш алгоритм проверки, допустим. И допустим он будет работать у вас секунды. Так, начали проверять пары (перед проверкой вы их, естественно, находите). Одну проверили, вторую, третью... а идеального квадрата нет а, следовательно, и комплекта 4-х покрытий тоже нет.
Ну и в чём эффект? Пусть алгоритм работает секунды, а пар будут миллиарды, все их всё равно не проверить.

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

Существование хотя бы одного такого комплекта - это выполнение необходимого условия. Тогда можно искать дальше.
Несуществование такого комплекта - это невыполнение необходимого условия, и дальше искать нечего.

-- Вт июн 30, 2015 12:40:06 --

Кстати, по поводу преобразований. Я не вникала пока и не считала преобразования ассоциативного квадрата 9-го порядка.
Но вот для ассоциативных квадратов 10-го порядка мы с коллегами пытались применить все возможные перестановки строк/столбцов, дабы получить идеальный квадрат.
Коллеги утверждают, что всего перестановок симметричных строк/столбцов в ассоциативном квадрате 10-го порядка будет 14745600.

А сколько их будет в ассоциативном квадрате 9-го порядка?

[whitefox]

Nataly-Mak в сообщении #1032378 писал(а):

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

Существование хотя бы одного такого комплекта - это выполнение необходимого условия. Тогда можно искать дальше.
Несуществование такого комплекта - это невыполнение необходимого условия, и дальше искать нечего.

Вот это-то и вызывает большое сомнение. Сомнение в существовании эффективного способа проверки невозможности комплекта из четырёх точных ортогональных покрытий для данного набора чисел. Опять же, имхо.

[Nataly-Mak]

Ну так ведь и применение вашего алгоритма вызывает большое сомнение в том, что мы так сразу и наткнёмся на идеальный квадрат. А если нет - сразу не наткнёмся - значит, надо проверять все пары ортогональных покрытий, а это тот же самый полный перебор, эффективность которого очень сомнительна.

[whitefox]

Nataly-Mak в сообщении #1032378 писал(а):

Коллеги утверждают, что всего перестановок симметричных строк/столбцов в ассоциативном квадрате 10-го порядка будет 14745600.

А сколько их будет в ассоциативном квадрате 9-го порядка?

Первоначально я получил для 10-го порядка такое же число, но потом понял, что пара симметрий не учтена, и это число можно уменьшить в четыре раза. Для 9-го порядка число привёл выше:

whitefox в сообщении #1032357 писал(а):

Всего получается $192^2=36\ 864$ варианта.

Общая формула такая:

$$(m!\cdot2^{m-1})^2,\quad \text{где}\quad m=\left\lfloor\frac{n}{2}\right\rfloor$$

-- 30 июн 2015, 12:05 --

Nataly-Mak в сообщении #1032383 писал(а):

Ну так ведь и применение вашего алгоритма вызывает большое сомнение в том, что мы так сразу и наткнёмся на идеальный квадрат. А если нет - сразу не наткнёмся - значит, надо проверять все пары ортогональных покрытий, а это тот же самый полный перебор, эффективность которого очень сомнительна.

Мой алгоритм и не претендует на решение общей задачи. Он, всего лишь, эффективно решает частную задачу.

[Nataly-Mak]

Вы утверждаете, что проверить 36864 варианта квадрата 9-го порядка на пандиагональность (предварительно получив каждый вариант перестановкой строк/столбцов) - дело нескольких секунд?
Да, перед этим ещё надо найти пару ортогональных покрытий и построить из неё ассоциативный квадрат.
Программу в студию!

-- Вт июн 30, 2015 13:11:21 --

Цитата:

Он, всего лишь, эффективно решает частную задачу.

Решение частной задачи в студию!

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

Кстати, если вы нашли идеальный квадрат - это уже полное решение задачи, а не части её. Ведь у нас задача-то - найти идеальный квадрат

[whitefox]

Nataly-Mak в сообщении #1032391 писал(а):

Да ни черта он не решает, если идеального квадрата не существует.

Nataly-Mak в сообщении #1032391 писал(а):

Да, перед этим ещё надо найти пару ортогональных покрытий

Отрицательный результат — это тоже результат.
Ибо задача, которую решает мой алгоритм:

whitefox в сообщении #1032357 писал(а):

проверить пару ортогональных покрытий на возможность построения идеального квадрата

И заметьте, он не ищет пару ортогональных покрытий, всё это подаётся на его вход в уже готовом виде.

Nataly-Mak в сообщении #1032391 писал(а):

Программу в студию!

Nataly-Mak в сообщении #1032391 писал(а):

Решение частной задачи в студию!

Пожалуйста, не берите меня на слабо.

-- 30 июн 2015, 12:37 --

Nataly-Mak в сообщении #1032391 писал(а):

Кстати, если вы нашли идеальный квадрат - это уже полное решение задачи, а не части её. Ведь у нас задача-то - найти идеальный квадрат

Так счастливо совпало, что если идеальный квадрат найден, то это является решением и общей задачи — проверить массив чисел на возможность построения идеального квадрата, и частной задачи — проверить пару точных покрытий на возможность построения идеального квадрата. А если квадрат не найден, то это, увы, решение только частной задачи.

[Nataly-Mak]

whitefox в сообщении #1032399 писал(а):

Ибо задача, которую решает мой алгоритм:

whitefox в сообщении #1032357 писал(а):

проверить пару ортогональных покрытий на возможность построения идеального квадрата

И заметьте, он не ищет пару ортогональных покрытий, всё это подаётся на его вход в уже готовом виде.

Я это поняла уже давно - что ваш алгоритм проверяет один ассоциативный квадрат на предмет получения из него идеального.

Но! Я тут, кажется, такую задачу вообще не ставила. Или ставила? Что-то не припомню.
У меня задача такая: найти минимальный идеальный квадрат 9-го порядка или доказать, что он не существует.

Ваш алгоритм в этой задаче ничего не решает. Проверка одной ортогональной пары точных покрытий массива на получение из неё идеального квадрата абсолютно ничего не даёт для решения поставленной задачи. И я уже много раз пыталась это объяснить. Ну, проверили мы одну пару, вторую пару... Нет идеального квадрата. И дальше что делать?

Цитата:

Пожалуйста, не берите меня на слабо.

Надеюсь, у вас с чувством юмора всё в порядке (там стояли смайлики).

-- Вт июн 30, 2015 13:45:57 --

Цитата:

А если квадрат не найден, то это, увы, решение только частной задачи.

Да какой же?? Проверка ассоциативного квадрата на получение из него идеального?

Ну ладно, не будем "дуб да мочало - начинай всё сначала"

-- Вт июн 30, 2015 13:54:36 --

Цитата:

Отрицательный результат — это тоже результат.

Только для одной пары ортогональных покрытий - нет! Это ничего нам не даёт.
Вот если вы проверите все ортогональные пары и получите отрицательный результат - тогда да! Это будет результат.

[whitefox]

Nataly-Mak в сообщении #1032403 писал(а):

Но! Я тут, кажется, такую задачу вообще не ставила. Или ставила?

Ставили:

Nataly-Mak в сообщении #1032014 писал(а):

Необходимо написать процедуру проверки комплекта из 4-х точных попарно ортогональных покрытий массива на предмет составления идеального квадрата.

Предложенный алгоритм решает эту задачу путём проверки всех шести пар ортогональных покрытий.

Nataly-Mak в сообщении #1032403 писал(а):

Ваш алгоритм в этой задаче ничего не решает. Проверка одной ортогональной пары точных покрытий массива на получение из неё идеального квадрата абсолютно ничего не даёт для решения поставленной задачи. И я уже много раз пыталась это объяснить.

И я тоже уже много раз пытаюсь Вам объяснить, что предложен алгоритм для решения не Вашей общей задачи, а Вашей частной задачи — проверки возможности построения идеального квадрата по известным четырём, трём, и даже двум точным ортогональным покрытиям.

[Nataly-Mak]

whitefox в сообщении #1032419 писал(а):

Nataly-Mak в сообщении #1032403 писал(а):

Но! Я тут, кажется, такую задачу вообще не ставила. Или ставила?

Ставили:

Nataly-Mak в сообщении #1032014 писал(а):

Необходимо написать процедуру проверки комплекта из 4-х точных попарно ортогональных покрытий массива на предмет составления идеального квадрата.

Предложенный алгоритм решает эту задачу путём проверки всех шести пар ортогональных покрытий.

Проверка построения идеального квадрата из 4-х попарно ортогональных покрытий и из пары ортогональных покрытий - это всё-таки разные задачи.
К тому же, я имела в виду, что данная процедура будет строить квадрат и в том случае, когда постороение его возможно. А если невозможно, будет констатировать факт невозможности построения.

Ещё раз: мне не надо проверять пары ортогональных покрытий на получение из них идеального квадрата.
Для решения поставленной мной задачи это ровным счётом ничего не даёт, ну если, конечно, вы не скажете, что в состоянии проверить все ортогональные пары покрытий.

Это всё равно, как я раньше пыталась проверить ВСЕ магические квадраты 6-го порядка на наличие среди них пандиагональных.

-- Вт июн 30, 2015 15:00:35 --

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

-- Вт июн 30, 2015 15:02:34 --

Вот полная цитата:

Цитата:

Необходимо написать процедуру проверки комплекта из 4-х точных попарно ортогональных покрытий массива на предмет составления идеального квадрата. Иначе даже если мы получим такой комплект для искомого минимального решения с магической константой $S=12249$ , нам нечем будет его проверить.

Теперь понятно, о какой процедуре идёт речь?

[whitefox]

Nataly-Mak в сообщении #1032428 писал(а):

Проверка построения идеального квадрата из 4-х попарно ортогональных покрытий и из пары ортогональных покрытий - это всё-таки разные задачи.

Проверка пары это примитив для проверки четвёрки, нужно всего лишь проверить шесть пар.

Nataly-Mak в сообщении #1032428 писал(а):

К тому же, я имела в виду, что данная процедура будет строить квадрат и в том случае, когда постороение его возможно. А если невозможно, будет констатировать факт невозможности построения.

Предложенная процедура именно это и делает, она либо сообщит, что квадрат построить по данным четырём покрытиям не возможно, либо предъявит идеальный квадрат.

Nataly-Mak в сообщении #1032428 писал(а):

Ещё раз: мне не надо проверять пары ортогональных покрытий на получение из них идеального квадрата.
Для решения поставленной мной задачи это ровным счётом ничего не даёт, ну если, конечно, вы не скажете, что в состоянии проверить все ортогональные пары покрытий.

Ещё раз: предложенный алгоритм является примитивом для построения алгоритма проверяющего четвёрки точных покрытий на возможность построения идеального квадрата. И это является решением поставленной Вами частной задачи. И, пожалуйста, не делайте вид будто бы я утверждаю о возможности решить этим алгоритмом общую задачу, сказано было прямо противоположное:

whitefox в сообщении #1032375 писал(а):

Общую же задачу считаю безнадёжной для полного перебора, имхо.

Nataly-Mak в сообщении #1032428 писал(а):

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

И я предложил алгоритм который может реализовывать такая программа. Но раз у Вас есть куда лучший метод для решения Вашей частной задачи, то на своём я настаивать не смею.

Засим, откланиваюсь.

[Nataly-Mak]

Цитата:

Засим, откланиваюсь.

То есть мне отвечать уже не нужно? Интересный выход из дискуссии.
Но всё-таки отвечу.

Цитата:

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

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

О предложенном вами алгоритме проверки ассоциативного квадрата (или что то же - пары ортогональных покрытий) на передмет получения из него идеального квадрата я знала задолго до того, как вы его предложили. Уже рассказала выше, что мы с коллегами пытались применить этот алгоритм к ассоциативному квадрату 10-го порядка. То есть коллеги (трое) написали программу, реализующую как раз этот самый алгоритм: перестановка всех симметричных строк/столбцов и проверка полученных вариантов на пандиагональность. Это было уже больше месяца назад. Результат был такой: максимальное количество правильных диагоналей - 8 штук из 20. Это вполне ожидаемый результат.
Такой же примерно будет и при проверке ассоциативных квадратов 9-го порядка, примерно 99% из всех, если не больше. И только среди мизерной части всех ассоциативных квадратов могут оказаться идеальные, если вообще могут для данного случая (минимального идеального квадрата).

И наконец, я исхожу всё-таки от комплектов из 4-х попарно ортогональных покрытий, ибо именно такие комплекты необходимы для построения идеального квадрата. Надо найти такой комплект, а уж проверить его - дело второе и, думаю, не такое уж сложное.

[Nataly-Mak]

Nataly-Mak в сообщении #1031776 писал(а):

... можно написать программку, которая будет строить по двум точным ортогональным покрытиям ассоциативный квадрат. Это должна быть простая программка. Ведь вручную всё делается так просто! Процедура очень занятная
Попробуйте! Правда, очень занимательно. Главное - успех всегда обеспечен!
И программка должна быть красивая.
Кто готов написать красивую программку?

Никто не хочет написать очень простенькую и красивую программку
Пришлось самой написать. Действительно, всё оказалось очень просто.
Вот код программы:

(Оффтоп)

#COMPILE EXE
#DIM NONE

FUNCTION PBMAIN () AS LONG
 LOCAL I,J,K,L AS LONG

DIM A(9,9) AS LONG, B(9,9) AS LONG, C(9,9) AS LONG

OPEN "A31.TXT" FOR INPUT AS #1
FOR I=1 TO 9
FOR J=1 TO 9
INPUT #1,A(I,J)
NEXT J
NEXT I
CLOSE #1

OPEN "A32.TXT" FOR INPUT AS #1
FOR I=1 TO 9
FOR J=1 TO 9
INPUT #1,B(I,J)
NEXT J
NEXT I
CLOSE #1

OPEN "A33.TXT" FOR OUTPUT AS #1

FOR L=1 TO 9
FOR K=1 TO 9
FOR I=1 TO 9
FOR J=1 TO 9
IF A(L,I)=B(K,J) THEN C(L,K)=A(L,I):GOTO 10
NEXT J
NEXT I
PRINT #1,"OSHIBKA!":GOTO 1000
10 NEXT K
NEXT L

FOR I=1 TO 9
FOR J=1 TO 9
PRINT #1,C(I,J);
NEXT J
PRINT #1,
NEXT I

1000 CLOSE #1
END

END FUNCTION

Пример

даны два точных ортогональных покрытия массива, цепочки нормализованы:

23 719 743 1013 1223 1901 1913 2081 2633
29 479 659 1103 1493 1949 2069 2129 2339
59 191 281 389 1109 2459 2549 2591 2621
509 683 911 1151 1433 1439 1559 2153 2411
11 113 179 449 1361 2273 2543 2609 2711
311 569 1163 1283 1289 1571 1811 2039 2213
101 131 173 263 1613 2333 2441 2531 2663
383 593 653 773 1229 1619 2063 2243 2693
89 641 809 821 1499 1709 1979 2003 2699

29 59 101 683 1811 1913 2243 2699 2711
89 389 593 659 1571 2081 2153 2273 2441
113 773 1013 1283 1433 1493 1613 1979 2549
179 311 653 719 1499 1559 2339 2459 2531
131 509 821 1103 1361 1619 1901 2213 2591
191 263 383 1163 1223 2003 2069 2411 2543
173 743 1109 1229 1289 1439 1709 1949 2609
281 449 569 641 1151 2063 2129 2333 2633
11 23 479 809 911 2039 2621 2663 2693

Вводим покрытия в программу и мгновенно получаем следующий ассоциативный квадрат:

1913 2081 1013 719 1901 1223 743 2633 23
29 659 1493 2339 1103 2069 1949 2129 479
59 389 2549 2459 2591 191 1109 281 2621
683 2153 1433 1559 509 2411 1439 1151 911
2711 2273 113 179 1361 2543 2609 449 11
1811 1571 1283 311 2213 1163 1289 569 2039
101 2441 1613 2531 131 263 173 2333 2663
2243 593 773 653 1619 383 1229 2063 2693
2699 89 1979 1499 821 2003 1709 641 809

$K=2722$, $S=12249$

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

Цитата:

Гораздо сложнее будет программа для процедуры построения идеального квадрата из комплекта 4-х точных попарно ортогональных покрытий массива. Да тут ещё и успех вряд ли всегда будет обеспечен. Но пока не утверждаю.
Вот для пандиагональных квадратов 7-го порядка это точно установлено: не из каждого набора 4-х точных попарно ортогональных покрытий массива можно построить пандиагональный квадрат. Найден конкретный пример, доказывающий это утверждение.

Выше приведён комплект из 4-х точных попарно ортогональных покрытий массива (правда это не для искомого минимального квадрата, а для решения с дырками).
Надо написать аналогичную процедуру построения из этих покрытий идеального квадрата. Это сложно (для меня), я пока не знаю, как это сделать. К тому же, тут, скорее всего, квадрат не всегда построится.
Но для приведённого комплекта квадрат построится.

Если при построении ассоцитивного квадрата мы пересекаем только цепочки-строки и цепочки-столбцы, при построении идеального квадрата нам надо пересекать цепочки-строки, цепочки-столбцы, цепочки-диагонали прямые и цепочки-диагонали обратные.