Écrivez une fonction / sous-routine pour trier une liste d'entiers, style Tour de Hanoi .

Vous recevrez une pile d'entiers. Ceci est la pile principale.

Vous disposez également de deux piles d'aide supplémentaires. Ces piles d'assistance ont cependant une propriété unique: chaque élément doit être plus petit ou de la même taille que l'élément en dessous. La pile principale n'a pas une telle restriction.

Vous êtes chargé de trier la pile principale en place, en plaçant les plus grands entiers en dessous. Votre fonction / sous-programme renverra (ou équivalent) le nombre de mouvements effectués lors du tri de la pile.
_{Remarque: vous devez trier la pile principale en place , pas de tri sur une autre pile et appeler cela la réponse. Cependant, si pour une raison quelconque vous ne pouvez pas le faire, vous pouvez simuler les piles modifiables, mais rappelez-vous qu'il s'agit du type Tour de Hanoi; il n'y a que 3 chevilles et une seule cheville peut être désordonnée.}

Votre fonction / sous-routine peut inspecter n'importe quelle pile à tout moment, mais elle ne peut faire un mouvement qu'en sautant et en poussant. Un seul coup est un pop d'une pile qui est poussé à l'autre.

Testez votre fonction / sous-routine pour chaque permutation des 6 premiers nombres naturels. En d'autres termes, testez votre fonction / sous-programme {1},{2},...,{6},{1,1},{1,2},...,{1,6},{2,1},...(cela devrait être un total de ou des possibilités (merci à Howard d'avoir corrigé mes calculs)). La fonction / sous-routine qui déplace les éléments le moins de fois gagne.61+62+...+6655986

Java - solution optimale (1080544 coups)

Cette solution crée un arbre de chemin le plus court à partir de la cible et vers l'arrière, puis parcourt le chemin de l'état initial à la cible. Beaucoup de place pour l'amélioration de la vitesse, mais cela résout toujours tous les problèmes 55986 en une minute environ.

En supposant que l'algorithme est correctement implémenté, cela devrait être la meilleure solution théoriquement.

import java.util.*;

public class HanoiSort {

    public static void main(String[] args) {
        int sumNumMoves = 0;
        for (int size = 1; size <= 6; ++size) {
            Collection<List<Integer>> initMainStacks = generateInitMainStacks(Collections.<Integer>emptyList(), size);
            for (List<Integer> initMainStack : initMainStacks) {
                sumNumMoves += solve(initMainStack);
            }
        }
        System.out.println(sumNumMoves);
    }

    /*
     * Recursively create initial main stacks
     */
    private static Collection<List<Integer>> generateInitMainStacks(List<Integer> mainStack, int remainingSize) {
        Collection<List<Integer>> initMainStacks;
        if (remainingSize > 0) {
            initMainStacks = new ArrayList<>();
            for (int number = 1; number <= 6; ++number) {
                List<Integer> nextMainStack = new ArrayList<>(mainStack);
                nextMainStack.add(number);
                initMainStacks.addAll(generateInitMainStacks(nextMainStack, remainingSize - 1));
            }
        } else {
            List<Integer> initMainStack = new ArrayList<>(mainStack);
            initMainStacks = Collections.singleton(initMainStack);
        }
        return initMainStacks;
    }

    private static final List<Integer> EMPTY_STACK = Collections.emptyList();

    /*
     * Create a shortest path tree, starting from the target state (sorted main stack). Break when the initial state
     * is found, since there can be no shorter path. This is akin to building a chess endgame tablebase.
     *
     * Traverse the path from initial state to the target state to count the number of moves.
     */
    private static int solve(List<Integer> initMainStack) {
        List<List<Integer>> initState = Arrays.asList(new ArrayList<>(initMainStack), EMPTY_STACK, EMPTY_STACK);
        List<Integer> targetMainStack = new ArrayList<>(initMainStack);
        Collections.sort(targetMainStack);
        List<List<Integer>> targetState = Arrays.asList(new ArrayList<>(targetMainStack), EMPTY_STACK, EMPTY_STACK);
        Map<List<List<Integer>>,List<List<Integer>>> tablebase = new HashMap<>();
        Deque<List<List<Integer>>> workQueue = new ArrayDeque<>();
        tablebase.put(targetState, null);
        workQueue.add(targetState);
        while (!tablebase.containsKey(initState)) {
            assert !workQueue.isEmpty() : initState.toString();
            List<List<Integer>> state = workQueue.removeFirst();
            Collection<List<List<Integer>>> prevStates = calcPrevStates(state);
            for (List<List<Integer>> prevState : prevStates) {
                if (!tablebase.containsKey(prevState)) {
                    tablebase.put(prevState, state);
                    workQueue.add(prevState);
                }
            }
        }

        int numMoves = 0;
        List<List<Integer>> state = tablebase.get(initState);
        while (state != null) {
            ++numMoves;
            state = tablebase.get(state);
        }
        return numMoves;
    }

