FluxBlog

Through a complex chain of events involving an email to a blog at work, then following links at said blog, and then links from those links, I ended up at Raganwald's blog reading about a semi-popular "interview test question." The question originates from a company called NexTag which invites potential hires to either send their resume in and hope for the best or solve their problem. The following surrounding this question has almost graduated from "obscurity" to "cult."

The naive solution to this problem, shuffling the cards and checking the order, is clearly not going to work. Since there are n! possible permutations, any domain with more than 100 cards could potentially require more cycles to solve than there are cycles left before the entropy of the universe reaches its maximum.

I found myself thinking back fondly to my university course in abstract algebra. The shuffle process is essentially a permutation of a set. Asking how many shuffles is needed to return the entire deck to its original state is the same as asking the order of the permutation group. Since the deck of cards is finite, the order of the group (the number of permutations in one complete cycle) is equal to the least common multiple of the orders of all the cyclic subgroups. You see, getting that degree WAS good for something...

Having solved this obvious first optimization (cutting the run time from eons to seconds) - the obvious next question is: what is the best time complexity for an algorithm to solve this? The naive first order optimization for this problem is O(n^2): You take each 'card' and run it through the permutation until it returns to its original spot, recording the number of permutations this took. In the worst case (which may not really exist), each card would cycle through every other position before returning to its original spot, and... voila! exactly n^2 iterations of the innermost loop.

However, there is a little something else that comes out of permutation group theory: the order of a cyclic subgroup is equal to the length of the subgroup. Thus if value a0 goes through 10 different positions in one cycle, then there are 9 other values that go through the exact same cycle. Thus if one were to "mark off" where we've been, we would only need to consider those positions we haven't visited yet. In other words, a big-O time complexity of exactly n.

In general, O(n) is pretty darned good. Not as good as O(log n) or O(1) maybe, but still, pretty darned good. Suprisingly a google search for solutions to this problem turn up a vast number of solutions that run in quadratic time. This is probably because the domain of the parameters stated (nCards = 1002, iCut = 101) is sufficiently small that an n^2 algorithm completes very quickly.

I still think there is a closed-form solution to this problem (which would be big-O of 1), but alas, that would take some serious effort to derive. So until someone comes up with a better-than-linear solution, I present to you the elegant O(n) solution to the perfect shuffles card problem (and my apologies in advance for not knowing enough about blogger to format this better):

public class shuffle {

 public static long shuffles(int nCards, int nCut ) {
  long result = 1;
  int[] permute = new int[nCards];
  int shufflePoint = nCards-1;
  int shuffleSize = nCut > nCards-nCut ? nCut : nCards-nCut; 
  for ( int i = 0; i < shuffleSize; i++) {
   int topHalfBottomCard = nCut-i-1;
   int bottomHalfBottomCard = nCards-i-1;
   if ( topHalfBottomCard >= 0 )
    permute[shufflePoint--] = topHalfBottomCard;
   if ( bottomHalfBottomCard >= nCut )
    permute[shufflePoint--] = bottomHalfBottomCard;
  }
  
  boolean[] visited = new boolean[nCards];

  for ( int i = 0; i < nCards; i++) {
   int current = permute[i];
   if ( visited[current] ) continue;
   int cycleLength = 0;
   while ( visited[current] == false ) {
    cycleLength++;
    visited[current] = true;
    current = permute[current];
   }
   result = lcm(result,cycleLength);
  }
  return result;
 }

 /*
  * Okay, so I didn't write lcm or gcd... I borrowed them
  * from blogsummaries.blogspot.com
  */
 private static long lcm(long a, long b) {
  return (a*b) / gcd(a, b);
 }
   
 private static long gcd(long a, long b) {
  return (b == 0) ? a : gcd(b, a % b);
 }
   
 public static void main(String[] args) {
  long totalTime = System.currentTimeMillis();
  // long s = shuffles(Integer.parseInt(args[0]),Integer.parseInt(args[1]));
  long s = shuffles(1002,101);
  totalTime = System.currentTimeMillis()-totalTime;
  System.out.println("Required shuffles = "+s);
  System.out.println(""+totalTime+"ms to process");
 }

}

It seems everyone needs a blogger blog. If only to post in other blogger's blogs!

Hello, World!