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 => cslot 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 => aslot 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.


Replies are listed 'Best First'.  

Re: sort with fewest moves
by chipmunk (Parson) on Feb 10, 2002 at 17:02 UTC  
 [reply] 
by wog (Curate) on Feb 10, 2002 at 18:42 UTC  
... 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: 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  
For example, with Perl you could solve this specific problem with the following two statements: and, of course, with one statement: 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:
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] 
by axelrose (Scribe) on Feb 10, 2002 at 19:25 UTC  
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  
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] 
by hossman (Prior) on Feb 12, 2002 at 06:58 UTC  
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)
 [reply] [d/l] 
by axelrose (Scribe) on Feb 11, 2002 at 19:38 UTC  
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:)  [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  
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] 
by theorbtwo (Prior) on Feb 10, 2002 at 22:59 UTC  
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] 
by hossman (Prior) on Feb 11, 2002 at 01:03 UTC  
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] 
by theorbtwo (Prior) on Feb 11, 2002 at 01:16 UTC  
by axelrose (Scribe) on Feb 11, 2002 at 19:26 UTC  
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  
Sample Output
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] 