wu :: forums - Print Page


    
      
        wu :: forums
        (http://www.ocf.berkeley.edu/~wwu/cgi-bin/yabb/YaBB.cgi)
      

        riddles >> cs >> Shuffle a deck of cards.
        
(Message started by: Aryabhatta on May 16^th, 2004, 11:53am)

Title: Shuffle a deck of cards.
Post by Aryabhatta on May 16^th, 2004, 11:53am

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.

Title: Re: Shuffle a deck of cards.
Post by TenaliRaman on May 16^th, 2004, 12:44pm

I can do the entire thing using just 1 variable and with a time complexity of around O(n²).

Hint (nearly big one) : [hide]think abt modelling it on inplace insertion sort[/hide]

Title: Re: Shuffle a deck of cards.
Post by towr on May 16^th, 2004, 1:08pm

hmm.. based on that ::[hide]you could adapt quicksort.
assuming there is an ordering operator for a_n and b_n and you can distinguish both decks[/hide]::

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..

Title: Re: Shuffle a deck of cards.
Post by towr on May 16^th, 2004, 2:50pm

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)

Title: Re: Shuffle a deck of cards.
Post by Barukh on May 17^th, 2004, 9:30am

Maybe, the following helps?

[smiley=square.gif][hide]
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.
[/hide][smiley=square.gif]

Title: Re: Shuffle a deck of cards.
Post by towr on May 17^th, 2004, 9:55am

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.

Title: Re: Shuffle a deck of cards.
Post by Aryabhatta on May 17^th, 2004, 10:46pm

You might not be looking for one, but here is one hint:
[hide]
Try the cases when n is 1,4,13,40,....
[/hide]

Title: Re: Shuffle a deck of cards.
Post by Barukh on May 17^th, 2004, 11:54pm

on 05/16/04 at 14:50:53, 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, 2²ⁿ = 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 2⁴ = 1 mod 5, and 4 is the smallest such number. At the contrary, n = 3 is not on the list, so we have 2⁶ = 1 mod 7, but also 2³ = 1 mod 7.

Title: Re: Shuffle a deck of cards.
Post by towr on May 18^th, 2004, 12:41am

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)

Title: Re: Shuffle a deck of cards.
Post by Aryabhatta on May 18^th, 2004, 7:26am

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. ?

Title: Re: Shuffle a deck of cards.
Post by towr on May 18^th, 2004, 8:25am

on 05/18/04 at 07:26:57, 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

Title: Re: Shuffle a deck of cards.
Post by Barukh on May 18^th, 2004, 9:09am

on 05/18/04 at 07:26:57, 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: 2²⁰ = 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 2^m = 1 mod (2n+1).

on 05/18/04 at 08:25:27, 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?

Title: Re: Shuffle a deck of cards.
Post by towr on May 18^th, 2004, 9:23am

on 05/18/04 at 09:09:11, 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.

Title: Re: Shuffle a deck of cards.
Post by grimbal on May 18^th, 2004, 10:24am

on 05/18/04 at 09:09:11, 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

Title: Re: Shuffle a deck of cards.
Post by grimbal on May 18^th, 2004, 10:47am

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.

Title: Re: Shuffle a deck of cards.
Post by Aryabhatta on May 18^th, 2004, 12:13pm

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? ;)

Title: Re: Shuffle a deck of cards.
Post by towr on May 18^th, 2004, 1:17pm

on 05/18/04 at 12:13:39, 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.

Title: Re: Shuffle a deck of cards.
Post by towr on May 18^th, 2004, 1:30pm

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..)

Title: Re: Shuffle a deck of cards.
Post by Aryabhatta on May 18^th, 2004, 1:46pm

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:
[]
[hide]
Try it for n = 1,4,13,40, etc
[/hide]
[]

Title: Re: Shuffle a deck of cards.
Post by towr on May 18^th, 2004, 2:22pm

That sequence suggest 'times 3 + 1', but 40*3+1=121 isn't valid.. So it's not a very helpfull hint..

Title: Re: Shuffle a deck of cards.
Post by Aryabhatta on May 18^th, 2004, 3:31pm

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' ?

Title: Re: Shuffle a deck of cards.
Post by towr on May 18^th, 2004, 11:36pm

