Sign in to follow this  
laeuchli

Card Shuffle Problem

Recommended Posts

Hello All,

One of my friends had an interview the other day and was given this puzzle(we always trade questions after such things).

"The exercise solves a coding problem that involves shuffling a deck of cards.
The problem description is as follows:
You are given a deck containing 313 cards. While holding the deck:
1. Take the top card off the deck and set it on the table
2. Take the next card off the top and put it on the bottom of the deck in
your hand.
3. Continue steps 1 and 2 until all cards are on the table. This is a round.
4. Pick up the deck from the table and repeat steps 1-3 until the deck is in
the original order.
Write a program to determine how many rounds it will take to put the deck back
into the original order."

So my view on this is that its basically a permutation group, and they would like to solve the equation p.p.p....=p^n=e. If this is the case, there is no better solution then determining p and applying it till you get back to where you started. Is that correct, or is there something I'm missing here?
Jesse

Share this post


Link to post
Share on other sites
if you determine the permutation as disjoint cycles then the order is just the lowest common multiple of the cycle sizes.

aka if your permutation is (1 2)(4 8 9)(3 4) then o(p) = lcm(2,3,2) = 6

the permutation would be trivial to compute by doing a single iteration of steps 1,2,3 (getting all cards on the table) and just producing the cycles.

take a deck of 4 cards [1,2,3,4] after steps 1,2,3 we have [4,2,3,1] so the permutation is (1 4) who's order is 2, so for 4 cards only 2 rounds are needed.

Share this post


Link to post
Share on other sites

Create an account or sign in to comment

You need to be a member in order to leave a comment

Create an account

Sign up for a new account in our community. It's easy!

Register a new account

Sign in

Already have an account? Sign in here.

Sign In Now

Sign in to follow this