Search code examples
algorithmmathrepeatshuffleplaying-cards

How many times do I have to repeat a specific shuffle of playing cards to get back to where I started?

This is my first post on Stack Overflow, so please excuse my mistakes if I'm doing something wrong.

Ok so I'm trying to find an algorithm/function/something that can calculate how many times I have to do the same type of shuffle of 52 playing cards to get back to where I started.

The specific shuffle I'm using goes like this:
-You will have two piles.
-You have the deck with the back facing up. (Lets call this pile 1)
-You will now alternate between putting a card in the back of pile 1 Example: Let's say you have 4 cards in a pile, back facing up, going from 4 closest to the ground and 1 closest to the sky (Their order is 4,3,2,1. You take card 1 and put it beneath card 4 mening card 1 is now closest to the ground and card 4 is second closest, order is now 1,4,3,2. and putting one in pile 2.
-Pile 2 will "stack downwards" meaning you will always put the new card at the bottom of that pile. (Back always facing up)
-The first card will always get put at the back of pile 1.
-Repeat this process until all cards are in pile 2.
-Now take pile 2 and do the exact same thing you just did.

My question is: How many times do I have to repeat this process until I get back where I started?

Side notes:
- If this is a common way of shuffling cards and there already is a solution, please let me know.
- I'm still new to math and coding so if writing up an equation/algorithm/code for this is really easy then don't laugh at me pls ;<.
- Sorry if I'm asking this at the wrong place, I don't know how all this works.
- English isn't my main language and I'm not a native speaker either so please excuse any bad grammar and/or other grammatical errors.

I do however have a code that does all of this (Link here) but I'm unsure if it's the most effective way to do it, and it hasn't given a result yet so I don't even know if it works. If you wan't to give tips or suggestions on how to change it then please do, I would really appreciate it. It's done in scratch however because I can't write in any other languages... sorry...

Thanks in advance.

Solution

  • Any fixed shuffle is equivalent to a permutation; what you want to know is the order of that permutation. This can be computed by decomposing the permutation into cycles and then computing the least common multiple of the cycle lengths.

    I'm not able to properly understand your algorithm, but here's an example of shuffling 8 elements and then finding the number of times that shuffle needs to be repeated to get back to an unshuffled state.

    Suppose the sequence starts as 1,2,3,4,5,6,7,8 and after one shuffle, it's 3,1,4,5,2,8,7,6.

    • The number 1 goes to position 2, then 2 goes to position 5, then 5 goes to position 4, then 4 goes to position 3, then 3 goes to position 1. So the first cycle is (1 2 5 4 3).
    • The number 6 goes to position 8, then 8 goes to position 6. So the next cycle is (6 8).
    • The number 7 stays in position 7, so this is a trivial cycle (7).

    The lengths of the cycles are 5, 2 and 1, so the least common multiple is 10. This shuffle takes 10 iterations to get back to the intitial state.

    If you don't mind sitting down with pen and paper for a while, you should be able to follow this procedure for your own shuffling algorithm.