Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

Let's say you have a randomised deck of $N$ different cards. An $M$-action ($M\le N$) is defined as follows: you look at the top $M$ cards of the deck, put as many of them as you choose on top of the deck, and the rest on the bottom, each time in any order you choose. How many $M$-actions does it take to arrange an $N$-card deck into a given order?

share|improve this question
    
Tangentially, you might be interested in a book the Wall St. Journal recently reviewed, "Magical Mathematics", by Diaconis and Graham (Harvard and Stanford). Here's the link. You might not be able to get in unless you are a subscriber. But you probably find stuff on it elsewhere. online.wsj.com/article/… –  Andrew Dec 21 '11 at 20:36
2  
I'm sorry you asked this question, because I have paying work to do. I must be strong... –  TonyK Dec 21 '11 at 21:08
    
Say M=4 and N is large. If I find 1 and 2 in the first look, put them on top and put the others on the bottom, which cards do I look at for the next try? The 3rd, 4th, 5th and 6th? If I look at the top 4 again I can never get more than the first 4 sorted. –  Ross Millikan Dec 21 '11 at 21:40
    
@Ross: I think you still look at the 1st, 2nd, 3rd, and 4th. So you may want to send the first few to the bottom of the deck for a while (keeping them in order whenever they rise to the top again) to get to some fresh cards. –  mjqxxxx Dec 21 '11 at 22:05
1  
@TonyK: 1234 --> 3421 --> 3214 --> 1432. –  mjqxxxx Dec 21 '11 at 22:56

1 Answer 1

up vote 9 down vote accepted

Let's call the operation of looking at the top $M$ cards and placing them on the top and/or bottom of the deck in arbitrary order scrying. There are $N!$ different states that the deck can be in initially, and each iteration of scry M presents $(M+1)!$ choices of where to place the cards. So a simple lower bound is that, in the worst case, it must take $\lceil{\log(N!)/\log((M+1)!)}\rceil$ iterations to sort the deck. This is conservative, as seen by considering the $M=1$ case, where the task may not even be achievable.

A better lower bound is obtained by picturing the cards in a circle, with a pointer between the bottom and top cards. Then the operation scry M becomes: rearrange the $M$ cards clockwise from the pointer, in place, then move the pointer up to $M$ places clockwise. To place the cards in the correct order, ignoring the position of the pointer, must take $\lceil{\log((N-1)!)/\log(M!)}\rceil$ operations in the worst case.

On the other hand, it can't take more than $N^2/(M-1)$ iterations, as demonstrated by the following algorithm. Assume without loss of generality that the target order is $\{1,2,...N\}$. For $i=1,2,...N$: move the pointer clockwise by $M$ positions per iteration until card $i$ is in the window, then move card $i$ and the pointer clockwise by $M-1$ positions per iteration until the $i$-th position is in the window, then deposit card $i$ in the $i$-th position and increment $i$. This takes at most $N/(M-1)$ iterations per correctly placed card. This can be improved by carrying along the next $k$ cards instead of just one (reducing the distance the pointer can be moved per iteration to $M-k$). With this variation, it takes at most $N/(M-k)$ iterations per $k$ correctly placed cards, for a total count of $N^2/(k(M-k))$ iterations, which is minimized at $4N^2/M^2$ by taking $k=M/2$.

Because of the finite "range" of the operation, I would conjecture that the actual complexity is $\Theta(N^2)$, i.e., that this upper bound is asymptotically tight, and that it is achieved when the deck is shuffled into the reverse of its target order. I'm less sure about the exact dependence on $M$.


Update: For $M=2$ and $2\le N\le10$, the maximum number of operations required is $1,1,3,5,7,11,14,19,23.$ This is reasonably well fit by $\alpha N^2$, where $\alpha$ is around $0.2-0.25$. The entropy lower bound $\lceil{\log((N-1)!)/\log(M!)}\rceil$ with the same parameters is $0,1,3,5,7,10,13,16,19.$

share|improve this answer
3  
Goodness, what a curiously specific choice of name... :-) –  Steven Stadnicki Dec 21 '11 at 22:59
1  
Also, I believe the proof that the complexity is $\Theta(N^2)$ is pretty straightforward, along the lines you suggested (although I'm less sure about the maximum): any operation on $M$ cards can only change the number of inversions of the deck's permutation by $O(f(M))$ for some $f$ - specifically, some function of $M$ but not of $N$ - and since a permutation can have $\Theta(N^2)$ inversions we need to do $\Theta(N^2)$ of these operations to get them all. –  Steven Stadnicki Dec 21 '11 at 23:03

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.