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( <fromslot>, <toslot> ) 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.
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.
 Starting at slot 1, find the first tape that is not in the right slot.
 Move that tape to slot 0.
 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.
 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.  [reply] 

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:

0 c b a d

a c b 0 d

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:
 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).

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.
 [reply] 
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 inplace 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 2element swap would
look like this:
Granted trying to notate a 3 atatime swap would be
difficult, if even possible (thus the ++).
If we'd known that you had to use a onearmed robot to
begin with, the replies might have been more useful. ;)  [reply] [d/l] [select] 

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.  [reply] [d/l] 
Re: sort with fewest moves (BoseNelson 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 wellknown one is the BoseNelson sort (although trudging through web pages, I seem to be coming across Batcher's OddEven 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 longlost 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 (Minimumcomparison 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$st%t#u'  [reply] [d/l] [select] 

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
 [reply] [d/l] 

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.
 [reply] 
Re: sort with fewest moves
by belg4mit (Prior) on Feb 10, 2002 at 18:27 UTC

 [reply] 
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 1N,
given that the only memory available is
an array from 1N, 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.")  [reply] [d/l] [select] 

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 tapelibrary servicing robot, which only has one operation: switch the tapes in positions N and M. (move(n,m))
You're right about bubblesort 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
 [reply] 

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.
 [reply] [d/l] [select] 


> 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.
 [reply] 
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
Jim
Update: Hmmm . . . after much thought, this
approach uses the first outofsequence slot for the
initial move. Once the initial move is made, the rest is
optimal, but it raises a potential flawperhaps by
pretesting 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.
 [reply] [d/l] [select] 

