Jump to content
  • Advertisement
Sign in to follow this  

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.

If you intended to correct an error in the post then please contact us.

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?

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
Sign in to follow this  

  • Advertisement

Important Information

By using GameDev.net, you agree to our community Guidelines, Terms of Use, and Privacy Policy.

We are the game development community.

Whether you are an indie, hobbyist, AAA developer, or just trying to learn, GameDev.net is the place for you to learn, share, and connect with the games industry. Learn more About Us or sign up!

Sign me up!