Естественные науки

Школьные учителя математики не хотят с головоломкой "пятнашки" разбираться. Предлагаю вам отсортировать массив.

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

Пронумеруем все занятые фишками поля на доске змейкой. Верхнюю строку слева направо, следующую строку справа налево и т. д.
Всего 15 полей вне зависимости от положения свободной клетки.

Рассмотрим элементарные ходы. Смещение пустой клетки на одну позицию вдоль змейки не меняет порядок фишек в змейке и позволяет загнать пустую клетку в любое место змейки.
Остальные элементарные ходы превращаются в "хорошие" перестановки фишек в змейке.
Например, перестановка пустой клетки из первой строки во вторую или обратно производит следующую перестановку фишек в змейке:
3-ю, 4-ю, 5-ю фишки в змейке переставляет по циклу, буду обозначать такую перестановку (3, 4, 5) либо:
переставляет по циклу (2, 3, 4, 5, 6) фишки в змейке, либо переставляет по циклу (1, 2, 3, 4, 5, 6, 7, 8) фишки.
Понятно, что обратный ход соответсвует обращению цикла, об этом помним и не спамим.

Перестановка пустой клетки из второй строки в третью или обратно соответствует одной из след. перестановок фишек в змейке:
(7, 8, 9), либо (6, 7, 8, 9, 10), либо (5, 6, 7, 8, 9, 10, 11).

Аналогично для 3-й и 4-й строки имеем циклы (11, 12, 13) и т. д.

Все эти перестановки четные, осталось ими породить вообще все четные из пятнадцати.

Поставим окончательную задачу так: имеется массив из 15 уникальных элементов, известно, что перестановка элементов массива четная.
Требуется отсортировать массив, используя допустимые операции, указанные выше - например, операцию, переставляющую 3-й, 4-й и 5-й элемент по циклу и т. л.
Можно алгоритм сортировки оформить словесно, можно в виде программы, которую можно выполнить онлайн где-нибудь на ideone.com или аналогичном сайте.
Женька Саблин
Женька Саблин
396
Коммутатором перестановок a и b, обозн. [a, b], называем перестановку aba^-1b^-1, произведение ab понимается в стандартном смысле композиции "a после b".

Тогда:
[(1 2 3 4 5 6 7), (2 3 4 5 6)] = (2 7 3)
[(1 2 3 4 5 6 7), (3 4 5)] = (3 6 4)
[(1 2 3 4 5 6 7), (7 8 9)] = (1 8 7)
[(2 3 4 5 6), (6 7 8 9 10)] = (2 7 6)
[(3 4 5), (5 6 7 8 9 10 11)] = (3 6 5)
[(5 6 7 8 9 10 11), (6 7 8 9 10)] = (6 11 7)
[(5 6 7 8 9 10 11), (7 8 9)] = (7 10 8)
[(5 6 7 8 9 10 11), (11 12 13)] = (5 12 11)
[(6 7 8 9 10), (10 11 12 13 14)] = (6 11 10)
[(7 8 9), (9 10 11 12 13 14 15)] = (7 10 9)
[(9 10 11 12 13 14 15), (10 11 12 13 14)] = (10 15 11)
[(9 10 11 12 13 14 15), (11 12 13)] = (11 14 12)

А циклы справа от равенств порождают группу четных перестановок из 15 по двум причинам:
- каждое число от 1 до 15 входит хотя бы в один из циклов
- каждый из цкилов (кроме первого) содержит число, входящее в хотя бы один из предыдущих.

Как ими сортировать, сообразите... Смотрим сперва в конец списка - в последний цикл. Там из чисел, не входящих ни в один из пред. циклов, видим только число 14.
Загоняем циклами фишку 14 на 14-ю позицию

Затем про последний цикл забываем, сортируем оставшимися циклами оставшиеся фишки и т. д..

Код здесь:
https://ideone.com/HiRWqX
НД
Николай Дусалиев
34 449
Лучший ответ
Между двумя состояниями есть невзаимная операция — перемена местами двух соседних, делящая их на два разных порядковых набора. Вот и всё — не пересекаются они.
Евгений Дедков
Евгений Дедков
87 472
Женька Саблин Не понял. Я предлагаю собрать головоломку ровно из тех всевозможных начальных расположений фишек, из которых задача разрешима.
Доказано, что задача не имеет решения.

З. Ы. когда то читал доказательство, но не помню. Что то по поводу чётности.
ОМ
Ольга Меньшикова
8 679
Женька Саблин Вы чииали о другом - например, если в собранной головоломке поменять две фишки местами, то из такого расположения головоломку не собрать.

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

Т. к. в группе перестанрвок из n (n >1) существует ровно одна подгруппа индекса 2 (т. е. в которой в 2 раза меньше элементов, чем в самой группе), и эта подгруппа является группой четных перестановок, то моя задача разрешима.

Похожие вопросы