Perfect Shuffle Algorithm

Factual Questions
1

I was given a problem for a job interview for a computer programming job. I was to write a routine that cuts a computer simulated deck and performs a perfect shuffle. A perfect shuffle, you cut the deck x cards from thre top. Then the bottom card from the top of the deck goes down first, then the bottom card from the bottom of the deck on top of it, one at a time, until one of the stacks runs out, then the remaining cards go on top of the deck. I was to simulate this pretty easy in JAVA and it works fine. The question he had was if the deck was 1001 cards, and you cut from the top 102 cards, then perfect shuffled, how many times would you have to shuffle the deck to return it’s to it’s original order? My algorithm works, but runs slow for large decks. I let it run for 16 hours, it shuffled 800,000,000+ times and I suspended it. He says there is a much simpler, faster way to come up with the answer, than the way I did it.

They way I did it, is I created an array of 1002 cards in computer memory, then created a 2nd array, shuffled the 1st into the 2nd, compared to see if the new was in the original order, if not, copied the 2nd array back into the deck, and repeated until the came up in th4e right order.

Does anybody have any ideas, how to do this simpler, faster?

I do know in a perfect shuffle, the top card gets lowered into the deck 2 positions every shuffle. Also, every shuffle I am only shuffling 204 cards (102 off the top + 102 off the bottom) and putting the remaining 797 cards on the top of the deck.

I could use this job.

2

I don’t quite understand the question. You are shuffling the 102 cards back into the other 900? Or you are just taking 102 cards and doing a perfect shuffle on them (51 cards on a side) until they come back to the same order, or what?

I take it there is no requirement to actually randomize anything here, eh? Some people’s idea of a ‘perfect shuffle’ is one in which there is no latent entropy from the original deck (i.e. perfect random distribution).

One answer to your question is that if a perfect shuffle s is iterated f times on a deck of 2n cards, where f is the exponent of 2,mod(2n-1), the deck is restored to its original ordering. For example, a 52-card deck is returned to its original ordering after 8 perfect shuffles, since 2[sup]8[/sup]=1,mod 51.

For more information, I suggest you read “The Theory of Gambling and Statistical Logic” by Richard Epstein. Or, you might go to Dejanews and do a search in the rec.gambling.poker newsgroup for ‘perfect shuffle’. The subject has come up there before.

3

I am shuffling the top 102 cards into the bottom 899. So only 204 cards get shuffled each time. But don’t forget the next 102 are taken off the top next time. I am begining to see a pattern on a print out, but it is not obvious.

I have searched deja.com and posted it to sci.stat.math, etc…

4

I hope you get the job if only to tell all of your coworkers what an asshole the interviewer is. I guarantee you, I could ask every single software engineer working in my department this question and noone would know or care, and you could probably bet even money that the interviewer never had to figure out the answer.
Man. Just hearing about crap like that burns me up.

5

The amazing thing about this is that I enjoyed the challange. I am trying to learn JAVA and this was good experience. The potential employer admits that no one now ad ays answers his puzzle. Programmers now a days are in so high demand that they refuse to take tests. It is not that if you don’t pass the test you don’t get the job, it shows how well you think. It is a complex simulation. Right now I have lots of time and I think very well.

I was looking for patterns in the card dealings and did discover a pattern. The bottom card gets moved up through the deck. When it reaches the bottom again the deck is in a total different order. It took over 300 shuffles of the deck to get to that point. But now I have a template/map that shows where each card goes after shuffling 300+ times. By mapping the cards to the template, it is like shuffling the deck 300+ times. This made the routine run 300+ times faster. By using the same logic, you could then wait until the 1st 2 cards are the same then use that as a template and it would run 6,000+ faster, then the 1st 3 cards the same, etc…

I am a very good computer programmer (co-author of WordStar) and you can see my 1st JAVA program at www.cyberthings.com/java/firefly.htm
This is an internet/industry 1st. It is a simulation of a toy I make. But, you use the mouse to shake and control the toy, just as you would use the handle in the actual toy, and the simulation shows you an actual representaion of what the toy would look like.

Check out the rest of my art work at www.cyberthings.com

6

JF, my program was much like your first attempt: shuffling one array into another and seeing if it’s back in original order; if not, making the new array the old array and repeating.

