1. Starting at slot 1, find the first tape that is not in the right slot.
2. Move that tape to slot 0.
3. Since that tape was not in the right slot, there is another tape which belongs in that slot. Find that tape and move it into the right slot.
4. Repeat the previous step until the tape in slot 0 is moved into the right slot.

This algorithm is not sufficent. Take for example, this arrangement of tapes: d c b a 0. Following your algorithm the tapes would be moved like so:
1. 0 c b a d
2. a c b 0 d
3. a c b d 0

... then it would stop since the tape that was in slot 0 was just moved to the right slot.

You could work around this, by after moving the tape in slot 0 to the right slot, starting from step 1 again (until all tapes are in order).

I apoligize in advance if any of the following contains an error, which it very well may.

If the removal of tape T causes the movement of a certain set of tapes "M" before tape T is replaced in the correct location, than the movement of any item in "M" must cause the movement of tape T and every other item in "M" before the replacement of tape T. (Attempt at proof if you don't find this obvious: Every item in set M either determines the movement of another tape in set M or tape T. Since each tape determines the movement of one and only one tape, let us order the set M starting with the tape that tape T determines the removal of, and continuing with the tape that determines the removal of, etc. The last element in set M must determine the removal of tape T, since that would stop the building of the set after starting from tape T (since tape T would then be moved back from the "free" slot to which it was removed). Thus, if we remove a tape in set M, it determines the removal of every tape after it in set M, and then determines the removal of tape T, which then determines the removal of every item before it in set M, which then determines the replacement of that tape in set M.)

(update: In case it's not obvious to you, note that this means that it doesn't matter which element we start at. The entire set of tapes can be divided into groups that we can remove one item to the "free" slot and organize by moving items around in the sequence dictated. To sort the whole sequence using our method of always moving things to where they belong, we must move any one item from each of these groups to the free slot and proceed. But, since these groups are independent it doesn't matter what we group we start with, and since we will not tapes already in the right place (if we didn't that would obviously add extra, unnecessary moves), we will pick each group exactly once...)

Also, moving any tape to a slot that is not where it should end up, besides the movement to the free slot to allow the initial movement of a bunch of tapes will not result in less moves being needed. If we move a tape T into a slot where it does not belong, either:

1. the set of tapes, M, whose movement is determined by T will all be allowed to move (without incuring an extra move to move something in/out of the free slot), but after any of this movement then require us to move tape T to the slot where it belongs which would be equivilent to moving tape T to the free slot, thus not saving any moves).
2. or, tape T has been moved to a place in the correct location for one of the tapes in set M, and thus, tape T less tapes then are in set M will allowed to be moved (without incuring an extra move, as before).

All other algorithms to solve this problem would either choose to not move tapes to the position where they will eventually end up or will choose a different tape to move initially. By the stuff above, those other ways eithe result in the same number of moves, or more moves, so this is the shortest way to solve the problem.

For example, with Perl you could solve this specific problem with the following two statements:

($slots[1], $slots[2]) = ($slots[2], $slots[1]);
($slots[2], $slots[3]) = ($slots[3], $slots[2]);
[download]

($slots[1], $slots[2], $slots[3]) = ($slots[2], $slots[3], $slots[1]);
[download]

--Jim

Update: Well, that's the algorithm part I alluded to, your list of moves for the 2-element swap would look like this:

• swap(1, 2)
• swap(2, 3)

If we'd known that you had to use a one-armed robot to begin with, the replies might have been more useful. ;)

Do you mean something like

@slots = @slots[2,1,4,3]
[download]

It looks nice but I really need a list of move actions for the robot.

Interestingly enough, there seems to be scant details available on the net. Google doesn't turn up much. I read about this technique in a long-lost issue of Computer Language.

The only link halfway useful that I have found is www.cs.brandeis.edu/~hugues/sorting_networks.html ... I think you're going to have to dig out a copy of Knuth volume III - Searching and Sorting. <update> Hmm, I just did. The Knuth, as usual, is heavy on mathematics and short on algorithms. I still can't find any code to help you. It's in section 5.3.1 (Minimum-comparison sorting) for what it's worth.</update>

