Author |
Topic: A Perfect Shuffle Problem. (Read 5061 times) |
|
BlueSea
Newbie
Posts: 16
|
 |
A Perfect Shuffle Problem.
« on: Oct 30th, 2007, 8:03am » |
 Quote  Modify
|
Just asked on an interview question like this (somehow interesting)
Given a deck of nCards unique cards, cut the deck iCut cards from top and perform a perfect shuffle. A perfect shuffle begins by putting down the bottom card from the top portion of the deck followed by the bottom card from the bottom portion of the deck followed by the next card from the top portion, etc., alternating cards until one portion is used up. The remaining cards go on top.
The problem is to find the number of perfect shuffles required to return the deck to its original order. Your function should be declared as:
static long shuffles(int nCards,int iCut);
|
|
 IP Logged |
|
|
|
Grimbal
wu::riddles Moderator
Uberpuzzler
Gender: 
Posts: 7527
|
|
Re: A Perfect Shuffle Problem.
« Reply #1 on: Oct 30th, 2007, 8:20am » |
Quote Modify
|
| hidden: | The easiest way is to start with an array with numbers 1..nCard and simulate the shuffling, until you see it came back to the initial order.
The smarter way is to express one shuffle as a permutation, find out the cycles and return the smallest common multiple of the cycle lengths. |
|
| « Last Edit: Oct 30th, 2007, 8:20am by Grimbal » |
IP Logged |
|
|
|
BlueSea
Newbie
Posts: 16
|
|
Re: A Perfect Shuffle Problem.
« Reply #2 on: Oct 30th, 2007, 8:26am » |
Quote Modify
|
I don't quite understand the perfect shuffle very well.
For example, given two sets with a cut:
Set1: 123456
Set2: 789
How to perform perfect shuffle as shown in the problem then? Thanks.
|
|
IP Logged |
|
|
|
Grimbal
wu::riddles Moderator
Uberpuzzler
Gender:
Posts: 7527
|
|
Re: A Perfect Shuffle Problem.
« Reply #3 on: Oct 30th, 2007, 9:26am » |
Quote Modify
|
If you have 123456 and 789, you have nCards=9 and iCard=6, assume "top" is left.
Start with 9 cards
123456789
take 6 cards from the top
123456 / 789
Put the bottom card of the top part on the table, then the bottom of the bottom part, and proceed alternating packs. Obviously at some point, you have only one pack left.
6 -> 96 -> 596 -> 8596 -> ... -> 123748596
So the result of your first shuffle is
123748596
And I realize that we don't need to express the full permutation after all.
|
|
IP Logged |
|
|
|
BlueSea
Newbie
Posts: 16
|
|
Re: A Perfect Shuffle Problem.
« Reply #4 on: Oct 30th, 2007, 10:16am » |
Quote Modify
|
Thanks to Grimbal first
In the second round, the remaining cards will be 123 as top portion, right?
123/748596 -> 748/519263
After the 2nd round of perfect shuffles, the top portion in the third round should be:
748/519263 -> 519/276438
Correct me if this is wrong. Thanks.
|
|
IP Logged |
|
|
|
SMQ
wu::riddles Moderator
Uberpuzzler
Gender:
Posts: 2084
|
|
Re: A Perfect Shuffle Problem.
« Reply #5 on: Oct 30th, 2007, 10:23am » |
Quote Modify
|
It looks like in the above you only cut three cards from the top, not six like Grimbal did in his example.
I get:
1) 123456 / 789 --> 123748596
2) 123748 / 596 --> 123579468
3) 123579 / 468 --> 123456789
So the answer it that the third perfect shuffle returns the deck to its original order.
--SMQ
|
|
IP Logged |
--SMQ
|
|
|
BlueSea
Newbie
Posts: 16
|
|
Re: A Perfect Shuffle Problem.
« Reply #6 on: Oct 30th, 2007, 11:00am » |
Quote Modify
|
I get somehow confused. The problem says that after one portion is used up, the remaining portion is used on the top. What does it mean by "when a portion is used up"? Thank you.
If you have 123456 (top portion) to 789 (bottom portion), it means that "123" is the remaining portion in the top portion after sending 456 to the bottom portion 2. Is this understanding right?
|
|
IP Logged |
|
|
|
SMQ
wu::riddles Moderator
Uberpuzzler
Gender:
Posts: 2084
|
|
Re: A Perfect Shuffle Problem.
« Reply #7 on: Oct 30th, 2007, 11:38am » |
Quote Modify
|
You have a deck of nine cards (nCards = 9):
ABCDEFGHI
To perform a single perfect shuffle, you do the following:
1) Cut the deck between the sixth and seventh card (iCut = 6):
ABCDEF / GHI
2) Deal the bottom card of the top portion to the top of a new pile:
ABCDE / GHI | F
3) Deal the bottom card of the bottom portion to the top of the new pile:
ABCDE / GH | IF
4) Repeat steps 2) and 3) as long as possible:
ABCD / GH | EIF
ABCD / G | HEIF
ABC / G | DHEIF
ABC / | GDHEIF
5) One portion of the original deck is now "used up" -- i.e. there are no more cards left in that portion -- place the remaining cards on top of the new pile:
/ | ABCGDHEIF
The question then asks: how many times do you need to perform a perfect shuffle to return the deck to its original order.
The first time is as above.
The second time:
ABCGDHEIF
ABCGDH / EIF
ABCGD / EIF | H
ABCGD / EI | FH
ABCG / EI | DFH
ABCG / E | IDFH
ABC / E | GIDFH
ABC / | EGIDFH
/ | ABCEGIDFH
The third time:
ABCEGIDFH
ABCEGI / DFH
ABCEG / DFH | I
ABCEG / DF | HI
ABCE / DF | GHI
ABCE / D | FGHI
ABC / D | EFGHI
ABC / | DEFGHI
/ | ABCDEFGHI
So shuffles(9, 6) should return 3.
Clear?
--SMQ
|
|
IP Logged |
--SMQ
|
|
|
BlueSea
Newbie
Posts: 16
|
|
Re: A Perfect Shuffle Problem.
« Reply #8 on: Oct 30th, 2007, 12:41pm » |
Quote Modify
|
Thanks to SMQ, this is quite clear. Thanks again.
|
|
IP Logged |
|
|
|
Mr.Unknown
Newbie
Posts: 4
|
|
Re: A Perfect Shuffle Problem.
« Reply #9 on: Oct 31st, 2007, 1:30am » |
Quote Modify
|
on Oct 30th, 2007, 8:20am, Grimbal wrote:
The smarter way is to express one shuffle as a permutation, find out the cycles and return the smallest common multiple of the cycle lengths |
|
Could you just explain it a little more? or just give a link incase it has been discussed already.
|
|
IP Logged |
|
|
|
towr
wu::riddles Moderator
Uberpuzzler
Some people are average, some are just mean.
Gender:
Posts: 13730
|
|
Re: A Perfect Shuffle Problem.
« Reply #10 on: Oct 31st, 2007, 2:33am » |
Quote Modify
|
on Oct 31st, 2007, 1:30am, Mr.Unknown wrote:| Could you just explain it a little more? or just give a link incase it has been discussed already. |
|
There's similar riddle where e.g. you have the keys of a typewriter switched, and you need to figure out how often you need to type the output to get the original message.
Back to the cards; if you have a card at position i and it moves to position j, then you can look where the card previously at j ended up (which will also be where i ends up if you shuffle again) And you can continue this until you're back at the start.
Now, this path won't be equally long for each card. So you need to find the smallest multiple (i.e. the length they all fit a whole number of times in)
if we take the 9,6 shuffle of before
shuffling once gives ABCEGIDFH
A,B,C return to their own place
D moves to the position of G, which moves to the position of E which moves to D
So after three steps, you're back
And moving on to the next letter we haven't had: F->H->I->F, also three steps
So, the least common multiple is LCM(1,1,1,3,3)=3
|
|
IP Logged |
Wikipedia, Google, Mathworld, Integer sequence DB
|
|
|
SMQ
wu::riddles Moderator
Uberpuzzler
Gender:
Posts: 2084
|
|
Re: A Perfect Shuffle Problem.
« Reply #11 on: Oct 31st, 2007, 8:56am » |
Quote Modify
|
static long gcd(long a, long b) {
return (a == 0) ? b : gcd(b % a, a);
}
static long lcm(long a, long b) {
return a * (b / gcd(a, b));
}
static long shuffles(int nCards, int iCut) {
// check for error
if ((iCut > nCards) || (iCut < 0)) return 0;
// if the cut is past half way, some cards are never shuffled
if (iCut > (nCards / 2)) return shuffles((nCards - iCut) * 2, nCards - iCut);
// check for easy cases
if (iCut == 0) return 1;
if ((iCut == 1) || ((iCut == 2) && ((nCards % 2) == 0))) return nCards;
if (iCut == 2) return ((nCards - 1) / 2) * ((nCards + 1) / 2);
// perform a single shuffle
// (starting from 0, ..., iCut - 1 | iCut, ..., nCards - 1)
int[] deck = new int[nCards];
for(int i = 0; i < iCut; i++) {
// place one from the bottom of the top portion
deck[(nCards - 1) - i * 2] = (iCut - 1) - i;
// place one from the bottom of the bottom portion
deck[(nCards - 2) - i * 2] = (nCards - 1) - i;
}
// place the rest on top
for(int i = 0; i < nCards - iCut * 2; i++) {
deck[i] = iCut + i;
}
// find lcm of the loop lengths, using -1 to mark loops as we go
long total = 1;
for(int i = 0; i < nCards; i++) {
if (deck[i] != -1) {
// haven't seen this loop before
long length = 1;
int j = i, k = deck[i];
deck[i] = -1;
while (k != i) {
// move to next position in loop
length++;
j = k;
k = deck[j];
deck[j] = -1;
}
// got loop length; calculate running lcm
total = lcm(total, length);
}
}
// return lcm of all loop lengths
return total;
}
--SMQ
|
|
IP Logged |
--SMQ
|
|
|
BlueSea
Newbie
Posts: 16
|
|
Re: A Perfect Shuffle Problem.
« Reply #12 on: Nov 1st, 2007, 11:04am » |
Quote Modify
|
Hi SMQ, since you have changed cards[j] to -1, how do you validate the correctness of the algorithm?
Moreover, if big number is used, for example, like (2000, 100), a long-type variable may bear the overflow size...
|
| « Last Edit: Nov 1st, 2007, 11:05am by BlueSea » |
IP Logged |
|
|
|
SMQ
wu::riddles Moderator
Uberpuzzler
Gender:
Posts: 2084
|
|
Re: A Perfect Shuffle Problem.
« Reply #13 on: Nov 1st, 2007, 11:25am » |
Quote Modify
|
on Nov 1st, 2007, 11:04am, BlueSea wrote:| Hi SMQ, since you have changed cards[j] to -1, how do you validate the correctness of the algorithm? |
|
You could make a copy of the deck first, if you wanted to. I'll admit I didn't even compile that code before posting it, let alone run it, so it's possible I made an error, but the general algorithm is mathematically provable.
Quote:| Moreover, if big number is used, for example, like (2000, 100), a long-type variable may bear the overflow size... |
|
The specification called for the function to return a long, so presumably that's large enough for the intended use -- if not, an arbitrary precision math library/type (e.g. Java's BigInt or the GMP library for C) could easily be substituted. I put parenthesis around (b / gcd(a, b)) when calculating the lcm specifically to prevent overflowing any intermediate calculations.
--SMQ
|
| « Last Edit: Nov 1st, 2007, 11:26am by SMQ » |
IP Logged |
--SMQ
|
|
|
BlueSea
Newbie
Posts: 16
|
|
Re: A Perfect Shuffle Problem.
« Reply #14 on: Nov 1st, 2007, 5:13pm » |
Quote Modify
|
Hi SMQ, could you specify how to store the initial deck record and the final deck record for print? I want to check whether they keep same for some large numbers of decks.
Thank you.
|
| « Last Edit: Nov 1st, 2007, 5:14pm by BlueSea » |
IP Logged |
|
|
|
SMQ
wu::riddles Moderator
Uberpuzzler
Gender:
Posts: 2084
|
|
Re: A Perfect Shuffle Problem.
« Reply #15 on: Nov 2nd, 2007, 7:33am » |
Quote Modify
|
Rather than cluttering the main shuffles function, I'd split the perfect shuffle out to it's own function (don't forget that now iCut can be past the half-way point!) and write a separate routine to verify the result:
class Shuffles {
public static void main(String [] args) throws java.io.IOException {
// get card count and cut point
java.io.BufferedReader systemIn =
new java.io.BufferedReader(new java.io.InputStreamReader(System.in));
System.out.print("Number of Cards: ");
int nCards = Integer.parseInt(systemIn.readLine());
if (nCards < 0) {
System.out.println("\n Please enter a non-negative number of cards");
return;
}
System.out.print("Cut after Card #: ");
int iCut = Integer.parseInt(systemIn.readLine());
if (iCut < 0 || iCut > nCards) {
System.out.println("\n Please enter a cut position from zero through the number of cards");
return;
}
// predict number of shuffles
long predicted = shuffles(nCards, iCut);
System.out.println("\nPrediction: the deck will return to its initial order");
System.out.println(" after " + predicted + " perfect shuffles");
// check if user wants to verify prediction
boolean verify = predicted < 1000000;
System.out.print("\nVerify Prediction? " + (verify ? "[Y/n]" : "[y/N]") + ":");
String verifyString = systemIn.readLine();
if (verifyString.startsWith("y") || verifyString.startsWith("Y")) verify = true;
if (verifyString.startsWith("n") || verifyString.startsWith("N")) verify = false;
if (verify) {
// verify prediction
long counted = countShuffles(nCards, iCut);
if (counted == predicted) {
System.out.println("VERIFIED!");
} else {
System.out.println("Verification Failed!");
System.out.println(" Counted number of shuffles is " + counted);
}
}
}
public static long shuffles(int nCards, int iCut) {
// check for error
if ((iCut > nCards) || (iCut < 0)) return 0;
// if the cut is past half way, some cards are never shuffled
if (iCut > (nCards / 2)) return shuffles((nCards - iCut) * 2, nCards - iCut);
// check for easy cases
if (iCut == 0) return 1;
if ((iCut == 1) || ((iCut == 2) && ((nCards % 2) == 0))) return nCards;
if (iCut == 2) return ((nCards - 1) / 2) * ((nCards + 1) / 2);
// perform a single shuffle from a sorted deck
int[] deck = new int[nCards];
for(int i = 0; i < nCards; i++) deck[i] = i;
perfectShuffle(deck, iCut);
// find lcm of the loop lengths, using -1 to mark loops as we go
long total = 1;
for(int i = 0; i < nCards; i++) {
if (deck[i] != -1) {
// haven't seen this loop before
long length = 1;
int j = i, k = deck[i];
deck[i] = -1;
while (k != i) {
// move to next position in loop
length++;
j = k;
k = deck[j];
deck[j] = -1;
}
// got loop length; calculate running lcm
total = lcm(total, length);
}
}
// return lcm of all loop lengths
return total;
}
public static long countShuffles(int nCards, int iCut) {
// create initial sorted deck
int[] deck = new int[nCards];
for(int i = 0; i < nCards; i++) deck[i] = i;
// shuffle until resorted
long count = 0;
boolean sorted;
do {
// shuffle
perfectShuffle(deck, iCut);
count++;
// check for sorted deck
sorted = true;
for(int i = 0; i < nCards; i++) {
if (deck[i] != i) { sorted = false; break; }
}
} while (!sorted);
return count;
}
public static void perfectShuffle(int[] deck, int iCut) {
// copy the deck
int[] oldDeck = new int[deck.length];
for(int i = 0; i < deck.length; i++) oldDeck[i] = deck[i];
// shuffle oldDeck to deck
int interleaved = (iCut * 2 <= deck.length) ? iCut : (deck.length - iCut);
for(int i = 0; i < interleaved; i++) {
// place one from the bottom of the top portion
deck[(deck.length - 1) - i * 2] = oldDeck[(iCut - 1) - i];
// place one from the bottom of the bottom portion
deck[(deck.length - 2) - i * 2] = oldDeck[(deck.length - 1) - i];
}
if (iCut * 2 <= deck.length) {
// place the rest on top
for(int i = 0; i < deck.length - iCut * 2; i++) {
deck[i] = oldDeck[iCut + i];
}
}
}
public static long lcm(long a, long b) {
long uncommon = b / gcd(a,b), result = a * uncommon;
if (result / uncommon != a) {
throw new ArithmeticException("long multiplication overflow");
}
return result;
}
public static long gcd(long a, long b) {
return (a == 0) ? b : gcd(b % a, a);
}
}
D:\Personal\wwu\java>javac Shuffles.java
D:\Personal\wwu\java>java Shuffles
Number of Cards: 52
Cut after Card #: 23
Prediction: the deck will return to its initial order
after 2431 perfect shuffles
Verify Prediction? [Y/n]: Y
VERIFIED!
--SMQ
|
| « Last Edit: Nov 2nd, 2007, 8:24am by SMQ » |
IP Logged |
--SMQ
|
|
|
BlueSea
Newbie
Posts: 16
|
|
Re: A Perfect Shuffle Problem.
« Reply #16 on: Nov 2nd, 2007, 11:45am » |
Quote Modify
|
Cool, SMQ, that works perfectly in Java. It has no overflow in Java for (1200, 100)
If running in C++, I found I must use unsigned long long type to replace all Total, GCD, LCM related variables.
Thanks again for your help.
|
|
IP Logged |
|
|
|
SMQ
wu::riddles Moderator
Uberpuzzler
Gender:
Posts: 2084
|
|
Re: A Perfect Shuffle Problem.
« Reply #17 on: Nov 2nd, 2007, 12:56pm » |
Quote Modify
|
Just for fun: a Java version w/out verification, but using BigInteger so there are no overflows:
import java.math.BigInteger;
class Shuffles {
public static void main(String [] args) throws java.io.IOException {
// get card count and cut point
java.io.BufferedReader systemIn =
new java.io.BufferedReader(new java.io.InputStreamReader(System.in));
System.out.print("\nNumber of Cards: ");
int nCards = Integer.parseInt(systemIn.readLine());
if (nCards < 0) {
System.out.println("\n Please enter a non-negative number of cards");
return;
}
System.out.print("Cut after Card #: ");
int iCut = Integer.parseInt(systemIn.readLine());
if (iCut < 0 || iCut > nCards) {
System.out.println("\n Please enter a cut position from zero through the number of cards");
return;
}
// predict number of shuffles
BigInteger predicted = shuffles(nCards, iCut);
System.out.println("\nThe deck will return to its initial order");
System.out.println(" after " + predicted + " perfect shuffles");
}
public static BigInteger shuffles(int nCards, int iCut) {
// check for error
if ((iCut > nCards) || (iCut < 0)) return BigInteger.ZERO;
// if the cut is past half way, some cards are never shuffled
if (iCut > (nCards / 2)) return shuffles((nCards - iCut) * 2, nCards - iCut);
// check for easy cases
if (iCut == 0) return BigInteger.ONE;
if ((iCut == 1) || ((iCut == 2) && ((nCards % 2) == 0))) return BigInteger.valueOf(nCards);
if (iCut == 2) return BigInteger.valueOf(((nCards - 1) / 2) * ((nCards + 1) / 2));
// perform a single shuffle from a sorted deck
int[] deck = new int[nCards];
for(int i = 0; i < iCut; i++) {
// place one from the bottom of the top portion
deck[(deck.length - 1) - i * 2] = (iCut - 1) - i;
// place one from the bottom of the bottom portion
deck[(deck.length - 2) - i * 2] = (deck.length - 1) - i;
}
// place the rest on top
for(int i = 0; i < deck.length - iCut * 2; i++) {
deck[i] = iCut + i;
}
// find lcm of the loop lengths, using -1 to mark loops as we go
BigInteger total = BigInteger.ONE;
for(int i = 0; i < nCards; i++) {
if (deck[i] != -1) {
// haven't seen this loop before
long length = 1;
int j = i, k = deck[i];
deck[i] = -1;
while (k != i) {
// move to next position in loop
length++;
j = k;
k = deck[j];
deck[j] = -1;
}
// got loop length; calculate running lcm
total = total.divide(total.gcd(BigInteger.valueOf(length)))
.multiply(BigInteger.valueOf(length));
}
}
// return lcm of all loop lengths
return total;
}
}
D:\Personal\wwu\java>javac Shuffles.java
D:\Personal\wwu\java>java Shuffles
Number of Cards: 4000000
Cut after Card #: 1003
The deck will return to its initial order
after 598104629359824399334567129993232076809799758400 perfect shuffles
--SMQ
|
|
IP Logged |
--SMQ
|
|
|
BlueSea
Newbie
Posts: 16
|
|
Re: A Perfect Shuffle Problem.
« Reply #18 on: Nov 4th, 2007, 8:24am » |
Quote Modify
|
cool, it works perfectly. thanks to SMQ.
|
|
IP Logged |
|
|
|
Jigsaw
Guest
|
|
Re: A Perfect Shuffle Problem.
« Reply #19 on: Jun 24th, 2008, 2:56am » |
Quote Modify
 Remove
|
on Oct 31st, 2007, 8:56am, SMQ wrote:
if ((iCut == 1) || ((iCut == 2) && ((nCards % 2) == 0))) return nCards;
if (iCut == 2) return ((nCards - 1) / 2) * ((nCards + 1) / 2);
--SMQ |
|
Sorry that I'm bringing back a very old thread. I was just digging the grave when I found this.
SMQ, if you still remember would you mind explaining in brief how you generalized the values for the case where iCut==2. I worked through a few cases and though I found that the result was in compliance with your formula, I didn't see any general pattern in it(the shuffled deck).
Thank you.
|
|
IP Logged |
|
|
|
SMQ
wu::riddles Moderator
Uberpuzzler
Gender:
Posts: 2084
|
|
Re: A Perfect Shuffle Problem.
« Reply #20 on: Jun 24th, 2008, 6:15am » |
Quote Modify
|
on Jun 24th, 2008, 2:56am, Jigsaw wrote:| SMQ, if you still remember would you mind explaining in brief how you generalized the values for the case where iCut==2. |
|
Sure! Number the starting deck like this: O1 E2 O3 E4 ..., where each O card starts out in an odd-numbered position and each E card starts out in en even-numbered position.
If there are an even number of cards, the deck starts out as O1 E2 O3 E4 ... On-3 En-2 On-1 En,
and after a single perfect shuffle looks like O3 E4 ... On-3 En-2 On-1 O1 En E2.
If we look at the cycle, letting --> represent "moved to the former position of", we find O1 --> En-2 --> En-4 --> ... E4 --> E2 --> En --> On-1 --> On-3 --> On-5 --> ... --> O3 --> O1. This single cycle involves all the cards in the deck, so n perfect shuffles will be required to return it to its unshuffled state. This accounts for the if ((iCut == 2) && ((nCards % 2) == 0)) return nCards; portion.
Otherwise with an odd number of cards, the deck starts out as O1 E2 O3 E4 ... En-3 On-2 En-1 On,
and after a single perfect shuffle looks like O3 E4 ... En-3 On-2 En-1 O1 On E2.
Here we find two cycles: O1 --> On-2 --> On-4 --> ... O3 --> O1, and E2 --> On --> En-1 --> En-3 --> ... E4 --> E2. The first cycle involves all but one of the odd cards, and the second cycle involves the remaining odd card and all of the even cards. Since the numbers of cards in these cycles differ by one we know they're relatively prime and so can skip the formal LCM calculation and simply multiply. This accounts for the if (iCut == 2) return ((nCards - 1) / 2) * ((nCards + 1) / 2); line.
Hope that's clear!
--SMQ
|
|
IP Logged |
--SMQ
|
|
|
Jigsaw
Guest
|
|
Re: A Perfect Shuffle Problem.
« Reply #21 on: Jun 24th, 2008, 6:50am » |
Quote Modify
Remove
|
on Jun 24th, 2008, 6:15am, SMQ wrote:
That's crystal clear. Thanks a lot.
|
|
IP Logged |
|
|
|
|
RIDDLES SITE
WRITE MATH!
Home 
Help 
Search 
Members 
Login 
Register
Reply
Notify of replies
Send Topic
Print