Mine only took about a minute to run and came up with 97020 shuffles.

I used a function to return the new position in the deck given a card’s old position. Maybe we used different functions. See if mine is the same as yours:[ul][li]If the card was #1 - 102, it’s new position will be #799 - 1001, odds only.[/li][li]if the card was #103 - 899, it’s new position will be #1 - 797.[/li]if the card was #900 - 1001, its new position will be #798 - 1000, evens only.[/ul]

7

It doesn’t seem obvious to me that the reoccurence of the 2nd card in the second spot would have a period that is a multiple of the reoccurence of the 1st card’s. What I mean is, your 6000x faster algorithm might end up skipping the first correct answer.

What I would do would be to just focus on one card at a time. How many shuffles until card 1 is first again? How many shuffles from time 0 before card 2 is first again? The cards should all have some definite period. Now you can multiply all the periods to get an answer, or you can find the LCM(?) for the right answer.

(Forgot my math terms.) For example, say the period of card 1 is 2, card 2 is 3, and card 3 is 6. They will be ordered identically after 236=36 tries, but the right answer is LCM(2,3,6)=6.

Rav

8

Yeah, what Rav said. :slight_smile:

A light went on after I posted my last message. Instead of the “whole deck” approach, I tried what he detailed.

I counted how many times it would take for card 1 to become 1st again, card 2 to become 2nd again, etc. I then took the least common multiple of all the numbers (mostly repeats), and I got the same answer as I did iteratively: 97020.

To find all of these counts took less than a second. (I then manually figured the LCD, but the computer could figure that out in the first second too. I just didn’t feel like writing an LCD algorithm.)

FYI, none of the cards ever cycles through all the positions. Most took 735 shuffles to repeat. Others took 180, 77, and 9 (!). These factor to 3x5x7[sup]2[/sup], 2[sup]2[/sup]x3[sup]2[/sup]x5, 7x11, and 3[sup]2[/sup]. The LCD is therefore 2[sup]2[/sup]x3[sup]2[/sup]x5x7[sup]2[/sup]x11 = 97020.

9

And (not coincidentally, but surprisingly): 735 + 180 + 77 + 9 = 1001.

10

I made a mistake in my description (though it should not matter) there were 1002 cards and you cut 101 off the top of the deck, I doubt the # of shuffles would be much different.
For 1002 cards, 101 cards cut the answer was 5,812,104,600 shuffles.

Ravenous - the reason I know that the 1st correct answer wouldn’t be skipped, is because everytime I check for the 2nd card equal to it’s original value, the 1st card is equal to it’s original value. Now you have a template that skips 6,000 shuffles at a time and the 1st & 2nd card are equal to their original value. Now you do this until the 3rd card is equal to the origianl value and you have a template that allows you to skip 90,000 shuffles. These are guesstimates

I have put on the WEB the source for the program, with comments at www.cyberthings.com/java/DoShuffles.java
My JAVA compiler won’t load right now, but soon after I reboot, I will recompile and run the program with 1001 cards and a cut of 102. So I can give you valid results.

ANybody need a JAVA programmer? I am available.

Do check out my 1st JAVA program, a simulation of a toy I made at www.cyberthings.com/java/ffly.htm This is the 1st time on the Internet you can play with a product with your mouse and keyboard and give an accurate simulation of what the product looks like.

11

Yeah for 1001 cards 102 cut the answer is 97020. It took my computer about 5 seconds, but it had to load it from hard disk, start JAVA (it compiles the JAVA into 80x86 code), etc…

Try running 1002 cards 101 cuts and see how long. I think it took my machine in JAVA about 30 minutes.

AWB I can’t believe you wrote and ran that program so quick and your equations are phenominal.

12

Now, with 1002 card and a 101 cut, it’ll take 5,812,104,600 shuffles for the whole deck to return to its original order.

13

Could somebody dumb this thing down for me and describe 1) what a perfect shuffle is or isn’t, 2) a quick hint or two on the combinatorial mathematics involved is and 3) if you would be so kind as to start with a ssmaller deck of 5, 10, 12, 13 cards and then walk me through these examples?

Noise is for Toys Boys!

14

