Pathologically Eclectic Rubbish Lister PerlMonks

Re: sort with fewest moves

by chipmunk (Parson)
 on Feb 10, 2002 at 17:02 UTC ( #144473=note: print w/replies, xml ) Need Help??

in reply to sort with fewest moves

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.

Replies are listed 'Best First'.
Re: Re: sort with fewest moves
by wog (Curate) on Feb 10, 2002 at 18:42 UTC
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
Node Status?
node history
Node Type: note [id://144473]
help
Chatterbox?
 [ambrus]: Corion, if you're here, can you check the spam filter logs to see what's triggering this time? [ambrus]: Petroza had trouble posting yesterday, but has posted Issues Fetching URL with a variable token since. [mz2255]: Yes, just edited the scratchpad. Not sure if I'm doing something wrong, it's my first time.

How do I use this? | Other CB clients
Other Users?
Others cooling their heels in the Monastery: (11)
As of 2017-10-19 15:25 GMT
Sections?
Information?
Find Nodes?
Leftovers?
Voting Booth?
My fridge is mostly full of:

Results (255 votes). Check out past polls.

Notices?