That n=121 doesn't have just one cycle, but multiple..

Title: Re: Shuffle a deck of cards.
Post by Aryabhatta on May 18^th, 2004, 11:42pm

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..

Title: Re: Shuffle a deck of cards.
Post by towr on May 19^th, 2004, 1:09am

well n=121+1=122 doesn't either..
(2,5,14,41 do)
So what is that sequence suppose to hint at?

Title: Re: Shuffle a deck of cards.
Post by towr on May 19^th, 2004, 2:37am

The integer sequence database (http://www.research.att.com/~njas/sequences/) gives two interesting sequences, A071642 (http://www.research.att.com/projects/OEIS?Anum=A071642) (equivalent to where an array of size 2n gives one cycle) and A001122 (http://www.research.att.com/projects/OEIS?Anum=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.

Title: Re: Shuffle a deck of cards.
Post by Barukh on May 19^th, 2004, 4:39am

Wow! It gets really interesting!

on 05/18/04 at 12:13:39, Aryabhatta wrote:

if phi(p) = p -1 and 2 is a generator of Z/p, then there is only once cycle.

Right. And phi(p) = p – 1 is equivalent to p is prime.

Quote:

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? ;)

No, I don’t (if we don’t count the towr’s link). I just wanted to know that we didn’t seek the improvement in vain.

on 05/18/04 at 13:17:05, towr wrote:

There is (at least) one http://www.csr.uvic.ca/~jellis/Publications/shuffle.ps
But it sounds dreadfully complicated to me.

To me too… From what I understood, follows that quite complicated topics are involved, and if there is another (simpler) solution, it should be really ingenious.

Or, Aryabhatta, are you one of the authors of the aforementioned paper ;) ?

Title: Re: Shuffle a deck of cards.
Post by Barukh on May 19^th, 2004, 4:48am

on 05/19/04 at 01:09:16, towr wrote:

well n=121+1=122 doesn't either..
(2,5,14,41 do)
So what is that sequence suppose to hint at?

The numbers in Aryabhatta's sequence are of the form (3^m - 1)/2, but I don't see how this helps... :-/

Title: Re: Shuffle a deck of cards.
Post by Aryabhatta on May 19^th, 2004, 9:21am

Barukh wrote:
> Or, Aryabhatta, are you one of the authors of the
> aforementioned paper
> The numbers in Aryabhatta's sequence are of the form (3m -
> 1)/2, but I don't see how this helps...

No! I am not the author of that paper :)
For n = (3^m - 1)/2 , 2n+1 = 3^m.

btw, how do you guys get put what the others guy wrote in that box? I tried adding a table but it didn't work.

Here is some perl code which might be useful:

Code:

print "Enter the value of n: ";
$n = <stdin>;
chop $n;
$N = 2*$n;

$LOOP_COUNT = 0;

%SEEN = {};

sub do_loop {
my $count = 0;
my $x = $_[0];

if (exists $SEEN{$x}){
return;
}
$LOOP_COUNT++;
print "$x";
while ($count <= $N){

$x = ((2*$x) % ($N + 1));

if (exists $SEEN{$x}){
last;
}else{
$SEEN{$x} = 1;
print " -> $x";
$count++;
}
}
print " \[ $count \]\n\n";
}

$cur = 1;

while ($cur <= $N){
do_loop($cur);
$cur++;
}

print "Total number of loops = $LOOP_COUNT\n";

Title: Re: Shuffle a deck of cards.
Post by towr on May 19^th, 2004, 9:27am

on 05/19/04 at 09:21:18, Aryabhatta wrote:

btw, how do you guys get put what the others guy wrote in that box? I tried adding a table but it didn't work.

There's a quote link next to a reply link at the top of everybodies post. You can also use [quote] tags..

Title: Re: Shuffle a deck of cards.
Post by Aryabhatta on May 19^th, 2004, 10:01am

on 05/19/04 at 09:27:07, towr wrote:

There's a quote link next to a reply link at the top of everybodies post. You can also use tags..

Aah! Thanks :)

Title: Re: Shuffle a deck of cards.
Post by towr on May 19^th, 2004, 11:11am

ok..
So now, what good is it to look at 2n+1 = 3^k?