The algorithm essentially accepts a single number (the number of elements to sort), and then spits out a series of pairs, which are the indices of the elements to compare. And it turns out that as some of the comparison (a,b) and (c,d) don't affect each other, you can run them in parallel, thereby reducing the overall time taken.

It is apparently very hard to generate a minimal number of comparisons. These days people are attacking the problem through Genetic Algorithm (GA) techniques.

Some more links. Using sorting networks reveals more hits.

• cs.engr.uky.edu/~lewis/essays/algorithms/sortnets/sort-net.html
• www.theory.csc.uvic.ca/~mmania/networks/intro.htm

I don't think sorting networks will work here.

If I remember correctly, (and I'm not certain I ever really understood them) they're built on the principle of swaps, and while you can definitely think of a move as a swap where one of the items is empty, a sorting network would suggest solutions that aren't possible.

For example a if the input was (0,2,1) the solution you would get is swap(1,2) -- but that's not possible. in this case only swaps in which one parameter is currently "0" are valid.

It really sounds like a Game Playing problem ... here's a recursive solution that tries all the "smart" moves and figures out which one leads to the correct order in the minimal number of moves.

If a "close to optimal" solution is good enough, then pick_move could be modified to use Alpha Beta Pruning to figure out which of the "smart" moves looks like it's the smartest. I would guess a good scoring method would award one point to for each tape in the correct slot, and half a point if there's a tape in slot 0. (in which case something else is empty, and can be filled directly)

#!/usr/bin/perl -wl

use strict;

sub smart_moves {
    my @slots = @{ shift(@_) };
    my @from;
    my $to;
    for (my $i = 0; $i < scalar(@slots); $i++) {
    if (0 != $i and 0 == $slots[$slots[$i]]) {
        # only one smart move if the home for the tape 
            # in slot i is empty
        return ( [ $i, $slots[$i] ] );
    }
    if (0 == $slots[$i]) {
        $to = $i;
        next;
    }
    # don't move anything that's allready 'home'
    push @from, $i unless $i eq $slots[$i];
    }
    return map { [$_ , $to ] } @from;
}

sub make_move {
    # returns the new @slots after the move
    my @slots = @{shift(@_)};
    my @move = @{shift(@_)};
    $slots[$move[1]] = $slots[$move[0]];
    $slots[$move[0]] = 0;
    return @slots;
}

sub pick_move {
    my @slots = @{shift(@_)}; # current configuration
    my @history = @{shift(@_)}; # moves made so far
    my @moves = smart_moves(\@slots);
    
    return @history if 0 == scalar @moves;
    
    my @best;
    foreach (@moves) {
    my @s = make_move \@slots, $_;
    my @h = @history; # copy it
    push @h, $_;
    my @result = pick_move(\@s, \@h);
    if (0 == scalar(@best) || scalar(@result) <= scalar(@best))  {
        @best = @result;
    }
    }
    return @best;
}

my @slots = @ARGV;
my @done = pick_move(\@slots, []);

foreach (@done) {
    print join(",", @slots) . "\t$_->[0] => $_->[1]";
    @slots = make_move(\@slots,$_);
}
print join(",", @slots)

__END__
laptop:~> monk.pl 0 2 1
0,2,1   2 => 0
1,2,0   1 => 2
1,0,2   0 => 1
0,1,2
laptop:~> monk.pl 0 1 2
0,1,2
laptop:~> monk.pl 0 2 1 4 5 3
0,2,1,4,5,3     5 => 0
3,2,1,4,5,0     4 => 5
3,2,1,4,0,5     3 => 4
3,2,1,0,4,5     2 => 3
3,2,0,1,4,5     1 => 2
3,0,2,1,4,5     3 => 1
3,1,2,0,4,5     0 => 3
0,1,2,3,4,5
laptop:~> monk.pl 0 2 1 7 8 9 5 4 3 6
0,2,1,7,8,9,5,4,3,6     9 => 0
6,2,1,7,8,9,5,4,3,0     5 => 9
6,2,1,7,8,0,5,4,3,9     6 => 5
6,2,1,7,8,5,0,4,3,9     8 => 6
6,2,1,7,8,5,3,4,0,9     4 => 8
6,2,1,7,0,5,3,4,8,9     7 => 4
6,2,1,7,4,5,3,0,8,9     3 => 7
6,2,1,0,4,5,3,7,8,9     6 => 3
6,2,1,3,4,5,0,7,8,9     2 => 6
6,2,0,3,4,5,1,7,8,9     1 => 2
6,0,2,3,4,5,1,7,8,9     6 => 1
6,1,2,3,4,5,0,7,8,9     0 => 6
0,1,2,3,4,5,6,7,8,9
[download]

Many thanks to you and all the others for the many and sound responses!

After all I understand that I should have named it "minimal move algorithm"

I need some time to digest all of this. For the moment I'll leave the monastery for the German Perl workshop which starts tomorrow evening:)
Cheers, Axel.

--
perl -pe "s/\b;([st])/'\1/mg"

This sounds alot like Bubble Sort to me.

The distinction being that Bubble Sort is usually defined in terms of a  swap(a, b) method which is considered atomic. Since  swap) can be (and frequently is) defined in terms of two moves that use a temp variable, Bubble Sort can solve your problem given your constraints -- uut it will never come close to a solution with a minimal number of moves. It will only ever call  move(a, 0) and  move(0, a).

