# Card Shuffle Problem

This topic is 2872 days old which is more than the 365 day threshold we allow for new replies. Please post a new topic.

## 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
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 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 on other sites
Ah I didn't know that..I guess that makes the problem much simpler.

1. 1
2. 2
Rutin
25
3. 3
4. 4
5. 5

• 10
• 10
• 13
• 20
• 14
• ### Forum Statistics

• Total Topics
632946
• Total Posts
3009363
• ### Who's Online (See full list)

There are no registered users currently online

×