Sort "Tower of Hanoi"


    Towers of Hanoi
    About the famous game of Edward Luke on Habré did not write just lazy . It seems that all covers have been torn off and it is no longer possible to add something else about the algorithm. But no, this topic has more hidden resources. Today, in particular, we will remake the algorithm for solving this puzzle into a complete sorting. (Why? Just for fun. On Friday, you can.)

    This post is dedicated to the memory of the true programming guru Andrei Mrrl Astrelin, who once explained this algorithm to me simply and intelligibly. The pseudo-code below is its authorship.


    In the classic puzzle, initially the discs on the first pole are already ordered. But we will allow them to be strung in any order.

    In addition, disk sizes are assumed to be unique. We will not cling to this restriction and allow repetitions.

    If you allow yourself only these two liberties, then the initial conditions of the puzzle can be interpreted as an array (the disks are numbers), and the task boils down to the need to sort the given array.

    The rest of the conditions we (almost) do not change:

    • We have two auxiliary poles (a pair of empty arrays).
    • We can transfer discs one by one.
    • Put only smaller ones for the most part (since we have resolved the same disk sizes, you can also place the movable disk on top of others on the same size).
    • We have the right to compare the portable disk only with the uppermost disks (that is, all 3 arrays are stacks).

    Our task: to take the classic recursive puzzle algorithm ...

    defhanoi(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)

    ... and turn it into a sort!

    In fact, from the fact that we resolved the initial disorder and repetitions for the sizes of the disks - nothing fundamentally changed from this. By and large, the problem is solved in the same classical recursive way. The most important thing to understand is that all movements of the disks are divided into several stages, each of which is a classic “khan” in miniature.

    That is, at each stage, we do not consider all the available disks, but only the totality of those that satisfy the old conditions. Having sorted this small set according to the classics, we will bring the overall state of the system closer to the classic puzzle. Then we again take that set of disks which corresponds to the classics and apply the known algorithm again. And this set will be larger than in the previous step! And so we repeat until all the disks on all the poles suddenly begin to differ from the classical state.

    The system that was initially broken (by the fact that the disks are not ordered at the input) self-restores with each iteration.

    As for the resolution of repetitions, it does not matter at all. Because we are moving identical discs in succession just as one disc.

    Algorithm


    Let's call the columns A , B , C ( A at the beginning is non-empty).

    We introduce the steps of:

    A -> C () - shift one disc A to C .
    top (A) , top (C) - the size of the upper disc A or C . If the column is empty, then this size = MaxInt .
    B -> C ( K ) - shift from B to C all disks whose size is less than K (we can do this if the upper disks A andWith at least K ).
    swap () - rearrange columns B and C (or rename them - we don't care where the disks will be).
    while ( A ) is a loop while A is not empty.

    Then this algorithm works:

    //С каждым перемещённым диском с шеста 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

    Complexity


    In the worst case, the sorting tends to time complexity for the classical algorithm, which is simple and elegant, but at the same time as inefficient as possible. About the best and average difficult to guess.

    As for memory, we can say that if recursion is used, then the costs will be appropriate.

    Implementation


    I haven't written my own version of Python yet (I will do it later). However, below in the "Links" section I have added a few links where you can see the implementation in different languages. Particularly interesting option on Java. The author did not begin to use the well-known recursive method for solving the puzzle, but built the shortest path tree. Presumably, this is the most effective solution if you write sorting in the style of the “Tower of Hanoi”.

    Algorithm Characteristics

    TitleSort “Tower of Hanoi”, Tower of Hanoi sort
    Idea authorEdward Luke
    ClassSorting inserts
    Comparisonsthere is
    Time complexitythe best?
    average?
    the worstO ( 2 n )

    Links


    Of Hanoi Tower / Tower of Hanoi

    Implementation: Sea , the Java vs the C ++ vs the Python , the Python .

    Articles series:



    In the AlgoLab application, this sorting is now available. Although it belongs to the class of sorting inserts, because of the extravagance of the algorithm, it is placed in the “Other sorting” section. There is also a limit - the numbers in the sorted array can only be from 1 to 5 (due to the difficult drawing of disks). Other numbers will still be replaced by these.

    There is also a limit on the size of the array - no more than 20 elements. This is done purely in your own interests - if you take too large an array, then it may well be that you will have to sort it into old age.

    EDISON Software - web-development
    The article was written with the support of the company EDISON Software, which professionally develops smart urban lighting and maintains sites in python

    Also popular now: