P is for Practical PerlMonks

### Re: Re: sort with fewest moves

by wog (Curate)
 on Feb 10, 2002 at 18:42 UTC ( #144492=note: print w/replies, xml ) Need Help??

in reply to Re: sort with fewest moves
in thread sort with fewest moves

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.

Create A New User
Domain Nodelet?
Node Status?
node history
Node Type: note [id://144492]
help
Chatterbox?
and the web crawler heard nothing...

How do I use this? | Other CB clients
Other Users?
Others pondering the Monastery: (5)
As of 2022-01-27 21:09 GMT
Sections?
Information?
Find Nodes?
Leftovers?
Voting Booth?
In 2022, my preferred method to securely store passwords is:

Results (71 votes). Check out past polls.

Notices?