I can't think of any other constant space sorting algorithms (that operate on arrays). But one extremely important question that needs to be answered before you can even try to for finding an optimal algorithm is: how do you define optimal? is move(n,m) the only operation with a "cost" ? what about doing comparispons or slots? Would a solution that analyzed all of the slots in detail first,then built up a list of moves be considered optimal?

(I ask, because you're post only refers to the ideal situation being one in which "the number of moves is minimal.")

In this case, it appears that yes, move(n,m) is the only operation with cost. (I'm not sure if it's cost is constant over all n,m. I think we're supposted to assume that it is.)

In purticular, this is going to be applied to a tape-library servicing robot, which only has one operation: switch the tapes in positions N and M. (move(n,m))

You're right about bubble-sort being a possiblity... but I don't think it's a good one. Remember that it isn't finding the sequence of moves that has to be done in constant space, it's the acautual movement of physical tapes.

TACCTGTTTGAGTGTAACAATCATTCGCTCGGTGTATCCATCTTTG ACACAATGAATCTTTGACTCGAACAATCGTTCGGTCGCTCCGACGC

That's why I'm not clear on the goal, is it:

Find an algorithm, whose performance is inconsequential, that can determine the minimal number of moves to sort the tapes.

Or is it something like:

Find an optimal algorithm for sorting the tapes such that the only atomic operations move(m,n) and examine(n) -- which tells you what tape is in slot n.

If any amount of preprocessing and analysis is allowed, then any number of hueristics could be useful for find a path from the starting order to sorted order.

If nothing else, you can do a breadth first search of all the possible permutations of moves untill you achieve the desired ordering.

> is move(n,m) the only operation with a "cost" ?


Practically yes. Finding the right order is easily achieved with Perl in memory. The cost mainly results from time a robot arm needs to pick and move a tape. (about 30 seconds)

I neglect the time difference for tape moves betwenn different slots. (a maximum of 60 tapes)

> Would a solution that analyzed all of the slots in detail first,then built up a list of moves be considered optimal?
Yes - that's how I want to solve it.

use strict;
my @slots;
my $max = 10;
my $empty = 0;
my $sum_moves = 0;
my %rlookup;
my $trials = 3;
my $min_moves = $max*$max;
my $max_moves = 0;

# initialize @slots
$slots[$_] = $_ for (0..$max);
srand time;

for my $ct (1..$trials) {
   # randomize @slots
   for (1..$max) {
      my $rand = int(rand $max) + 1;
      ($slots[$_], $slots[$rand]) = ($slots[$rand], $slots[$_]);
   }

   %rlookup = ();
   build_hash();
   my $moves = 0;
   my $unordered = inorder();
   while ($unordered || $empty) {
      print join " ", @slots, " \$empty: $empty  ";
      if ($slots[0] != 0) {
         print "move($rlookup{$empty}, $empty);\n";
         $slots[$empty] = $rlookup{$slots[$empty]};
         $slots[$rlookup{$empty}] = 0;
         $empty = $rlookup{$empty};
      } else {
         print "move($unordered, $empty);\n";
         ($slots[$empty], $slots[$unordered]) = ($slots[$unordered], $
+slots[$empty]);
         $empty = $unordered;
      }
      $moves++;
      build_hash();
      $unordered = inorder();
   }
   print join " ", @slots, " \$empty: $empty\n";
   print "Trial: ", pack("A5", $ct), "  Moves: $moves\n\n";
   $min_moves = $moves if $moves < $min_moves;
   $max_moves = $moves if $moves > $max_moves;
   $sum_moves += $moves;
}

print "Number of slots: $max\n";
print "Trials: $trials\n";
print "Average Moves: ", $sum_moves / $trials, "\n";
print "Minimum Moves: ", $min_moves, "\n";
print "Maximum Moves: ", $max_moves, "\n";

sub inorder {
   my $i;
   for (1..$max) {
      $i = $_;
      last if $_ != $slots[$_];
   }
   return $i % $max;
}

sub build_hash {
  $rlookup{$slots[$_]} = $_ for (0..$max);
}
[download]

0 2 3 7 6 4 10 5 8 9 1  $empty: 0  move(1, 0);
2 0 3 7 6 4 10 5 8 9 1  $empty: 1  move(10, 1);
2 1 3 7 6 4 10 5 8 9 0  $empty: 10  move(6, 10);
2 1 3 7 6 4 0 5 8 9 10  $empty: 6  move(4, 6);
2 1 3 7 0 4 6 5 8 9 10  $empty: 4  move(5, 4);
2 1 3 7 4 0 6 5 8 9 10  $empty: 5  move(7, 5);
2 1 3 7 4 5 6 0 8 9 10  $empty: 7  move(3, 7);
2 1 3 0 4 5 6 7 8 9 10  $empty: 3  move(2, 3);
2 1 0 3 4 5 6 7 8 9 10  $empty: 2  move(0, 2);
0 1 2 3 4 5 6 7 8 9 10  $empty: 0
Trial: 1      Moves: 9

0 5 8 10 6 2 9 3 7 1 4  $empty: 0  move(1, 0);
5 0 8 10 6 2 9 3 7 1 4  $empty: 1  move(9, 1);
5 1 8 10 6 2 9 3 7 0 4  $empty: 9  move(6, 9);
5 1 8 10 6 2 0 3 7 9 4  $empty: 6  move(4, 6);
5 1 8 10 0 2 6 3 7 9 4  $empty: 4  move(10, 4);
5 1 8 10 4 2 6 3 7 9 0  $empty: 10  move(3, 10);
5 1 8 0 4 2 6 3 7 9 10  $empty: 3  move(7, 3);
5 1 8 3 4 2 6 0 7 9 10  $empty: 7  move(8, 7);
5 1 8 3 4 2 6 7 0 9 10  $empty: 8  move(2, 8);
5 1 0 3 4 2 6 7 8 9 10  $empty: 2  move(5, 2);
5 1 2 3 4 0 6 7 8 9 10  $empty: 5  move(0, 5);
0 1 2 3 4 5 6 7 8 9 10  $empty: 0
Trial: 2      Moves: 11

0 6 7 4 5 2 3 1 8 9 10  $empty: 0  move(1, 0);
6 0 7 4 5 2 3 1 8 9 10  $empty: 1  move(7, 1);
6 1 7 4 5 2 3 0 8 9 10  $empty: 7  move(2, 7);
6 1 0 4 5 2 3 7 8 9 10  $empty: 2  move(5, 2);
6 1 2 4 5 0 3 7 8 9 10  $empty: 5  move(4, 5);
6 1 2 4 0 5 3 7 8 9 10  $empty: 4  move(3, 4);
6 1 2 0 4 5 3 7 8 9 10  $empty: 3  move(6, 3);
6 1 2 3 4 5 0 7 8 9 10  $empty: 6  move(0, 6);
0 1 2 3 4 5 6 7 8 9 10  $empty: 0
Trial: 3      Moves: 8

Number of slots: 10
Trials: 3
Average Moves: 9.33333333333333
Minimum Moves: 8
Maximum Moves: 11
[download]

--Jim

Update: Hmmm . . . after much thought, this approach uses the first out-of-sequence slot for the initial move. Once the initial move is made, the rest is optimal, but it raises a potential flaw--perhaps by pre-testing each of the unordered initial moves, the optimal solution for any given trial could be determined. I'll do some more experimenting and post the results.