    /*
     * Given a state, calculate all possible previous states
     */
    private static Collection<List<List<Integer>>> calcPrevStates(List<List<Integer>> state) {
        Collection<List<List<Integer>>> prevStates = new ArrayList<>();
        for (int fromStackNo = 0; fromStackNo < 3; ++fromStackNo) {
            List<Integer> fromStack = state.get(fromStackNo);
            if (!fromStack.isEmpty()) {
                int number = fromStack.get(0);
                for (int toStackNo = 0; toStackNo < 3; ++toStackNo) {
                    if (toStackNo != fromStackNo) {
                        List<Integer> toStack = state.get(toStackNo);
                        if ((toStackNo == 0) || toStack.isEmpty() || (toStack.get(0) >= number)) {
                            List<List<Integer>> prevState = new ArrayList<>(state);
                            List<Integer> prevFromStack = new ArrayList<>(fromStack);
                            prevFromStack.remove(0);
                            prevState.set(fromStackNo, prevFromStack);
                            List<Integer> prevToStack = new ArrayList<>(toStack);
                            prevToStack.add(0, number);
                            prevState.set(toStackNo, prevToStack);
                            prevStates.add(prevState);
                        }
                    }
                }
            }
        }
        return prevStates;
    }

}

C - 2547172 pour 55986 entrées

Il y a beaucoup de place à l'amélioration ici. Pour ma propre raison, j'ai simplifié cela afin qu'il ne soit possible d'inspecter que l'élément supérieur de chaque pile. La levée de cette restriction auto-imposée permettrait des optimisations telles que la détermination de l'ordre final à l'avance et la tentative de minimiser le nombre de mouvements nécessaires pour y parvenir. Un exemple convaincant est que mon implémentation a le pire des cas si la pile principale est déjà triée.

Algorithme:

