задача дня-13

[falcao]

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

Comments

[c_3_c]

n = 15:

15 11 4 7 5 9 1 8 3 13 14 12 2 10 6
3 14 13 15 11 4 7 5 9 1 8 6 2 10 12
15 1 14 3 11 13 9 4 5 7 8 6 2 10 12
14 9 5 4 1 3 13 11 15 7 8 6 2 10 12

[falcao]

Спасибо за варианты. Если я правильно понимаю, это полный "улов" для n=15.

Интересно было бы найти первое значение n, для которого варианты отсутствуют (оно точно существует).

[c_3_c]

Для n = 15 приведены варианты, которые найдены за 20 часов полнопереборной программой. Для n = 12 - все.

А вот теперь все:

15 11 4 7 5 9 1 8 3 13 14 12 2 10 6
3 14 13 15 11 4 7 5 9 1 8 6 2 10 12
15 1 14 3 11 13 9 4 5 7 8 6 2 10 12
14 9 5 4 1 3 13 11 15 7 8 6 2 10 12
12 11 13 9 4 5 3 2 1 15 7 8 6 10 14

[falcao]

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

[relf]

По крайней мере для n <= 23 такие есть:

n=16: [1, 9, 4, 5, 3, 2, 13, 11, 15, 7, 8, 6, 10, 14, 16, 12]
n=17: [9, 11, 16, 17, 15, 2, 13, 1, 12, 5, 7, 3, 4, 14, 6, 8, 10]
n=18: [6, 1, 5, 7, 3, 11, 16, 17, 15, 2, 13, 9, 4, 14, 18, 10, 8, 12]
n=19: [4, 15, 13, 17, 9, 8, 1, 7, 2, 19, 3, 16, 11, 5, 6, 14, 10, 18, 12]
n=20: [4, 7, 5, 9, 1, 17, 15, 19, 11, 8, 3, 13, 20, 6, 14, 10, 18, 2, 16, 12]
n=21: [3, 4, 17, 15, 2, 13, 21, 5, 16, 9, 7, 20, 1, 19, 11, 8, 14, 10, 18, 12, 6]
n=22: [1, 4, 15, 17, 13, 21, 5, 16, 9, 7, 11, 3, 19, 20, 18, 22, 14, 8, 6, 2, 10, 12]
n=23: [7, 3, 11, 13, 9, 17, 19, 15, 23, 22, 1, 21, 5, 16, 14, 18, 10, 8, 2, 6, 4, 20, 12]

[ditour]

Что-то не придумывается никаких неочевидных оптимизаций. "В лоб" за полчаса досчиталось до n = 47, первая неудача была на 30, последнее успешное решение на 38.

P.S. Пока отвлёкся, нашлось решение для n = 51.

[relf]

Из оптимизаций можно попробовать "встречу посередине" - посчитать только лишь половины перестановок и потом посомотреть какие из половинок можно скомпоновать.

[ditour]

Я не проверял вообще все перестановки, а заполнял последовательность, возвращаясь при заходе в тупик. До n = 31 на моём лэптопе весь расчёт занимает меньше секунды.

[relf]

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

[relf]

Вот изящная программка на Sage с использованием рекурсивно-перечислимых множест и MapReduce. Для примера взято n=21, но можно заменить на любое другое.
Особенно мощь этого подхода можно прочуствовать на многопроцессорной системе, где MapReduce автоматически распараллеливается и всё сильно ускоряется.

[falcao]

Мне, к сожалению, этот аппарат не оценить, так как я с ним совершенно не знаком. Но хотя бы со стороны понаблюдаю!

[c_3_c]

Впечатляюще!

[zhiltsov]

Привожу количество решений для каждого n.
Сами решения тоже есть, если что.

3 6
4 6
5 15
6 14
7 9
8 28
9 16
10 37
11 51
12 13
13 34
14 44
15 5
16 20
17 24
18 15
19 45
20 52
21 2
22 8
23 34
24 21
25 15
26 13
27 1
28 2
29 1
30 0
31 0
32 0
33 0
34 1
35 0
36 0
37 3
38 7
39 0

[falcao]

Весьма интересно! Можно ли привести решения для тех случаев, когда оно единственное? То есть при n=27, 29, 34. Это могло бы помочь построить единую серию для какого-то набора случаев, если там просматривается закономерность.

[zhiltsov]

27 1
[9, 19, 17, 2, 15, 7, 23, 12, 11, 1, 21, 16, 5, 27, 13, 14, 25, 3, 22, 26, 18, 8, 10, 6, 4, 20, 24]

29 1
[21, 20, 1, 19, 15, 4, 11, 13, 9, 17, 28, 23, 5, 18, 7, 29, 27, 2, 25, 3, 22, 8, 14, 26, 16, 10, 6, 24, 12]

34 1
[33, 23, 10, 13, 7, 6, 1, 29, 27, 2, 25, 21, 4, 17, 15, 19, 11, 8, 3, 5, 31, 9, 22, 14, 30, 26, 34, 18, 16, 20, 12, 28, 32, 24]