I have a deck of say, $100$ cards, in a physical stack in front of me. I have also (by computer) generated randomly a permutation of these cards in whatever form is convenient. My question is, how do I translate this permutation (relative to the order they're already in) into instructions for rearranging the cards into that new order with the minimum amount of fiddling?
What I mean by that is, if I cut a deck into two parts, I cannot easily control how many cards will be in each part, beyond about $5$-$6$. If I want to have a precise number of cards, I have to do so one at a time, but could equally easily do so from the top or bottom of a stack. I can similarly create any number of new stacks (one card at a time), or combine existing stacks of any size in any order. (Cards could be allowed to reverse facing in doing so, but they must end up with their original facing by the end of the process)
So for the purposes of this question, assume the following operations on the cards and associated costs:
- a stack can be split into two, at cost proportional to the size of the smaller stack
- as a special case of the above, a card can be retrieved from anywhere within a stack, at cost proportional to its depth from the closer side
- two stacks can be combined in any order, at unit cost
- The goal is to end up with a single stack, in the specified order, with minimum cost.
Trivially, I could get the right end result with the original Fisher-Yates method (with the computer providing the list of k values needed) just putting cards into a new stack instead of striking out numbers on paper. However, this doesn't take advantage of being able to move around and combine stacks of cards, and also potentially involves retrieving cards from deep within a stack, which is easy to mess up and which I would like to avoid.
IOW, given a permutation, how would I go about finding the "shortest" process, in terms of operations on card-stacks, for creating that permutation out of an ordered deck?