Perfect shuffling puzzle (requires programming)

[NickGlover]

To answer your earlier question about the speed of my algorithm:

Its initial part is O( n ), then the 2nd part is just one full pass, but it runs in O( 2n ). My LCM runs worst case in O( log( k ) ) for just two numbers where k is the smaller number, so for shuffles( 1002, 101 ), it runs in O( log( 206 ) + log( 235 ) + log( 9 ) + log( 232 ) + log( 50 ) + log( 40 ) ). This is always less than O( n ), and for shuffles( 1002, 101 ) it is less than 7*64.

Do you do LCM( a, b ) by calculating a*b/GCD( a, b ) (using Euclid's algorithm for the GCD)? It doesn't sound like it to me. You shouldn't have to sieve for prime factors to do an LCM.

IIRC, JavaScript uses a 64-bit float for integer and float math. This float will obviously go above 2^64, but the lower digits will lose accuracy (note: you only have 53-bits devoted to the digits; the rest is for the exponent and sign). My guess is that your answer for shuffles( 1002, 334 ) is wrong because of this.

I think it's been long enough that we can reveal our algorithm(s) now. How does your solution work, Maybeso? I'll describe mine if it is different from yours.

[Maybeso]

I think it's been long enough that we can reveal our algorithm(s) now. How does your solution work, Maybeso? I'll describe mine if it is different from yours.

Okay, here is how I tackled the problem. I will use shuffles(9, 4) as an example.

1. Perform 1 shuffle, mapping the transform. I build the map in the same order as the shuffle, so I can ignore which half has cards remaining.
map[3] = 9; map[9] = 8
map[2] = 7; map[8] = 6
map[1] = 5; map[7] = 4
map[6 5 4] = 3 2 1;

2. Follow card 1 through many shuffles, c = map[c], until it returns to position 1. Keep the loop length, and mark visited positions. Repeat for each card that hasn't been marked.
Card 1 -> 5, 2, 7, 4, 1 -- loop = 5.
Card 3 -> 9, 8, 6, 3 -- loop = 4.

3. We now have a list of loop lengths, the required number of shuffles is the lcm of all lengths.
After shuffles #4, 8, 16, and 20, cards 3, 6, 8, and 9 will be "at home".
After shuffles #5, 10, 15, and 20, cards 1, 2, 4, 5, and 7 will be "at home".
lcm(5, 4) = 20.

Do you do LCM( a, b ) by calculating a*b/GCD( a, b ) (using Euclid's algorithm for the GCD)? It doesn't sound like it to me. You shouldn't have to sieve for prime factors to do an LCM.

No, I collect the highest exponent of each prime factor from (a, b, c ...) and build my lcm that way.

Javascript doesn't support either gcd or lcm, so I googled for both. I ran across the two definitions of lcm first. And before I found an actual example of Euclid's algorithm, I'd already figured out the code for mine.

I was worried about all the divisions and mods I have to do, but I figured that (a, b, c ...) were bounded by
a+b+c+... = nCard,
which limits the amount of factoring more than it limits a*b*c*.... ( or does it? )

My biggest worry was overflowing the variable. If I'd realized (and been certain) I could do g=a, g=g*b/gcd(g,b), g=g*c/gcd(g,c), ... I would've used it instead.

Yes, I was rather suspicious of all those trailing zeros on 334; the correct answer is:
shuffles(1002, 334) = 22,452,171,121,806,841,800 :mrgreen:

[NickGlover]

My solution was pretty much the same as yours except for the difference in implement our LCMs. I was curious if anyone had a different way of looking at the problem and still getting a correct answer quickly.

Originally Posted by Maybeso

Javascript doesn't support either gcd or lcm, so I googled for both.

Most programmers' languages (C/C++, Java, JavaScript, VB) don't. Mathematicians' languages (Matlab, Maple, Mathematica) usually do support these functions.

Originally Posted by Maybeso

I was worried about all the divisions and mods I have to do, but I figured that (a, b, c ...) were bounded by
a+b+c+... = nCard,
which limits the amount of factoring more than it limits a*b*c*.... ( or does it? )

True, your LCM does not run any worse than sqrt(a)+sqrt(b)+sqrt(c)+..., which is less than both nCard and a*b*c*... for a, b, c, ... > 1, so it hardly affects the overall performance of your program.

Originally Posted by Maybeso

My biggest worry was overflowing the variable. If I'd realized (and been certain) I could do g=a, g=g*b/gcd(g,b), g=g*c/gcd(g,c), ... I would've used it instead.

Yeah, I used that and I also did g = ( g / gcd( g, b ) ) * b to avoid any overflow of g * b for answers close to the limits of Java's long (64-bits).

[asdf]

I was thinking about this, and I'm wondering how to find the cut amount for a given deck size which gives the largest amount of shuffles.

[NickGlover]

I don't really have much of an idea about how to find the cut that produces the largest amount of shuffles for a given deck size.

However, I did modify my program to find the answer using brute force for all deck sizes 2 thru 1002 (only took a few minutes). I couldn't see any clear patterns in these answers, but I will get Xyzzy to post a text file on mersenneforum.org with my results, and I will link to it in this post, so that others can look at it.

Edit: The link is http://www.mersenneforum.org/txt/lon...t_shuffles.txt

Note that for answers that were larger than 2^64, I used the web calculator on the GMP site to calculate the correct LCM.

[Maybeso]

I haven't had time to try it, but maybe if you use a smaller deck and, for each cut size print out:[list]the single shuffle mapping,
each of the loops, and the loop lengths,
other info ... gcd, lcm, combinations, permutations, etc.[/list:u]Perhaps a pattern will be revealed?

I'm a little curious about cut sizes that produce the smallest shuffle counts. If we could predict those, then would the opposite predict the biggies?

[NickGlover]

Ok, I did as Maybeso requested.

The file is at http://www.mersenneforum.org/txt/det...uffle_info.txt and it contains all shuffle counts for decks up to 25 cards. For each shuffle count, I have listed the mapping, cycle (loop) lengths, and the actual cycles themselves.

Note that for the cycle lengths, something like [ 1*5, 4 ] means the cycle lengths are 1, 1, 1, 1, 1, 4. I just didn't want to take up a lot of room with a bunch of useless 1's.

I didn't see the usefulness of any GCD or LCM intermediate values. To me it is evident that a lot of unique prime factors in the cycle lenths is what helps cause a high shuffle count. The cycle lengths are all small enough that it easy to see their prime factors.

I was not certain what types of combinations and permutations might be useful, so I didn't put anything like that in the output.

Originally Posted by Maybeso

I'm a little curious about cut sizes that produce the smallest shuffle counts. If we could predict those, then would the opposite predict the biggies?

No, the small shuffle counts happen for trivial cases. A count of 1 occurs for shuffles( nCards, 0 ) and shuffles( nCards, nCards ). A count of 2 occurs for shuffles( nCards, nCards - 1 ).

[Maybeso]

Originally Posted by NickGlover

... To me it is evident that a lot of unique prime factors in the cycle lengths is what helps cause a high shuffle count.

After looking at the text file, I agree -- none of the other information is useful (and takes too long to calc anyway).

So an app that "samples" cut sizes to find the highest shuffle counts would look alot like our current programs. About the only change might be to get the product of the cycle lengths (no lcm) and sort it into a list. Then when you're done, do an lcm on the top several in the list. Not much time saved there. And you'd have to store {cut size, product,[list of cycle lengths]} for each cut size.

Hmm, I think the app could ignore cut sizes > deck size/2, since the top cards become stationary. This produces shuffle counts identical to counts with the deck size and cut size reduced by the number of stationary cards.[code:1]shuffles( 1002, 611) --> 2*611 - 1002 = 220 stationary cards
1002 - 220 = 782, 611 - 220 = 391

shuffles( 1002, 611) = 252
shuffles( 782, 391) = 252

[/code:1]