You have a deck of 52 cards - for convenience, number them 1 through 52. You cut the cards into two equal halves and shuffle them perfectly. That is, the cards were in the order
1,2,3,...,52
and now they are
1,27,2,28,...,26,52. Let's call this a perfect in-shuffle.

If you repeat this in-shuffling process, how many in-shuffles will it take for the deck to return to its initial ordering (taking for granted that the cards will eventually do so)?
________________________

How does the solution change if you have a deck of 64 cards, or 10, or in general, n cards? For odd integer values of n, in-shuffling will take 1,2,3,...,n to 1,(n+3)/2,2,(n+5)/2,...,n,(n+1)/2. For example, when n=5, the first in-shuffle yields 1,4,2,5,3.

Guys I have a more difficult version of this problem and I have generalized the solution to take into consideration the given scenario. I have written a code for it in Java

Before that  I must tell you about the original problem for which the code was written....

PROBLEM: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

Write a Java program to find the result of shuffles(1002, 101)nCards =1002  ; iCut =102

I have used a class Map which contains the function shuffles which does the job for you.
The result for your problem is turning out to be:5812104600 !!!
Think it should be right..
When you run the code it will print something like .....
CYCLE WITH 1 INVOLVES 230 SHUFFLES
CYCLE WITH 2 INVOLVES 206 SHUFFLES
CYCLE WITH 4 INVOLVES 235 SHUFFLES
CYCLE WITH 8 INVOLVES 9 SHUFFLES
CYCLE WITH 11 INVOLVES 232 SHUFFLES
CYCLE WITH 25 INVOLVES 50 SHUFFLES
CYCLE WITH 41 INVOLVES 40 SHUFFLES
A = 230 B = 206 LCM:23690
A = 23690 B = 235 LCM:1113430
A = 1113430 B = 9 LCM:10020870
A = 10020870 B = 232 LCM:1162420920
A = 1162420920 B = 50 LCM:5812104600
A = 5812104600 B = 40 LCM:5812104600
Number of shuffles before it returns to original :5812104600

Here Cycle involves starting from card number 1 It will take 230 perfect shuffles befor it returns to its original position.
Now I cross out all the elemnts which are a part of this cycle .
Next I chose an uncrossed out element and check after how many shuffles it returns to its original position.
This I keep on doing until all my elements are crossed out . Next I take the LCM of all these shuffle values to give me the number of shuffles required to get back to the original deck position.
Hope it helped....
CODE:Map.java

<BLOCKQUOTE>

code:

<HR>

class Map { int mapIndex[]; boolean flag[]; int nCards; int iCut; long iteration[];int iCount; Map(int nC,int iC){ nCards = nC; iCut = iC; mapIndex = new int[nCards+1]; iteration = new long[100]; iCount = 0; flag = new boolean[nCards+1]; for(int i = 1 ; i <= nCards ; i++) { flag[i] = false; } if(iCut > nCards/2) prune(); generateMap(); } void prune(){ int bot = nCards - iCut; nCards = bot*2; iCut = bot; } void generateMap() { int pA,pB,paM,pbM; pA = iCut;paM = nCards; pB = nCards;pbM = nCards -1; do { mapIndex[pA] = paM; pA--;paM -=2; mapIndex[pB] = pbM; pB--;pbM -=2; }while(pA>0); pbM++; while(pB>iCut){ mapIndex[pB]=pbM; pB--;pbM--; } }long shuffles(){ long shuffle ,temp;temp = shuffle = 0; for(int i = 1 ;i<=nCards;i++){ if(flag[i]) continue; temp = traverse(i); iteration[iCount] = temp; System.out.println("CYCLE WITH "+i+" INVOLVES "+ temp + " SHUFFLES"); iCount++; } shuffle = lcm(); return shuffle;} long lcm() { long lcm = iteration[0]; for(int i = 1 ; i < iCount ; i++ ) { System.out.print("A = "+lcm+" B = "+ iteration[i]); lcm = subLCM(lcm,iteration[i]); System.out.println(" LCM:"+lcm); } return lcm; } long subLCM(long a, long b) { long l = 1 ; long max; long p,q; boolean flag; int i =2; do{ p = a/i; q = b /i ; do { flag = false; if(p*i == a ) { flag = true; a =a/i; p =a/i; } if(q*i == b ) { flag = true; b =b/i; q =b/i; } if(flag) { l = l*i;} }while(flag);i++; }while(a>1 || b>1); return l; } long traverse(int i){ int actual ,mapped; actual = i ; long shuffleCount = 0; do { flag[actual] = true; mapped = mapIndex[actual]; actual = mapped ;shuffleCount++; }while(actual != i); return shuffleCount;} public static void main(String args[]){ Map mP = new Map(1002,101); System.out.println("Number of shuffles before it returns to original :"+mP.shuffles()); }} <HR> NB: In our case we have to call shuffles(52,26);</BLOCKQUOTE> <BLOCKQUOTE>
Regards,
Amitava</BLOCKQUOTE>

Posted by Amitava on 2004-05-21 10:11:42