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


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

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

Replies are listed 'Best First'.
Re: Re: Re: sort with fewest moves
by hossman (Prior) on Feb 11, 2002 at 01:03 UTC
    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]
[reply]

In Section Seekers of Perl Wisdom