Beefy Boxes and Bandwidth Generously Provided by pair Networks
Perl-Sensitive Sunglasses
 
PerlMonks  

Re: Re: sort with fewest moves

by theorbtwo (Prior)
on Feb 10, 2002 at 22:59 UTC ( [id://144519]=note: print w/replies, xml ) Need Help??


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.

Log In?
Username:
Password:

What's my password?
Create A New User
Domain Nodelet?
Node Status?
node history
Node Type: note [id://144519]
help
Chatterbox?
and the web crawler heard nothing...

How do I use this?Last hourOther CB clients
Other Users?
Others having a coffee break in the Monastery: (5)
As of 2024-03-28 13:29 GMT
Sections?
Information?
Find Nodes?
Leftovers?
    Voting Booth?

    No recent polls found