A perfect, perfect shuffle for 52 cards:

  1. Cut the deck with the top 26 cards in your left hand. The bottom 26 cards in your right hand.
  2. From your left hand place the bottom card in the stack down, then from your right hand place the bottom card from the bottom of it’s stack down on top of the left card.
  3. Repeat step 2 until all cards are shuffled.

The permutation I described, you would have a deck of 1002 cards, cut the deck with the top 101 cards in your left hand, and the remaining 901 cards in your right hand. Shuffle the 101 cards from your left hand to the 101 cards into first 101 cards in your right hand. Your right hand now has 800 extra cards, which you put on the top of the deck. Then you shuffle them again. The problem I was faced with is how many times do you have to shuffle the cards as above until the return to the original order. It is over 5 billion times. The next problem is to look at the patterns and come up with an algorithm that makes it quicker to solve.
By shuffling in a computer as explained above, it took 120 hours shuffle 5 billion+ times. I noticed a pattern, and came up with a algorithm that then took 25 minutes to shuffle. Then these smart asses found patterns and came up with an algorithm that took seconds to come up with the answer. From 120 hours to seconds, and I still don’t even understand what the hell they did, but it works.

15

JimFox: By shuffling in a computer as explained above, it took 120 hours shuffle 5 billion+ times. I noticed a pattern, and came up with a algorithm that then took 25 minutes to shuffle. Then these smart asses found patterns and came up with an algorithm that took seconds to come up with the answer. From 120 hours to seconds, and I still don’t even understand what the hell they did, but it works.

OK, here what I did:
[list=1][li]Designed a function to return the position of a card after a shuffle, given its initial position:[/li]


FUNCTION newpos(x:integer):integer;

  BEGIN
    IF (x >= cutsize+1) AND (x <= decksize-cutsize)
      THEN newpos:=x-cutsize
    ELSE IF (x<=cutsize)
      THEN newpos:=x*2+(decksize-2*cutsize)
    ELSE
      newpos:=2*x-decksize-1;
  END;

This function works with a variable decksize and cutsize. The program around this only allows decksize >= 2*cutsize.
[li]Starting with card 1, I applied my newpos function repeatedly until it returned to position 1. I then noted how many times it took and saved it in an array. I did this again for card 2…card decksize.[/li]


  FOR j:=1 TO decksize DO
    BEGIN
      k:=j; n:=j; m:=0;
      REPEAT
        n:=newpos(n); m:=m+1;
      UNTIL n=k;
      recycle[j]:=m;
    END;

[li]I then took the least common multiple LCM of all of these counts (not too daunting, since most are repeats), which gave me the minimum number of shuffles needed.[/li]E.g., If you had a 13-card deck and a 5-card cut, for each card it would take the following shuffles to return back to their original places, not necessarily at the same time as the rest of the deck:
Card 1: 6
Card 2: 2
Card 3: 5
Card 4: 5
Card 5: 6
Card 6: 6
Card 7: 2
Card 8: 5
Card 9: 5
Card 10: 6
Card 11: 5
Card 12: 6
Card 13: 6

Now, factor these numbers to their prime factors:
2 = 2^1
5 = 5^1
6 = 2^1 * 3^1

The LCM is the product of the highest power of each prime factor listed. Therefore, the LCM = 2^1 * 5^1 * 3^1 = 30. Only 30 shuffles are needed to restore the 13-card deck.

For your 1002/101 deck, the shuffles needed are: 9, 40, 50, 206, 230, 232, and 235. These factored are:
9 = 3^2
40 = 2^3 * 5^1
50 = 2^1 * 5^2
206 = 2^1 * 103^1
230 = 2^1 * 5^1 * 23^1
232 = 2^3 * 29^1
235 = 5^1 * 47^1

Taking the highest powers gives:
2^3 * 3^2 * 5^2 * 23 * 29 * 47 * 109 =
5,812,104,600[/list=1]

16

Alternatively you could use a permutation look up table and keep applying the permutation to the original ordered array.

I tried the 1001 cards with 102 off the top shuffle, and my Pentium 200 flipped through the deck in 1.46 seconds. Most of that time was spent checking for the exit condition, too.

I think AWB’s method may be faster though.

Anyway, the reason why you don’t want to shuffle the array itself, is that the costs of inserting into an array are very high (order N^2).

Also, if you’re interested, permutations (via group theory) are usually explained in any good introductory abstract algebra text.