http://qs321.pair.com?node_id=144470

axelrose has asked for the wisdom of the Perl Monks concerning the following question:

I'd like to solve a special sorting task with Perl and wonder if this is a standard computer science problem.

Say I have three slots 1..3 and an empty slot 0

slot 1 => c
slot 2 => a
slot 3 => b
slot 0 => 0

The slots hold a labeled object (it's a tape library with magazine slots)

The goal is

slot 1 => a
slot 2 => b
slot 3 => c

and a list of move actions where ideally the number of moves is minimal.

A pragmatic solution is for instance

move( 1, 0 ); # ( 0, a, b, c )
move( 2, 1 ); # ( a, 0, b, c )
move( 3, 2 ); # ( a, b, 0, c )
move( 0, 3 ); # goal order achieved

where the function move( <from-slot>, <to-slot> ) moves an object from one slot to a different slot.

The question is not so much how to implement this in Perl but whether there exists an known algorithm. Of course I'm happy to post a Perl solution here.

Many thanks, Axel.

Replies are listed 'Best First'.
Re: sort with fewest moves
by chipmunk (Parson) on Feb 10, 2002 at 17:02 UTC
Here's an algorithm to find a solution using the shortest possible number of moves. It assumes that you know the proper order for the tapes, which you should, because figuring that out requires zero moves.

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.
If there are N tapes that are not in the right slots, clearly each tape must be moved at least once, for a minimum of N moves. However, in order to move a tape, the destination slot must be empty, so one extra move is required to first move a tape into slot 0. Therefore, the above algorithm, which takes N+1 steps, finds a shortest solution.
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.

Re: sort with fewest moves
by jlongino (Parson) on Feb 10, 2002 at 17:21 UTC
If this were homework (but of course it's not), I imagine a teacher would be very impressed if one of their students developed a uniquely Perl solution. Instead of trying to move elements around one at a time, come up with an algorithm to swap at least two elements.

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]);
and, of course, with one statement:
```(\$slots[1], \$slots[2], \$slots[3]) = (\$slots[2], \$slots[3], \$slots[1]);
Coming up with an algorithm for two in-place swaps shouldn't be too difficult (I've already shown you the Perl idiom), ++ if you can handle more than two elements at a time.

--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)
Granted trying to notate a 3 at-a-time swap would be difficult, if even possible (thus the ++).

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]
It looks nice but I really need a list of move actions for the robot.
Re: sort with fewest moves (Bose-Nelson algorithm)
by grinder (Bishop) on Feb 11, 2002 at 10:42 UTC
Algorithms that do this that have been known about since the 1960s. The most well-known one is the Bose-Nelson sort (although trudging through web pages, I seem to be coming across Batcher's Odd-Even Merge Sort more often).

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.

print@_{sort keys %_},\$/if%_=split//,'= & *a?b:e\f/h^h!j+n,o@o;r\$s-t%t#u'
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

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.

Re: sort with fewest moves
by belg4mit (Prior) on Feb 10, 2002 at 18:27 UTC
For some reason this reminded me of the [id://Hanoi|Towers of Hanoi]. There are of course some differences (slots<n in Hanoi, no swapping either {jlongino++}), but they do seem to be rather similar.

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

Re: sort with fewest moves
by hossman (Prior) on Feb 10, 2002 at 22:15 UTC
The way i'm reading your post is: "I'm looking for an algorithm that will let me sort elements 1-N, given that the only memory available is an array from 1-N, plus a single temp variable, and the only allowed opperation is  move(n, m)".

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.
Re: sort with fewest moves
by jlongino (Parson) on Feb 12, 2002 at 08:33 UTC
Rats! I figured someone would beat me to a solution. I haven't looked closely at hossman's. I came up with the solution without looking at any references. Mine has configurable parameters, produces some elementary stats, and is shorter :P. It can be improved I'm sure, but I was just happy to finish it. Specifically, instead of rebuilding the entire hash, the changed key/values could be updated. TIMTOWTDI!
```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);
}
Sample Output
```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