- PVSM.RU - https://www.pvsm.ru -
Ханойские башни
Про знаменитую игру Эдуарда Люка́ на Хабре не писа́л только ленивый [1]. Кажется, все покровы сорваны и что-то ещё по поводу алгоритма добавить уже невозможно. Но нет, у данной темы есть ещё скрытые ресурсы. Сегодня, в частности, мы переделаем алгоритм решения этой головоломки в полноценную сортировку. (Зачем? Just for fun. В пятницу можно.)
Данный пост посвящается памяти истинного гуру программирования Андрея Mrrl [2] Астрелина, который когда-то мне просто и доходчиво объяснил этот алгоритм. Псевдокод ниже по тексту — его авторства.
В классической головоломке изначально диски на первом шесте уже упорядочены. Но мы разрешим им быть нанизанными в любом порядке.
Кроме того, размеры дисков предполагаются уникальными. Не будем цепляться за это ограничение и разрешим повторы.
Если позволить себе только эти две вольности, то начальные условия головоломки можно интерпретировать как массив (диски — это числа), а задача сводится к тому, что данный массив требуется отсортировать.
Остальные условия мы (почти) не меняем:
Наша задача: взять классический рекурсивный алгоритм головоломки…
def hanoi(n, source, helper, target):
if n > 0:
hanoi(n - 1, source, target, helper)
if source:
target.append(source.pop())
hanoi(n - 1, helper, source, target)
… и превратить его в сортировку!
На самом деле, от того что мы разрешили начальную неупорядоченность и повторы для размеров дисков — от этого принципиально не поменялось ничего. По большому счёту задача решаема всё тем же классическим рекурсивным способом. Самое главное что нужно понять — все перемещения дисков разделяются на несколько этапов, каждый из которых — это классичекий «ханой» в миниатюре.
То есть мы на каждом этапе рассматриваем не все имеющиеся диски, а только совокупность тех из них, которые удовлетворяют старым условиям. Отсортировав по классике это небольшое множество мы приблизим общее состояние системы к классической головоломке. Тогда мы опять берём то множество дисков, которое соответствует классике и применяем известный алгоритм вновь. И это множество будет бо́льшим, чем на предыдущем шаге! И так повторяем до тех пор, пока все диски на всех шестах вдруг не станут отличаться от классического состояния.
Нарушенная изначально система (тем, что на входе диски не упорядочены) самовосстанавливается с каждой итерацией.
Что касается разрешения повторов, то это вообще не имеет никакого значения. Потому что подряд идущие одинаковые диски мы просто перемещаем как один диск.
Назовем столбики A, B, C (A в начале непустой).
Введем операции:
А->С() — переложить один диск с А на С.
top(A), top(С) — размер верхнего диска А или С. Если столбик пуст, то этот размер = MaxInt.
В->С(К) — переложить с В на С все диски, размер которых меньше К (мы это можем сделать, если верхние диски А и С не меньше К).
swap() — переставить столбики В и С (или переименовать их — нам ведь все равно, где окажутся диски).
while(A) — цикл пока А не пуст.
Тогда работает такой алгоритм:
//С каждым перемещённым диском с шеста A всё более восстанавливаем "ханойскую" систему
while(A) {
K = top(A);
//Мини-"ханой" для группы дисков
while(top(C) < K){
B->C(top(C));
swap();
}
A->C();
}
//Система восстановлена. Завершение - классический "ханой"
while(C) {
B->C(top(C));
swap();
}
© Mrrl [2]
В худшем случае сортировка стремится к сложности по времени для классического алгоритма, который хоть прост и изящен, но при этом максимально неэффективен. Насчёт лучшей и средней предположить затрудняюсь.
Насчёт памяти можно сказать, что если используется рекурсия, то и затраты будут соответствующие.
Свой вариант на Python пока не написал (сделаю это позже). Однако ниже в разделе «Ссылки» накидал несколько ссылок, по которым можно посмотреть имплементации на различных языках. Особенно интересен вариант на Джаве. Автор не стал брать за основу общеизвестный рекурсивный способ для решения головоломки, а построил кратчайшее дерево путей. Предположительно, это является самым эффективным решением, если писать сортировку в стиле «Ханойской башни».
Название | Сортировка «Ханойская башня», Tower of Hanoi sort | |
---|---|---|
Автор идеи | Эдуард Люка́ | |
Класс | Сортировки вставками | |
Сравнения | Есть | |
Временна́я сложность | лучшая | ? |
средняя | ? | |
худшая | O(2n) |
Tower of Hanoi [3] / Ханойская башня [4]
Реализации: Си [5], Java vs C++ vs Python [6], Python [7].
В приложении AlgoLab данная сортировка теперь доступна. Хотя она относится к классу сортировок вставками, по причине экстравагантности алгоритма она помещена в раздел «Прочие сортировки». Ещё там есть ограничение — числа в сортируемом массиве могут быть только от 1 до 5 (связано с непростой прорисовкой дисков). Другие числа всё равно будут заменены на эти.
Также есть ограничение на размер массива — не более 20-ти элементов. Сделано это сугубо в Ваших же интересах — если возьмёте слишком большой массив, то, может так статься, что сортировать его придётся до глубокой старости.
Автор: valemak
Источник [14]
Сайт-источник PVSM.RU: https://www.pvsm.ru
Путь до страницы источника: https://www.pvsm.ru/programmirovanie/300829
Ссылки в тексте:
[1] не писа́л только ленивый: https://habr.com/search/?q=%D1%85%D0%B0%D0%BD%D0%BE%D0%B9%D1%81%D0%BA%D0%B0%D1%8F+%D0%B1%D0%B0%D1%88%D0%BD%D1%8F
[2] Mrrl: https://habr.com/users/mrrl/
[3] Tower of Hanoi: https://en.wikipedia.org/wiki/Tower_of_Hanoi
[4] Ханойская башня: https://ru.wikipedia.org/wiki/%D0%A5%D0%B0%D0%BD%D0%BE%D0%B9%D1%81%D0%BA%D0%B0%D1%8F_%D0%B1%D0%B0%D1%88%D0%BD%D1%8F
[5] Си: https://gist.github.com/jcmvbkbc/8050585
[6] Java vs C++ vs Python: https://codegolf.stackexchange.com/questions/25157/tower-of-hanoi-sort
[7] Python: https://stackoverflow.com/questions/46902398/hanoi-sort-algirithm
[8] Excel-приложение AlgoLab.xlsm: https://habr.com/post/414447/
[9] Сортировки обменами: https://habr.com/post/414653/
[10] Сортировки вставками: https://habr.com/post/415935/
[11] Сортировка библиотекаря: https://habr.com/post/416653/
[12] Пасьянсная сортировка: https://habr.com/post/431094/
[13] Сортировки выбором: https://habr.com/post/422085/
[14] Источник: https://habr.com/post/431694/?utm_campaign=431694
Нажмите здесь для печати.