Author |
Topic: Shuffle a deck of cards. (Read 7786 times) |
|
Aryabhatta
Uberpuzzler
Gender: 
Posts: 1321
|
 |
Shuffle a deck of cards.
« on: May 16th, 2004, 11:53am » |
 Quote  Modify
|
You have a deck of 2n cards represented as an array
a1 a2 a3 ... an b1 b2 .... bn
Write an algorithm which will shuffle the array to
b1 a1 b2 a2 ..... bn an
The catch is: you can only use O(1) extra space.
i.e you have to do an 'in-place' shuffle of the array.
|
|
 IP Logged |
|
|
|
TenaliRaman
Uberpuzzler
I am no special. I am only passionately curious.
Gender:
Posts: 1001
|
|
Re: Shuffle a deck of cards.
« Reply #1 on: May 16th, 2004, 12:44pm » |
Quote Modify
|
I can do the entire thing using just 1 variable and with a time complexity of around O(n2).
Hint (nearly big one) : think abt modelling it on inplace insertion sort
|
|
IP Logged |
Self discovery comes when a man measures himself against an obstacle - Antoine de Saint Exupery
|
|
|
towr
wu::riddles Moderator
Uberpuzzler
Some people are average, some are just mean.
Gender:
Posts: 13730
|
|
Re: Shuffle a deck of cards.
« Reply #2 on: May 16th, 2004, 1:08pm » |
Quote Modify
|
hmm.. based on that ::you could adapt quicksort.
assuming there is an ordering operator for an and bn and you can distinguish both decks::
we can do better though.. I can think of something easily enough if n is a power of two, but I'll have to see if I can generalize that..
|
|
IP Logged |
Wikipedia, Google, Mathworld, Integer sequence DB
|
|
|
towr
wu::riddles Moderator
Uberpuzzler
Some people are average, some are just mean.
Gender:
Posts: 13730
|
|
Re: Shuffle a deck of cards.
« Reply #3 on: May 16th, 2004, 2:50pm » |
Quote Modify
|
Here are some cases for which a simple linear time algorithm I have works. Can anyone find a pattern in it?
n =1
n =2
n =5
n =6
n =9
n =14
n =18
n =26
n =29
n =30
n =33
n =41
n =50
n =53
n =65
n =69
n =74
n =81
n =86
n =89
n =90
n =98
I also have an recursive algorithm for O(n log n) time that works (and could still be speeded up significantly If I could figure out the pattern for the above)
|
|
IP Logged |
Wikipedia, Google, Mathworld, Integer sequence DB
|
|
|
Barukh
Uberpuzzler
Gender:
Posts: 2276
|
|
Re: Shuffle a deck of cards.
« Reply #4 on: May 17th, 2004, 9:30am » |
Quote Modify
|
Maybe, the following helps?
[smiley=square.gif]
Number the cards from 1 to 2n. What is to be done, is called the "In Shuffle". The general rule for it is: the card number k ends in the place that was originally occupied by the card whose number is 2k modulo 2n+1.
[smiley=square.gif]
|
|
IP Logged |
|
|
|
towr
wu::riddles Moderator
Uberpuzzler
Some people are average, some are just mean.
Gender:
Posts: 13730
|
|
Re: Shuffle a deck of cards.
« Reply #5 on: May 17th, 2004, 9:55am » |
Quote Modify
|
The problem is that with shuffling you can easily loose track of which card has what number. And there isn't room for much administration.
|
|
IP Logged |
Wikipedia, Google, Mathworld, Integer sequence DB
|
|
|
Aryabhatta
Uberpuzzler
Gender:
Posts: 1321
|
|
Re: Shuffle a deck of cards.
« Reply #6 on: May 17th, 2004, 10:46pm » |
Quote Modify
|
You might not be looking for one, but here is one hint:
Try the cases when n is 1,4,13,40,....
|
|
IP Logged |
|
|
|
Barukh
Uberpuzzler
Gender:
Posts: 2276
|
|
Re: Shuffle a deck of cards.
« Reply #7 on: May 17th, 2004, 11:54pm » |
Quote Modify
|
on May 16th, 2004, 2:50pm, towr wrote:Here are some cases for which a simple linear time algorithm I have works. Can anyone find a pattern in it?
n =1
n =2
n =5
n =6
n =9
n =14... |
|
I think I have it (not sure if it helps): For these and only these n, 22n = 1 mod (2n+1), and no smaller exponent has its property. In group theory, one would say that element 2 in a multiplicative group [bbz]/(2n+1)[bbz] has order 2n.
Example: n = 2 is on the list, so 24 = 1 mod 5, and 4 is the smallest such number. At the contrary, n = 3 is not on the list, so we have 26 = 1 mod 7, but also 23 = 1 mod 7.
|
| « Last Edit: May 17th, 2004, 11:56pm by Barukh » |
IP Logged |
|
|
|
towr
wu::riddles Moderator
Uberpuzzler
Some people are average, some are just mean.
Gender:
Posts: 13730
|
|
Re: Shuffle a deck of cards.
« Reply #8 on: May 18th, 2004, 12:41am » |
Quote Modify
|
I don't think it helps, but it does aptly describe the problem.
Because the problem is exactly that it's easy to do the swaps when you can go through all the numbers in one cycle (like for all the n I posted).
But for f.i. n=3 there are two cycles. Some have even more, and to get the right permutation you have to complete all cycles (and thus have to find exactly one starting state on all of them)
I've noticed that for at least the low n's you can just start at the first odd positions till you've swapped 2n elements. But is that true for larger n?
For example with n=3,
we can start in the first position, and 1 goes to 2, 2[to]4, 4[to]1, that's one cycle but only 3 swaps, we continue with 3, 3[to]5, 5[to]6, 6[to]3, 6 = 2*n swaps, so we're done.
With n = 7 we get 1,2,4,8 in the first cycle, 3,9,12,6 in the second, 5 and 10 in the third and 7,11,13,14 in the 4th and last.
If this pattern persists it's easy enough to solve the problem in linear time for all n (all we need as extra space is a counter, one swap-space and the number where we started our current cycle)
|
| « Last Edit: May 18th, 2004, 1:04am by towr » |
IP Logged |
Wikipedia, Google, Mathworld, Integer sequence DB
|
|
|
Aryabhatta
Uberpuzzler
Gender:
Posts: 1321
|
|
Re: Shuffle a deck of cards.
« Reply #9 on: May 18th, 2004, 7:26am » |
Quote Modify
|
Barukh wrote:
>I think I have it (not sure if it helps): For these and only
>these n, 2^2n = 1 mod (2n+1), and no smaller exponenthas
>its property. In group theory, one would say that element 2
>in a multiplicative group Z/(2n+1) has order 2n.
>
>Example: n = 2 is on the list, so 2^4 = 1 mod 5, and 4 is the
>smallest such number. At the contrary, n = 3 is not on the
> list, so we have 2^6 = 1 mod 7, but also 2^3 = 1 mod 7.
Not exactly true, but close.
For eg: 2^24 = 1 (mod 25) and no other 2^x = 1 (mod 25) for x < 24. But 12 is not on the list. This is because Z/(2n+1) contains only numbers which are relatively prime to (2n+1).
I think the list given by towr is such that 2n+1 is a prime. We will not have all primes in the list, as order of 2 in Z/p for some primes is not p-1. (eg p = 7)
towr, my guess is for the list of n you gave we have only 1 cycle. ?
|
|
IP Logged |
|
|
|
towr
wu::riddles Moderator
Uberpuzzler
Some people are average, some are just mean.
Gender:
Posts: 13730
|
|
Re: Shuffle a deck of cards.
« Reply #10 on: May 18th, 2004, 8:25am » |
Quote Modify
|
on May 18th, 2004, 7:26am, Aryabhatta wrote:| towr, my guess is for the list of n you gave we have only 1 cycle. ? |
|
Yes, indeed..
For these it is easy to proof a simple linear algorithm exists, just cycle through all the elements swapping one with the next.
There are two ways to proceed from here
-Try to recognize for which n this works, and integrate that into the O(n log(n)) algorithm to speed it up
-Or try to find a way to easily find starting points for the other cycles when there are more than 1. For instance by finding the lowest ranked element in each cycle. If those are 1,3,5,7.. that'd be nice, but of course we'd need to prove it
|
|
IP Logged |
Wikipedia, Google, Mathworld, Integer sequence DB
|
|
|
Barukh
Uberpuzzler
Gender:
Posts: 2276
|
|
Re: Shuffle a deck of cards.
« Reply #11 on: May 18th, 2004, 9:09am » |
Quote Modify
|
on May 18th, 2004, 7:26am, Aryabhatta wrote:Not exactly true, but close.
For eg: 2^24 = 1 (mod 25) and no other 2^x = 1 (mod 25) for x < 24. But 12 is not on the list. This is because Z/(2n+1) contains only numbers which are relatively prime to (2n+1). |
|
I must disagree with you here: 220 = 1 mod 25, and therefore 12 is not on the list. In general, it is easy to prove that if the condition described in my previous post is satisfied, then powers of 2 will go over every number, which is equivalent having just a single cycle. In group theory, one would say that the group is cyclic, and call 2 the generator of the group.
Quote:| I think the list given by towr is such that 2n+1 is a prime. |
|
That's true: if 2n+1 is not a prime, then it follows from the Euler's theorem that there exist a number m < 2n such that 2m = 1 mod (2n+1).
on May 18th, 2004, 8:25am, towr wrote:| -Or try to find a way to easily find starting points for the other cycles when there are more than 1. For instance by finding the lowest ranked element in each cycle. If those are 1,3,5,7.. that'd be nice, but of course we'd need to prove it |
|
Unfortunately, it's not always true: for n = 62, the first cycle includes not only 1, but also 3.
Aryabhatta, let me ask you the following yes or no question: are you aware of the general linear time, constant space algorithm?
|
|
IP Logged |
|
|
|
towr
wu::riddles Moderator
Uberpuzzler
Some people are average, some are just mean.
Gender:
Posts: 13730
|
|
Re: Shuffle a deck of cards.
« Reply #12 on: May 18th, 2004, 9:23am » |
Quote Modify
|
on May 18th, 2004, 9:09am, Barukh wrote:| Unfortunately, it's not always true: for n = 62, the first cycle includes not only 1, but also 3. |
|
That's a shame..
Back to the drawing board..
Quote:| Aryabhatta, let me ask you the following yes or no question: are you aware of the general linear time, constant space algorithm? |
|
'the' implies there is one, is there?
Aryabhatta, only asked for a constant space one, it'd just be that much nicer to get a linear-time one.
|
|
IP Logged |
Wikipedia, Google, Mathworld, Integer sequence DB
|
|
|
Grimbal
wu::riddles Moderator
Uberpuzzler
Gender:
Posts: 7526
|
|
Re: Shuffle a deck of cards.
« Reply #13 on: May 18th, 2004, 10:24am » |
Quote Modify
|
on May 18th, 2004, 9:09am, Barukh wrote:Unfortunately, it's not always true: for n = 62, the first cycle includes not only 1, but also 3.
|
|
In fact, already for n=11, the 1st cycle is:
1,2,4,8,16,9,18,13,3,6,12
It contains 3. The other cycle would start at 5:
5,10,20,17,11,22,21,19,15,7,14
|
|
IP Logged |
|
|
|
Grimbal
wu::riddles Moderator
Uberpuzzler
Gender:
Posts: 7526
|
|
Re: Shuffle a deck of cards.
« Reply #14 on: May 18th, 2004, 10:47am » |
Quote Modify
|
I just realized that O(1) space is impossible.
The reason is that the index you use to access the array containing the data must have at least log2(n) bits. And that is larger than O(1).
If you relax the rule and assume you can use an integer without upper bound, then you can use one such integer to store as many bits of information you want, for instance one bit per item telling whether it was moved or not.
|
|
IP Logged |
|
|
|
Aryabhatta
Uberpuzzler
Gender:
Posts: 1321
|
|
Re: Shuffle a deck of cards.
« Reply #15 on: May 18th, 2004, 12:13pm » |
Quote Modify
|
Barukh wrote:
[td]
2^20 = 1 (mod 25)
[/td]
Yes of course. Sorry about that. phi(25) = 20.
if phi(p) = p -1 and 2 is a generator of Z/p, then there is only once cycle.
Barukh wrote:
[td]
Are you aware of the general linear time algorithm
[/td]
Grimbal wrote:
[td]
O(1) is not possible. It is actually O(log n).
[/td]
Yes. There is an O(n) time algorithm which uses only O(log n) bits. Using O(log n) bits is considered O(1) space as we need to have at least that many bits to represent n. (I think i read this somewhere in one of Knuth's books)
If we write say a C prog, it will use only a constant amount of variables (each being O(log n) bits of course). So the O(1) space could be thought of as referring to number of variables or something similar.
Barukh, from the way you posed your question, it seems like you already know an algorithm. Do you? 
|
|
IP Logged |
|
|
|
towr
wu::riddles Moderator
Uberpuzzler
Some people are average, some are just mean.
Gender:
Posts: 13730
|
|
Re: Shuffle a deck of cards.
« Reply #16 on: May 18th, 2004, 1:17pm » |
Quote Modify
|
on May 18th, 2004, 12:13pm, Aryabhatta wrote:| Barukh, from the way you posed your question, it seems like you already know an algorithm. Do you? |
|
There is (at least) one http://www.csr.uvic.ca/~jellis/Publications/shuffle.ps
But it sounds dreadfully complicated to me.. It does however do what I suggested earlier, find 'seeds' for each cycle.
|
|
IP Logged |
Wikipedia, Google, Mathworld, Integer sequence DB
|
|
|
towr
wu::riddles Moderator
Uberpuzzler
Some people are average, some are just mean.
Gender:
Posts: 13730
|
|
Re: Shuffle a deck of cards.
« Reply #17 on: May 18th, 2004, 1:30pm » |
Quote Modify
|
Is it easy enough to find the largest m [le] n for which there is a single cycle?
Because then you could just move the n-m elements at the end of the first half to just in front the last n-m elements. And then shuffle the first 2m and the last 2(n-m) elements as seperate arrays.
ie if we have n=7
1 2 3 4 5 6 7 8 9 10 11 12 13 14
m=6 is the largest smaller one with a single cycle, so we move 7 to the position after 13
1 2 3 4 5 6 8 9 10 11 12 13 7 14
in-shuffle the first 12 elements
8 1 9 2 10 3 11 4 12 5 13 6 7 14
then the last 2 seperately
8 1 9 2 10 3 11 4 12 5 13 6 14 7
done
I think that would still be O(n) (not 100% sure though..)
|
|
IP Logged |
Wikipedia, Google, Mathworld, Integer sequence DB
|
|
|
Aryabhatta
Uberpuzzler
Gender:
Posts: 1321
|
|
Re: Shuffle a deck of cards.
« Reply #18 on: May 18th, 2004, 1:46pm » |
Quote Modify
|
towr wrote:
>Is it easy enough to find the largest m <= n for which there >is a single cycle?
>Because then you could just move the n-m elements at the
>end of the first half to just in front the last n-m elements.
>And then shuffle the first 2m and the last 2(n-m) elements
>as seperate arrays.
That might be difficult. That sort of m must be a prime number and not all primes give rise to exactly one cycle. But you are right. If we can find an m for which the permutation becomes 'easy' then we have an O(n) time algorithm.
I gave this hint earlier:
[]
Try it for n = 1,4,13,40, etc
[]
|
|
IP Logged |
|
|
|
towr
wu::riddles Moderator
Uberpuzzler
Some people are average, some are just mean.
Gender:
Posts: 13730
|
|
Re: Shuffle a deck of cards.
« Reply #19 on: May 18th, 2004, 2:22pm » |
Quote Modify
|
That sequence suggest 'times 3 + 1', but 40*3+1=121 isn't valid.. So it's not a very helpfull hint..
|
|
IP Logged |
Wikipedia, Google, Mathworld, Integer sequence DB
|
|
|
Aryabhatta
Uberpuzzler
Gender:
Posts: 1321
|
|
Re: Shuffle a deck of cards.
« Reply #20 on: May 18th, 2004, 3:31pm » |
Quote Modify
|
towr wrote:
> That sequence suggest 'times 3 + 1', but 40*3+1=121 isn't
>valid.. So it's not a very helpfull hint..
The total number of elements is 2n.
(as the problem was originally stated)
What did you mean by 'isnt valid' ?
|
|
IP Logged |
|
|
|
towr
wu::riddles Moderator
Uberpuzzler
Some people are average, some are just mean.
Gender:
Posts: 13730
|
|
Re: Shuffle a deck of cards.
« Reply #21 on: May 18th, 2004, 11:36pm » |
Quote Modify
|
That n=121 doesn't have just one cycle, but multiple..
|
|
IP Logged |
Wikipedia, Google, Mathworld, Integer sequence DB
|
|
|
Aryabhatta
Uberpuzzler
Gender:
Posts: 1321
|
|
Re: Shuffle a deck of cards.
« Reply #22 on: May 18th, 2004, 11:42pm » |
Quote Modify
|
towr wrote:
> That n=121 doesn't have just one cycle, but multiple..
the other values (except n=1) in that sequence also have multiple cycles..
|
|
IP Logged |
|
|
|
towr
wu::riddles Moderator
Uberpuzzler
Some people are average, some are just mean.
Gender:
Posts: 13730
|
|
Re: Shuffle a deck of cards.
« Reply #23 on: May 19th, 2004, 1:09am » |
Quote Modify
|
well n=121+1=122 doesn't either..
(2,5,14,41 do)
So what is that sequence suppose to hint at?
|
|
IP Logged |
Wikipedia, Google, Mathworld, Integer sequence DB
|
|
|
towr
wu::riddles Moderator
Uberpuzzler
Some people are average, some are just mean.
Gender:
Posts: 13730
|
|
Re: Shuffle a deck of cards.
« Reply #24 on: May 19th, 2004, 2:37am » |
Quote Modify
|
The integer sequence database gives two interesting sequences, A071642 (equivalent to where an array of size 2n gives one cycle) and A001122 (related to the first sequence)
And the latter suggest that there isn't an easy subsequence, as it has not been proven (only conjectured) the sequence is even infinite.
|
| « Last Edit: May 19th, 2004, 2:48am by towr » |
IP Logged |
Wikipedia, Google, Mathworld, Integer sequence DB
|
|
|
|
RIDDLES SITE
WRITE MATH!
Home 
Help 
Search 
Members 
Login 
Register
Reply
Notify of replies
Send Topic
Print