Сортировка ханойских башен

[Wran]

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

P. S. Решил несколько задач про ханойские башни. Решались нетрудно и, в основном, рекурсией. С этой не могу разобраться.

[_hum_]

Wran в сообщении #605390 писал(а):

Класть больший диск на меньший запрещается.

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

[Профессор Снэйп]

_hum_ в сообщении #605502 писал(а):

Например, как быть со случаем когда исходная конфигурация - обычная ханойская башня, у которой самый малый диск перемещен в основание?

А что здесь плохо? Перекладываем диски, кроме двух последних (самого большого и самого маленького) на другую палку, затем самый большой на свободную, затем самый маленький в верхушку пирамиды (в которой все, кроме самого большого), далее очевидно.

[Профессор Снэйп]

Пусть $s$ - перестановка, соответствующая изначальному упорядочению ханойских башен. Блоком считаем максимальный кусок $s(i), \ldots, s(j)$, для которого $s(i) > s(i+1) > \ldots > s(j)$. Задача сводится к перекладыванию всех блоков, то есть к перемещению блоков с параллельным их упорядочиванием.

[_hum_]

Профессор Снэйп в сообщении #605541 писал(а):

_hum_ в сообщении #605502 писал(а):

Например, как быть со случаем когда исходная конфигурация - обычная ханойская башня, у которой самый малый диск перемещен в основание?

А что здесь плохо? Перекладываем диски, кроме двух последних (самого большого и самого маленького) на другую палку, затем самый большой на свободную, затем самый маленький в верхушку пирамиды (в которой все, кроме самого большого), далее очевидно.

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