Author |
Topic: Shuffle a deck of cards. (Read 7788 times) |
|
Barukh
Uberpuzzler
Gender: 
Posts: 2276
|
 |
Re: Shuffle a deck of cards.
« Reply #25 on: May 19th, 2004, 4:39am » |
 Quote  Modify
|
Wow! It gets really interesting!
on May 18th, 2004, 12:13pm, 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 May 18th, 2004, 1:17pm, towr wrote:
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 ?
|
|
 IP Logged |
|
|
|
Barukh
Uberpuzzler
Gender:
Posts: 2276
|
|
Re: Shuffle a deck of cards.
« Reply #26 on: May 19th, 2004, 4:48am » |
Quote Modify
|
on May 19th, 2004, 1:09am, 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 (3m - 1)/2, but I don't see how this helps... 
|
|
IP Logged |
|
|
|
Aryabhatta
Uberpuzzler
Gender:
Posts: 1321
|
|
Re: Shuffle a deck of cards.
« Reply #27 on: May 19th, 2004, 9:21am » |
Quote Modify
|
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";
|
|
|
|
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 #28 on: May 19th, 2004, 9:27am » |
Quote Modify
|
on May 19th, 2004, 9:21am, 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..
|
|
IP Logged |
Wikipedia, Google, Mathworld, Integer sequence DB
|
|
|
Aryabhatta
Uberpuzzler
Gender:
Posts: 1321
|
|
Re: Shuffle a deck of cards.
« Reply #29 on: May 19th, 2004, 10:01am » |
Quote Modify
|
on May 19th, 2004, 9:27am, 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
|
|
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 #30 on: May 19th, 2004, 11:11am » |
Quote Modify
|
ok..
So now, what good is it to look at 2n+1 = 3k?
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.
|
|
IP Logged |
Wikipedia, Google, Mathworld, Integer sequence DB
|
|
|
Aryabhatta
Uberpuzzler
Gender:
Posts: 1321
|
|
Re: Shuffle a deck of cards.
« Reply #31 on: May 19th, 2004, 11:21am » |
Quote Modify
|
on May 19th, 2004, 11:11am, towr wrote:ok..
So now, what good is it to look at 2n+1 = 3k?
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...
|
|
IP Logged |
|
|
|
Aryabhatta
Uberpuzzler
Gender:
Posts: 1321
|
|
Re: Shuffle a deck of cards.
« Reply #33 on: May 19th, 2004, 12:11pm » |
Quote Modify
|
on May 19th, 2004, 11:54am, towr wrote:| To find the number of cycles? |
|
It also prints out the cycles..
Looks like perl was not the right choice 
|
|
IP Logged |
|
|
|
Barukh
Uberpuzzler
Gender:
Posts: 2276
|
|
Re: Shuffle a deck of cards.
« Reply #34 on: May 20th, 2004, 6:16am » |
Quote Modify
|
Under the publications of the same author, there is another paper. In section 7, they present a simpler shuffling algorithm. The idea is related to the following:
on May 18th, 2004, 1:30pm, towr wrote: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. |
|
and
on May 18th, 2004, 1:46pm, 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 = 2k – 2; for this case, albeit not a single cycle, the structure of cycles is easily computable.
on May 19th, 2004, 9:21am, Aryabhatta wrote:| Here is some perl code which might be useful: |
|
How much memory does this code use?
|
|
IP Logged |
|
|
|
Aryabhatta
Uberpuzzler
Gender:
Posts: 1321
|
|
Re: Shuffle a deck of cards.
« Reply #35 on: May 20th, 2004, 9:38am » |
Quote Modify
|
on May 20th, 2004, 6:16am, Barukh wrote:Under the publications of the same author, there is another paper. In section 7, they present a simpler shuffling algorithm. The idea is related to the following:
and
They choose m = 2k – 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.
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.
I hope you guys found this problem interesting!
|
| « Last Edit: May 20th, 2004, 9:40am by Aryabhatta » |
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 #36 on: May 20th, 2004, 10:04am » |
Quote Modify
|
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..
|
|
IP Logged |
Wikipedia, Google, Mathworld, Integer sequence DB
|
|
|
Barukh
Uberpuzzler
Gender:
Posts: 2276
|
|
Re: Shuffle a deck of cards.
« Reply #37 on: May 20th, 2004, 10:45am » |
Quote Modify
|
I think I've got it... Just one question:
on May 20th, 2004, 9:38am, 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 
|
|
IP Logged |
|
|
|
Aryabhatta
Uberpuzzler
Gender:
Posts: 1321
|
|
Re: Shuffle a deck of cards.
« Reply #38 on: May 20th, 2004, 11:32am » |
Quote Modify
|
on May 20th, 2004, 10:45am, 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 May 20th, 2004, 10:45am, Barukh wrote:
That's fantastic solution, Aryabhatta! it's simpler than all I saw before. You should certainly write a paper on this
|
|
|
|
IP Logged |
|
|
|
|
RIDDLES SITE
WRITE MATH!
Home 
Help 
Search 
Members 
Login 
Register
Reply
Notify of replies
Send Topic
Print