And about that piece of code. I'm not very good with perl, but it seems it works with O(n) space due to the seen array.

Title: Re: Shuffle a deck of cards.
Post by Aryabhatta on May 19^th, 2004, 11:21am

on 05/19/04 at 11:11:05, towr wrote:

ok..
So now, what good is it to look at 2n+1 = 3^k?

And about that piece of code. I'm not very good with perl, but it seems it works with O(n) space due to the seen array.

The perl code is not a solution. It is intended as a tool...

Title: Re: Shuffle a deck of cards.
Post by towr on May 19^th, 2004, 11:54am

To find the number of cycles?

Title: Re: Shuffle a deck of cards.
Post by Aryabhatta on May 19^th, 2004, 12:11pm

on 05/19/04 at 11:54:48, towr wrote:

To find the number of cycles?

It also prints out the cycles..
Looks like perl was not the right choice ???

Title: Re: Shuffle a deck of cards.
Post by Barukh on May 20^th, 2004, 6:16am

and

on 05/18/04 at 13:46:20, Aryabhatta wrote:

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.

They choose m = 2^k – 2; for this case, albeit not a single cycle, the structure of cycles is easily computable.

on 05/19/04 at 09:21:18, Aryabhatta wrote:

Here is some perl code which might be useful:

How much memory does this code use?

Title: Re: Shuffle a deck of cards.
Post by Aryabhatta on May 20^th, 2004, 9:38am

on 05/20/04 at 06:16:49, Barukh wrote:

Under the publications of the same author, there is another paper (http://www.csr.uvic.ca/~jellis/Publications/merge.ps). In section 7, they present a simpler shuffling algorithm. The idea is related to the following:

and

They choose m = 2^k – 2; for this case, albeit not a single cycle, the structure of cycles is easily computable.

How much memory does this code use?

The code I gave was not meant as a solution. It was meant as a tool to analyse the permutation when 2n+1 = 3^k.

Anyway, here is the solution I had in mind.
[hide]

As noticed, all we need is to find an m <= n for which the cycles are easy to compute. if m = O(n) then we have a linear time algorithm. Consider the case when m = 3^k - 1.

We will use the following theorem:

Thm: if g is a primitive root of p^2 then g is a primitive root of p^k for k >= 1.

Clearly 2 is a primitive root of 3^2. so 2 is a primitive root of 3^k. This shows that the group Z/3^k is cyclic with 2 being the generator.

So, the cycle containing 1 contains all the elements of Z/3^k. Now consider the cycle containing 3. Its elements are of the form 3*2^m. They will contain all the number which are multiples of 3 but not 3^2. The cycle containing 3^2 will contain all the number divisible by 3^2 but not 3^3 minus the elements in the cycle 3 etc. So we can see that 1,3,3^2,... all belong to different cycles and those are the only cycles.

This gives an O(n) time and O(1) space algorithm for m = 3^k - 1. This implies an O(n) time and O(1) space algorithm for the general n case.
[/hide]

I hope you guys found this problem interesting!

Title: Re: Shuffle a deck of cards.
Post by towr on May 20^th, 2004, 10:04am

I'm afraid my knowledge of group theory is insufficient to really understand that last part..

But yes, it's certainly been an interesting problem..

Title: Re: Shuffle a deck of cards.
Post by Barukh on May 20^th, 2004, 10:45am

I think I've got it... Just one question:

on 05/20/04 at 09:38:30, Aryabhatta wrote:

Thm: if g is a primitive root of p^2 then g is a primitive root of p^k for k >= 1.

Where the following theorem came from?

That's fantastic solution, Aryabhatta! it's simpler than all I saw before. You should certainly write a paper on this ;D

Title: Re: Shuffle a deck of cards.
Post by Aryabhatta on May 20^th, 2004, 11:32am

on 05/20/04 at 10:45:39, Barukh wrote:

I think I've got it... Just one question:

Where the following theorem came from?

That theorem is used to prove that Z/p^k is cyclic. I saw it in some number theory book, don't remember which one.

on 05/20/04 at 10:45:39, Barukh wrote:

That's fantastic solution, Aryabhatta! it's simpler than all I saw before. You should certainly write a paper on this ;D