1. Remplissez les deux piles auxiliaires (place pour l'optimisation ici, en affectant éventuellement à quelle pile en fonction d'une sorte de pivot).
2. Fusionner pour trier les piles auxiliaires sur la pile principale.
3. Répétez 1-2 jusqu'à ce que la pile principale soit triée (mais en sens inverse).
4. Inversez la pile principale (plus de place pour l'optimisation, en mélangeant beaucoup des mêmes éléments à plusieurs reprises).

Une analyse:

• La complexité d'espace supplémentaire est O (n) (pour les deux piles auxiliaires), ce qui est bien, car c'était une exigence du problème.
• La complexité du temps est O (n ^ 2) d'après mon décompte. Les corrections sont les bienvenues.

#include <assert.h>
#include <stdio.h>

#define SIZE 6

int s0[SIZE + 1];
int s1[SIZE + 1];
int s2[SIZE + 1];

int
count(int *stack)
{
    return stack[0];
}

int
top(int *stack)
{
    return stack[stack[0]];
}

void
push(int *stack, int value)
{
    assert(count(stack) < SIZE && "stack overflow");
    assert((stack == s0 || count(stack) == 0 || value <= top(stack)) && "stack order violated");
    stack[++stack[0]] = value;
}

int
pop(int *stack)
{
    int result = stack[stack[0]];
    assert(count(stack) > 0 && "stack underflow");
    stack[stack[0]] = 0;
    stack[0]--;
    return result;
}

int permutations;

void
permute(int len, int range, void (*cb)(void))
{
    int i;
    if(len == 0)
    {
        permutations++;
        cb();
        return;
    }
    for(i = 1; i <= range; i++)
    {
        push(s0, i);
        permute(len - 1, range, cb);
        pop(s0);
    }
}

void
print(void)
{
    int i;
    for(i = 1; i <= count(s0); i++)
    {
        printf("%d ", s0[i]);
    }
    printf("\n");
}

int save[SIZE + 1];

void
copy(int *src, int *dst)
{
    int i;
    for(i = 0; i <= SIZE; i++)
    {
        dst[i] = src[i];
    }
}

int total;

void
move(int *src, int *dst)
{
    total++;
    push(dst, pop(src));
}

void
merge(void)
{
    while(1)
    {
        if(count(s1) == 0 && count(s2) == 0)
        {
            break;
        }
        else if(count(s1) == 0 || (count(s2) > 0 && top(s2) < top(s1)))
        {
            move(s2, s0);
        }
        else
        {
            move(s1, s0);
        }
    }
}

void
reverse(void)
{
    while(1)
    {
        while(count(s2) == 0 || top(s0) == top(s2))
        {
            move(s0, s2);
        }
        if(count(s0) == 0 || top(s2) < top(s0))
        {
            while(count(s2) > 0)
            {
                move(s2, s0);
            }
            break;
        }
        while(count(s0) > 0 && (count(s1) == 0 || top(s0) <= top(s1)))
        {
            move(s0, s1);
        }
        while(count(s2) > 0)
        {
            move(s2, s0);
        }
        merge();
    }
}

void
sort(void)
{
    while(1)
    {
        if(count(s0) == 0)
        {
            merge();
            reverse();
            break;
        }
        else if(count(s1) == 0 || top(s1) >= top(s0))
        {
            move(s0, s1);
        }
        else if(count(s2) == 0 || top(s2) >= top(s0))
        {
            move(s0, s2);
        }
        else
        {
            merge();
        }
    }
}

void
helper(void)
{
    copy(s0, save);
    sort();
    copy(save, s0);
}

int
main(void)
{
    permute(1, 6, helper);
    permute(2, 6, helper);
    permute(3, 6, helper);
    permute(4, 6, helper);
    permute(5, 6, helper);
    permute(6, 6, helper);
    printf("%d\n", permutations);
    printf("%d\n", total);
    return 0;
}

Python, 3983838 3912258 se déplace sur 55986 entrées

C'est très inefficace.

J'ajouterai le nombre total de mouvements après que le PO clarifie s'il s'agit de tous ces cas ou d'autres cas spécifiques.

from itertools import product       # Required for testing
import time                         # Required if you want to see it in action.

from pycallgraph import PyCallGraph
from pycallgraph.output import GraphvizOutput

def main( l ):
    ################### Data ###################
    global a , b , c , d , copy , total_moves
    total_moves = 0

    a = [ x for x in l ]  # Input stack, order doesn't matter, we'll try to empty this one
    b = []                # Usable stack, restricted by order, we'll try to get the final sorted order here
    c = []                # Usable stack, restricted by order, but we'll try to keep it as empty as possible

    d = { 'a':a , 'b':b , 'c':c }  # Passing the stacks to the nested functions by their names as a string
    copy = [ x for x in a ]        # reference copy, read-only


    ################### Functions ###################
    def is_correct( stack ):
        if d[ stack ] == sorted( copy , reverse = True ):
            return True
        else:
            return False

    def reverse_exchange( source , destination , keep = 0 ):
        #
        # keep is the number of elements to keep at the bottom of the source stack
        # The remaining top elements are moved to the destination stack
        # We first move the top elements to stack a
        # and from a to c so that the order is preserved
        # effectively splitting the source stack into two
        #

        i = 0
        while len( d[ source ] ) > keep :
            move( source , 'a' )
            i += 1
        else:
            while i > 0:
                move( 'a' , destination )
                i -= 1

    # def validate( source , destination ):
    #   # 
    #   # Validates the give move
    #   #
    #   if len( d[ source ] ) == 0:
    #       return False
    #   if destination == 'a' or len( d[ destination ] ) == 0:
    #       return True
    #   else:
    #       if d[ destination ][ len( d[ destination ] ) - 1 ] >= d[ source ][ len( d[ source ] ) - 1 ]:
    #           return True
    #       else:
    #           return False

    def move( source , destination ):
        global total_moves
        # if validate( source , destination ):
        d[ destination ].append( d[ source ].pop() )

        total_moves += 1

            # Uncomment the following to view the workings step-by-step
            # print '\n'
            # print a
            # print b
            # print c
            # print '\n'
            # time.sleep(0.1)

        return True
        # else:
        #   return False


    ################### Actual logic ###################
    while ( not is_correct( 'a' ) ):

        copy_b   = [x for x in b ]                         # Checking where the topmost element of a
        top_of_a = a[ len(a) - 1 ]                         # should be inserted
        copy_b.append( top_of_a )                          #
        sorted_copy_b = sorted( copy_b , reverse = True )  #

        reverse_exchange( 'b' , 'c' , sorted_copy_b.index( top_of_a ) )                                                  # Sandwiching the top-most element
        move( 'a' , 'b' )                                                                                                # to proper position in b
        while (len(b) > 0 and len(c) > 0 and len(a) > 0) and (sorted (b , reverse = True)[0] <= a[len(a) - 1] <= c[0]):  #  # Optimization
            move( 'a' , 'b' )                                                                                            #  #
        reverse_exchange( 'c' , 'b' )                                                                                    # b is always sorted, c is always empty

        if is_correct( 'b' ):                     # Just moving b to a
            while ( not is_correct( 'a' ) ):      # The entire program focuses on "insertion sorting"
                reverse_exchange( 'b' , 'c' , 1 ) # elements of a onto b while keeping c empty
                move( 'b' , 'a' )                 # 
                if len(c) > 0 :                       #
                    reverse_exchange( 'c' , 'b' , 1 ) # Slightly more efficient
                    move('c' , 'a' )                  #



    return total_moves


# with PyCallGraph( output= GraphvizOutput() ):


    ################### Test cases #############
i = 0
for elements in xrange( 1 , 7 ):
    for cartesian_product in product( [ 1 , 2 , 3 , 4 , 5 , 6 ] , repeat = elements ):
        input_list = [ int( y ) for y in cartesian_product ]
        i += main(input_list)
        print i
print i

Explication

Quoi, des commentaires qui ne vous conviennent pas?

_{Note à OP: Merci de ne pas avoir fait ce code-golf.}

Python: 1.688.293 1.579.182 1.524.054 1.450.842 1.093.195 mouvements

La méthode principale consiste main_to_help_bestà déplacer certains éléments sélectionnés de la pile principale vers la pile d'assistance. Il a un drapeau everythingqui définit si nous voulons qu'il déplace tout dans le spécifié destination, ou si nous voulons garder uniquement le plus grand dans destinationle reste dans l'autre assistant.

En supposant que nous passons à l' dstaide de l'aide helper, la fonction peut être décrite comme suit:

1. Trouvez les positions des plus grands éléments
2. Déplacez tout au-dessus de l'élément le plus grand en haut pour helperrécursivement
3. Déplacer le plus grand élément vers dst
4. Repousser de helperà principal
5. Répétez 2-4 jusqu'à ce que les plus gros éléments soient dst
6. une. Si everythingest défini, déplacez récursivement les éléments du principal vers dst
   b. Sinon, déplacez récursivement les éléments principaux vershelper

L'algorithme de tri principal ( sort2dans mon code) appellera ensuite main_to_help_bestavec everythingset to False, puis ramènera le plus grand élément vers main, puis déplacera tout de l'assistant vers main, le gardant trié.

Plus d'explications intégrées sous forme de commentaires dans le code.

Fondamentalement, les principes que j'ai utilisés sont:

1. Gardez un assistant pour contenir le ou les éléments maximum
2. Gardez un autre assistant pour contenir tout autre élément
3. Ne faites pas autant de mouvements inutiles que possible

Le principe 3 est implémenté en ne comptant pas le mouvement si la source est la destination précédente (c'est-à-dire que nous venons de déplacer principal vers help1, puis nous voulons passer de help1 à help2), et de plus, nous réduisons le nombre de mouvements de 1 si nous le ramène à sa position d'origine (c.-à-d. principal pour aider1 puis aide1 pour principal). De plus, si les nmouvements précédents déplacent tous le même entier, nous pouvons réellement réorganiser ces nmouvements. Nous en profitons donc également pour réduire encore le nombre de mouvements.

Ceci est valable car nous connaissons tous les éléments de la pile principale, donc cela peut être interprété comme voyant à l'avenir que nous allons reculer l'élément, nous ne devrions pas faire ce mouvement.

Sample run (les piles sont affichées de bas en haut - donc le premier élément est le bas):

Longueur 1
Mouvements: 0
Tâches: 6
Max: 0 ([1])
Moyenne: 0,000

Longueur 2
Mouvements: 60
Tâches: 36
Max: 4 ([1, 2])
Moyenne: 1.667

Longueur 3
Déplace: 1030
Tâches: 216
Max: 9 ([2, 3, 1])
Moyenne: 4.769

Longueur 4
Déplace: 11765
Tâches: 1296
Max: 19 ([3, 4, 2, 1])
Moyenne: 9.078

Longueur 5
Déplace: 112325
Tâches: 7776
Max: 33 ([4, 5, 3, 2, 1])
Moyenne: 14.445

Longueur 6
Déplace: 968015
Tâches: 46656
Max: 51 ([5, 6, 4, 3, 2, 1])
Moyenne: 20.748

--------------
Global
Déménagements: 1093195
Tâches: 55986
Moyenne: 19.526

Nous pouvons voir que le pire des cas est lorsque le plus grand élément est placé sur le deuxième fond, tandis que les autres sont triés. Dans le pire des cas, nous pouvons voir que l'algorithme est O (n ^ 2).

Le nombre de coups est évidemment minimum pour n=1et n=2comme nous pouvons le voir sur le résultat, et je crois que c'est aussi minimum pour des valeurs plus grandes de n, bien que je ne puisse pas le prouver.

Plus d'explications sont dans le code.

from itertools import product

DEBUG = False

def sort_better(main, help1, help2):
    # Offset denotes the bottom-most position which is incorrect
    offset = len(main)
    ref = list(reversed(sorted(main)))
    for idx, ref_el, real_el in zip(range(len(main)), ref, main):
        if ref_el != real_el:
            offset = idx
            break

    num_moves = 0
    # Move the largest to help1, the rest to help2
    num_moves += main_to_help_best(main, help1, help2, offset, False)
    # Move the largest back to main
    num_moves += push_to_main(help1, main)
    # Move everything (sorted in help2) back to main, keep it sorted
    num_moves += move_to_main(help2, main, help1)
    return num_moves

def main_to_help_best(main, dst, helper, offset, everything=True):
    """
    Moves everything to dst if everything is true,
    otherwise move only the largest to dst, and the rest to helper
    """
    if offset >= len(main):
        return 0
    max_el = -10**10
    max_idx = -1
    # Find the location of the top-most largest element
    for idx, el in enumerate(main[offset:]):
        if el >= max_el:
            max_idx = idx+offset
            max_el = el
    num_moves = 0
    # Loop from that position downwards
    for max_idx in range(max_idx, offset-1, -1):
        # Processing only at positions with largest element
        if main[max_idx] < max_el:
            continue
        # The number of elements above this largest element
        top_count = len(main)-max_idx-1
        # Move everything above this largest element to helper
        num_moves += main_to_help_best(main, helper, dst, max_idx+1)
        # Move the largest to dst
        num_moves += move(main, dst)
        # Move back the top elements
        num_moves += push_to_main(helper, main, top_count)
    # Here, the largest elements are in dst, the rest are in main, not sorted
    if everything:
        # Move everything to dst on top of the largest
        num_moves += main_to_help_best(main, dst, helper, offset)
    else:
        # Move everything to helper, not with the largest
        num_moves += main_to_help_best(main, helper, dst, offset)
    return num_moves

def verify(lst, moves):
    if len(moves) == 1:
        return True
    moves[1][0][:] = lst
    for src, dst, el in moves[1:]:
        move(src, dst)
    return True

def equal(*args):
    return len(set(str(arg.__init__) for arg in args))==1

def move(src, dst):
    dst.append(src.pop())
    el = dst[-1]
    if not equal(dst, sort.lst) and list(reversed(sorted(dst))) != dst:
        raise Exception('HELPER NOT SORTED: %s, %s' % (src, dst))

    cur_len = len(move.history)
    check_idx = -1
    matched = False
    prev_src, prev_dst, prev_el = move.history[check_idx]
    # As long as the element is the same as previous elements,
    # we can reorder the moves
    while el == prev_el:
        if equal(src, prev_dst) and equal(dst, prev_src):
            del(move.history[check_idx])
            matched = True
            break
        elif equal(src, prev_dst):
            move.history[check_idx][1] = dst
            matched = True
            break
        elif equal(dst, prev_src):
            move.history[check_idx][0] = src
            matched = True
            break
        check_idx -= 1
        prev_src, prev_dst, prev_el = move.history[check_idx]
    if not matched:
        move.history.append([src, dst, el])
    return len(move.history)-cur_len

def push_to_main(src, main, amount=-1):
    num_moves = 0
    if amount == -1:
        amount = len(src)
    if amount == 0:
        return 0
    for i in range(amount):
        num_moves += move(src, main)
    return num_moves

def push_to_help(main, dst, amount=-1):
    num_moves = 0
    if amount == -1:
        amount = len(main)
    if amount == 0:
        return 0
    for i in range(amount):
        num_moves += move(main, dst)
    return num_moves

def help_to_help(src, dst, main, amount=-1):
    num_moves = 0
    if amount == -1:
        amount = len(src)
    if amount == 0:
        return 0
    # Count the number of largest elements
    src_len = len(src)
    base_el = src[src_len-amount]
    base_idx = src_len-amount+1
    while base_idx < src_len and base_el == src[base_idx]:
        base_idx += 1

    # Move elements which are not the largest to main
    num_moves += push_to_main(src, main, src_len-base_idx)
    # Move the largest to destination
    num_moves += push_to_help(src, dst, base_idx+amount-src_len)
    # Move back from main
    num_moves += push_to_help(main, dst, src_len-base_idx)
    return num_moves

def move_to_main(src, main, helper, amount=-1):
    num_moves = 0
    if amount == -1:
        amount = len(src)
    if amount == 0:
        return 0
    # Count the number of largest elements
    src_len = len(src)
    base_el = src[src_len-amount]
    base_idx = src_len-amount+1
    while base_idx < src_len and base_el == src[base_idx]:
        base_idx += 1

    # Move elements which are not the largest to helper
    num_moves += help_to_help(src, helper, main, src_len-base_idx)
    # Move the largest to main
    num_moves += push_to_main(src, main, base_idx+amount-src_len)
    # Repeat for the rest of the elements now in the other helper
    num_moves += move_to_main(helper, main, src, src_len-base_idx)
    return num_moves

def main():
    num_tasks = 0
    num_moves = 0
    for n in range(1, 7):
        start_moves = num_moves
        start_tasks = num_tasks
        max_move = -1
        max_main = []
        for lst in map(list,product(*[[1,2,3,4,5,6]]*n)):
            num_tasks += 1
            if DEBUG: print lst, [], []
            sort.lst = lst
            cur_lst = lst[:]
            move.history = [(None, None, None)]
            help1 = []
            help2 = []
            moves = sort_better(lst, help1, help2)
            if moves > max_move:
                max_move = moves
                max_main = cur_lst
            num_moves += moves

            if DEBUG: print '%s, %s, %s (moves: %d)' % (cur_lst, [], [], moves)
            if list(reversed(sorted(lst))) != lst:
                print 'NOT SORTED: %s' % lst
                return
            if DEBUG: print

            # Verify that the modified list of moves is still valid
            verify(cur_lst, move.history)
        end_moves = num_moves - start_moves
        end_tasks = num_tasks - start_tasks
        print 'Length %d\nMoves: %d\nTasks: %d\nMax: %d (%s)\nAverage: %.3f\n' % (n, end_moves, end_tasks, max_move, max_main, 1.0*end_moves/end_tasks)
    print '--------------'
    print 'Overall\nMoves: %d\nTasks: %d\nAverage: %.3f' % (num_moves, num_tasks, 1.0*num_moves/num_tasks)

# Old sort method, which assumes we can only see the top of the stack
def sort(main, max_stack, a_stack):
    height = len(main)
    largest = -1
    num_moves = 0
    a_stack_second_el = 10**10
    for i in range(height):
        if len(main)==0:
            break
        el = main[-1]
        if el > largest: # We found a new maximum element
            if i < height-1: # Process only if it is not at the bottom of main stack
                largest = el
                if len(a_stack)>0 and a_stack[-1] < max_stack[-1] < a_stack_second_el:
                    a_stack_second_el = max_stack[-1]
                # Move aux stack to max stack then reverse the role
                num_moves += help_to_help(a_stack, max_stack, main)
                max_stack, a_stack = a_stack, max_stack
                if DEBUG: print 'Moved max_stack to a_stack: %s, %s, %s (moves: %d)' % (main, max_stack, a_stack, num_moves)
                num_moves += move(main, max_stack)
                if DEBUG: print 'Moved el to max_stack: %s, %s, %s (moves: %d)' % (main, max_stack, a_stack, num_moves)
        elif el == largest:
            # The maximum element is the same as in max stack, append
            if i < height-1: # Only if the maximum element is not at the bottom
                num_moves += move(main, max_stack)
        elif len(a_stack)==0 or el <= a_stack[-1]:
            # Current element is the same as in aux stack, append
            if len(a_stack)>0 and el < a_stack[-1]:
                a_stack_second_el = a_stack[-1]
            num_moves += move(main, a_stack)
        elif a_stack[-1] < el <= a_stack_second_el:
            # Current element is larger, but smaller than the next largest element
            # Step 1
            # Move the smallest element(s) in aux stack into max stack
            amount = 0
            while len(a_stack)>0 and a_stack[-1] != a_stack_second_el:
                num_moves += move(a_stack, max_stack)
                amount += 1

            # Step 2
            # Move all elements in main stack that is between the smallest
            # element in aux stack and current element
            while len(main)>0 and max_stack[-1] <= main[-1] <= el:
                if max_stack[-1] < main[-1] < a_stack_second_el:
                    a_stack_second_el = main[-1]
                num_moves += move(main, a_stack)
                el = a_stack[-1]

            # Step 3
            # Put the smallest element(s) back
            for i in range(amount):
                num_moves += move(max_stack, a_stack)
        else: # Find a location in aux stack to put current element
            # Step 1
            # Move all elements into max stack as long as it will still
            # fulfill the Hanoi condition on max stack, AND
            # it should be greater than the smallest element in aux stack
            # So that we won't duplicate work, because in Step 2 we want
            # the main stack to contain the minimum element
            while len(main)>0 and a_stack[-1] < main[-1] <= max_stack[-1]:
                num_moves += move(main, max_stack)

            # Step 2
            # Pick the minimum between max stack and aux stack, move to main
            # This will essentially sort (in reverse) the elements into main
            # Don't move to main the element(s) found before Step 1, because
            # we want to move them to aux stack
            while True:
                if len(a_stack)>0 and a_stack[-1] < max_stack[-1]:
                    num_moves += move(a_stack, main)
                elif max_stack[-1] < el:
                    num_moves += move(max_stack, main)
                else:
                    break

            # Step 3
            # Move all elements in main into aux stack, as long as it
            # satisfies the Hanoi condition on aux stack
            while max_stack[-1] == el:
                num_moves += move(max_stack, a_stack)
            while len(main)>0 and main[-1] <= a_stack[-1]:
                if main[-1] < a_stack[-1] < a_stack_second_el:
                    a_stack_second_el = a_stack[-1]
                num_moves += move(main, a_stack)
        if DEBUG: print main, max_stack, a_stack
    # Now max stack contains largest element(s), aux stack the rest
    num_moves += push_to_main(max_stack, main)
    num_moves += move_to_main(a_stack, main, max_stack)
    return num_moves

if __name__ == '__main__':
    main()

Java - 2129090 2083142 se déplace sur des baies 55986

Le lien idéone .

Le cadre pour garantir que l'algorithme est correct:

private final Deque<Integer> main = new ArrayDeque<Integer>();
private final Deque<Integer> help1 = new ArrayDeque<Integer>();
private final Deque<Integer> help2 = new ArrayDeque<Integer>();

private int taskCount = 0;
private int opCount = 0;

private void sort(List<Integer> input) {
    taskCount++;
    main.addAll(input);
    sortMain();
    verify();
    main.clear();
}

private void verify() {
    if (!help1.isEmpty()) {
        throw new IllegalStateException("non-empty help1\n" + state());
    }
    if (!help2.isEmpty()) {
        throw new IllegalStateException("non-empty help2\n" + state());
    }
    int last = 0;
    for (int i: main) {
        if (last > i) {
            throw new IllegalStateException("unsorted main: " + main);
        }
        last = i;
    }
}

private void done() {
    System.out.println();
    System.out.print(opCount + "/" + taskCount);
}

private void move(Deque<Integer> from, Deque<Integer> to) {
    if (from == to) throw new IllegalArgumentException("moving from/to " + from);
    Integer i = from.pop();
    if (to != main && !to.isEmpty() && i > to.peek()) {
        throw new IllegalStateException(
                from + " " + i + " -> " + to);
    }
    to.push(i);
    opCount++;
}

private String name(Deque<Integer> stack) {
    return stack == help1 ? "help1" :
           stack == help2 ? "help2" :
           "main";
}

private String state() {
    return "main:  " + main + 
            "\nhelp1: " + help1 +
            "\nhelp2: " + help2;
}

L'algorithme réel:

private void ensureMain(Deque<Integer> stack) {
    if (stack != main) {
        throw new IllegalArgumentException("Expected main, got " + name(stack) + "\n" + state());
    }
}

private void ensureHelp(Deque<Integer> stack) {
    if (stack == main) {
        throw new IllegalArgumentException("Expected help, got main\n" + state());
    }
}

private void ensureHelpers(Deque<Integer> stack1, Deque<Integer> stack2) {
    ensureHelp(stack1);
    ensureHelp(stack2);
}

private void sortMain() {
    int height = main.size();
    int topIndex = height;
    while (topIndex == height && height > 1) {
        topIndex = lastIndexOfLargest(height, main);
        height--;
    }
    if (topIndex == height) { 
        // is already sorted
        return;
    }
    // split stack at largest element
    int part1Count = topIndex;
    int part2Count = height - topIndex;
    // move largest and first part to help 1
    moveFromMain(part1Count+1, help1, help2);
    // merge both parts to help 2, leaving largest on 1
    mergeToHelp(part2Count, main, part1Count, help1, help2);
    // move largest to main
    move(help1, main);
    // move remaining to main
    moveToMain(height, help2, help1);
}

/** Moves elements from main to helper, sorting them */
private void moveFromMain(int amount, Deque<Integer> target, Deque<Integer> help) {
    if (amount < 1) return;
    ensureHelpers(target, help);
    int topIndex = lastIndexOfLargest(amount, main);
    int part1Count = topIndex;
    int part2Count = amount - topIndex - 1;
    // move first part to help
    moveFromMain(part1Count, help, target);
    // move largest to target
    move(main, target);
    // merge both parts to target
    mergeToHelp(part2Count, main, part1Count, help, target);
}

/** Moves elements from helper to main, keeping them sorted */
private void moveToMain(int amount, Deque<Integer> source, Deque<Integer> help) {
    if (amount < 1) return;
    ensureHelpers(source, help);
    moveHelper(amount-1, source, help);
    move(source, main);
    moveToMain(amount-1, help, source);
}

/** Moves elements between helpers */
private void moveHelper(int amount, Deque<Integer> source, Deque<Integer> target) {
    pushToMain(amount, source);
    popFromMain(amount, target);
}

/** Merges top of main and helper to other helper */
private void mergeToHelp(int mainAmount, Deque<Integer> main, int helpAmount, Deque<Integer> help, Deque<Integer> target) {
    ensureMain(main);
    ensureHelpers(help, target);
    if (mainAmount < 0) mainAmount = 0;
    if (helpAmount < 0) helpAmount = 0;
    while (mainAmount > 0 || helpAmount > 0) {
        // while there is something to merge
        int largestMain = valueOfLargest(mainAmount, main);
        int largestHelp = valueOfLargest(helpAmount, help);
        if (largestMain > largestHelp) {
            // largest is in main
            int index = firstIndexOfLargest(mainAmount, main);
            if (index > 0) {
                // move excess to help:
                int mainTop = index;
                int helpTop = elementsSmallerThan(help, largestMain);
                if (helpTop > 0) {
                    // 1. move top of help to target
                    moveHelper(helpTop, help, target);
                    // 2. merge old top with excess from main
                    mergeToHelp(mainTop, main, helpTop, target, help);
                } else {
                    moveFromMain(mainTop, help, target);
                }
                mainAmount -= mainTop;
                helpAmount += mainTop;
            }
            move(main, target);
            mainAmount--;
        } else {
            // largest is at bottom of help
            int helpTop = helpAmount - 1; // largest is at bottom
            // move top to main
            pushToMain(helpTop, help);
            mainAmount += helpTop;
            // move largest to target
            move(help, target);
            helpAmount = 0;
        }
    }
}

private void pushToMain(int amount, Deque<Integer> from) {
    for (; amount > 0; amount--) move(from, main);
}

private void popFromMain(int amount, Deque<Integer> to) {
    for (; amount > 0; amount--) move(main, to);
}

private int firstIndexOfLargest(int height, Deque<Integer> stack) {
    if (height == 0) throw new IllegalArgumentException("height == 0");
    int topValue = 0;
    int topIndex = 0;
    int i = 0;
    for (Integer e: stack) {
        if (e > topValue) {
            topValue = e;
            topIndex = i;
        }
        if (++i == height) break;
    }
    return topIndex;
}

private int lastIndexOfLargest(int height, Deque<Integer> stack) {
    if (height == 0) throw new IllegalArgumentException("height == 0");
    int topValue = 0;
    int topIndex = 0;
    int i = 0;
    for (Integer e: stack) {
        if (e >= topValue) {
            topValue = e;
            topIndex = i;
        }
        if (++i == height) break;
    }
    return topIndex;
}

private int valueOfLargest(int height, Deque<Integer> stack) {
    int v = Integer.MIN_VALUE;
    for (Integer e: stack) {
        if (height-- == 0) break;
        if (e > v) v = e;
    }
    return v;
}

private int elementsSmallerThan(Deque<Integer> stack, int value) {
    int i = 0;
    for (Integer e: stack) {
        if (e >= value) return i;
        i++;
    }
    return i;
}

Le testcase:

public static void main(String[] args) throws Exception {
    HanoiSort hanoi = new HanoiSort();
    int N = 6;
    for (int len = 1; len <= N; len++) {
        Integer[] input = new Integer[len];
        List<Integer> inputList = Arrays.asList(input);
        int max = N;
        for (int i = 1; i < len; i++) max *= N;
        for (int run = 0; run < max; run++) {
            int n = run;
            for (int i = 0; i < len; n /= N, i++) {
                input[i] = (n % N)+1;
            }
            try {
                hanoi.sort(inputList);
            } catch (Exception e) {
                System.out.println(inputList);
                e.printStackTrace(System.out);
                return;
            }
        }
    }
    hanoi.done();
}

C / C ++ N'a pas mesuré les mouvements (chevilles: p1, p2, p3) Je ne sais pas comment ajouter du code C ++ qui utilise STL (problème de formatage). Perte de parties de code en raison des formats de balises html dans le code.

1. Obtenir n: nombre d'éléments triés en haut dans p1
2. Faites un mouvement de hanoi (n) vers p3 en utilisant p2 (conserve la propriété triée)
3. Déplacez les m elems suivants (au moins 1) dans l'ordre inverse de p1 à p2.

4. Fusionner les données de déplacement (n + m) de p2 et p3 à p1.

        4.1 merge sort p2 & P3 (reverse) to p1
        4.2 move (n+m) to p3
        4.3 hanoi p3 to p1 using p2
   

5. Appelez récursivement hanoi qui triera maintenant au moins n + m + 1 éléments.
6. Arrêtez lorsque n = taille de p1.

#comprendre 
#comprendre 
using namespace std;
/ ************************************************* ***************************** 
   Montrez le vecteur
************************************************** ***************************** /    

void show (vecteur p, msg chaîne)
{
   vector :: itérateur it;
   printf ("% s \ n", msg.c_str ());
   for (it = p.begin (); it & fr, vector & inter, vector & to, int n) {
   int d1;
   si (n & p1, vecteur & p2, vecteur & p3) {
   int d3, d2, d1;
   nombre entier, n;
   bool d2_added;

   d2 = p2.back (); p2.pop_back ();
   // les données vont descendre dans p1
   d2_added = false;
   while (p3.size ()> 0) {
      d3 = p3.back (); p3.pop_back ();
      if (d2_added == false && d2 0) {
      d1 = p1.back (); p1.pop_back ();
      p3.push_back (d1);
      --compter;
   }
   // Recule avec hanoi de p3 à p1
   // utilise p2 comme inter
   hanoi (p3, p2, p1, n);
}
/ ************************************************* ******************************
   Obtient le nombre de premiers éléments triés
************************************************** ***************************** /    
int get_top_sorted_count (vector & p1) {
   vector :: itérateur it;
   int prev = 0;
   int n = 1;

   for (it = --p1.end (); it> = p1.begin (); --it) {
     if (it == --p1.end ()) {
    prev = * it;
        continuer;
     }
     if (* it & p1, vector & p2, vector & p3) {
    int n, d1;
    n = get_top_sorted_count (p1);
    if (n == p1.size ()) {
       revenir;
    }
    hanoi (p1, p2, p3, n);
    p2.push_back (p1.back ());
    p1.pop_back ();
    merge_move (p1, p2, p3);
    hanoi_sort (p1, p2, p3);
}
/ ************************************************* ******************************    
    Torts baed sur hanoi
************************************************** ***************************** /    
int main (void)
{
  vecteur p1, p2, p3;
  p1.push_back (5);
  p1.push_back (4);
  p1.push_back (7);
  p1.push_back (3);
  p1.push_back (8);
  p1.push_back (2);
  show (p1, "... Bef Sort ...");
  hanoi_sort (p1, p2, p3);
  show (p1, "... Tri arrière ...");
}