## How many perfect shuffles are needed to return to original order?

I've been intrigued by this problem ever since I read about it over at NexTag.com. I didn't quite know how to program it at first sight because I wasn't sure what data structure to use to represent the stack of unique cards. Of course I also didn't know the "trick" to calculate the result quickly. Finally I went with an array and decided to just program it the brute force way to understand the problem better. I could have scribbled with pen and paper to see how the perfect shuffle works, but it was just too manual and error-prone if I didn't keep track. I made my program display all the iterations and ran it through several small cases. I also went ahead and ran the ultimate case of 1002 unique cards at the 101st cut and saw that my program just kept running and running.

Seeing the perfect shuffle work on smaller cases was very helpful. I admit I didn't see what was going at first, but I remember now that one of the strategies with problem solving is to see if there is some kind of pattern. I suppose the harder part is actually figuring out a way to make use of it.

The pattern that I was led to notice was that each unique card will always come back to its original position in the same amount of passes, of course not all of them at the same time otherwise the problem would be very easy to solve.(I suppose.)

So after finding out the passes for each unique card, the problem just boiled down to finding a combination of cycles of each unique card's passes so that all of the cards come back together at the same time, in other words the lowest common multiple(LCM) of all the passes is the number of perfect shuffles needed to return the deck back to its original order.

I didn't know how to find the LCM of a set of numbers let alone just two numbers! I mean I knew how for two small numbers just by knowing some of the multiples and also the easy method was to just multiply the numbers but that won't necessarily find the lowest even though it is a common multiple. After some research, I realized one way to express it algorithmically was to take one of the numbers, multiply it through consecutive numbers starting with 2, but check if the result is a multiple of the other number. If so, then that's the LCM. If not, then multiply the first number with the next consecutive number and check the result again until the LCM is found. But there's some "beginning stuff" to check before doing this: if the two numbers are the same, then the LCM is that number and second if the two numbers are multiples of each other, then the LCM is the larger number.

When I coded this strategy, I found out for the part where I have to multiply the consecutive numbers and do the check, I didn't know whether to operate it on the smaller or larger number. I just said I'll work on the smaller number without any reason. Later on I realized I should have operated on the larger number. This resulted in a performance increase because with the smaller number, I would need to go through several multiplications to eventually find a LCM that is a multiple of the larger number. This would be very bad if the two numbers are very far apart. With the larger number, I realized I wouldn't have to go through as many multiplications to eventually find a LCM that is a multiple of the smaller number. Cool!

Actually there's a longer explanation of why I went this route. Before I noticed the difference, I decided to research further on other ways to calculate the LCD and hopped on to Euclid's Algorithm. I scanned over it and quickly implemented into my program and noticed how big of an improvement it made! I made my program display what the calculations were doing at each step of the way and realized it calculated the LCM much quicker. When I was doing my original LCM strategy, I was wondering why it took a while for some numbers and very quickly for others. It finally dawned on me that I was always calculating the LCM from the smaller number and when the difference is very large, that's what took so long.

Whew! So I made the change and was impressed that it performed the same as using Euclid's Algorithm. Neato! I implemented Euclid's using recursion whereas my implementation was just loops.

Btw, I implemented my solution in C++(actually it's just C, I didn't use any of the fancy C++ stuff) because I haven't played with Java for a while.

`#include <iostream>#include <time.h>using namespace std;long long shuffles(int nSize, int nCut);long long findLowestCommonMultiple(int *arrayNumbers, int nSize);int main(void){    int i = 4;    int j = 2;    long long l;    clock_t c_cpubefore, c_cpuafter;    cout << "Deck size: ";    cin >> i;    cout << "Deck cut: ";    cin >> j;    c_cpubefore = clock();    l = shuffles(i, j);    c_cpuafter = clock();    cout << "cpu time spent calculating: " << (double) (c_cpuafter - c_cpubefore) / CLOCKS_PER_SEC << " seconds" << endl;    cout << "perfect shuffles needed for a set of (size " << i << " and a cut at " << j << ") is: " << l << endl;    return 0;}long long shuffles(int nSize, int nCut){    // simple check for now    if (nCut > nSize) {        cout << "ERROR: can't do shuffle because cut is larger than size of deck" << endl;        return 0;    }    // v2 strategy    // still have originalDeck array, but only do perfect shuffle until each    // element goes back to it's original position    // note: this is not the case where all elements need to be back at the    // same time(because this would just be back to brute force method)    // rather, just record the # of iterations needed for each element to come    // back to its original position individually.    // After that the problem just boils down to finding the unique combination    // for all the iterations such that all the elements come back to their    // original position, in other words, need to find the lowest common    // multiple of the iterations.    // another note: with this strategy, not able to show deck order for all    // iterations, only up to the maximum iterations for an element to come back    // to its original position    int i, j, nTopdeckCount, nBottomdeckCount;    long long lShuffles = 0;    bool bOrdered = false;    bool bNeedToShuffleAgain;    int nBottomdeckSize = nSize - nCut;    int *originalDeck = new int[nSize];    int *keeptrackpositionsDeck = new int[nSize];    int *topDeck = new int[nCut];    int *bottomDeck = new int[nBottomdeckSize];    // initialize the originalDeck and keeptrackpositionsDeck    for (i = 0; i < nSize; i++) {        originalDeck[i] = i;        keeptrackpositionsDeck[i] = 0;    }    while (!bOrdered) {        // get top deck of nCut numbers        for (i = 0; i < nCut; i++) {            topDeck[i] = originalDeck[i];        }        // get bottom deck of nSize - nCut numbers        for (i = nCut; i < nSize; i++) {            bottomDeck[i - nCut] = originalDeck[i];        }        nTopdeckCount = nCut - 1;        nBottomdeckCount = nBottomdeckSize - 1;        for (i = 0, j = nSize - 1; j >= 0; j--, i++) {            if ((i % 2) != 0) {                if (nBottomdeckCount >= 0) {                    originalDeck[j] = bottomDeck[nBottomdeckCount];                    nBottomdeckCount--;                } else {                    for (; j >= 0; j--) {                        originalDeck[j] = topDeck[nTopdeckCount];                        nTopdeckCount--;                    }                    break;                }            } else {                if (nTopdeckCount >= 0) {                    originalDeck[j] = topDeck[nTopdeckCount];                    nTopdeckCount--;                } else {                    for (; j >= 0; j--) {                        originalDeck[j] = bottomDeck[nBottomdeckCount];                        nBottomdeckCount--;                    }                    break;                }            }        }        // increment shuffles count        lShuffles++;        // just did one perfect shuffle, now analyze each element and see if        // it has come back to its original position        bNeedToShuffleAgain = false;        for (i = 0; i < nSize; i++) {            if (keeptrackpositionsDeck[i] == 0) {                if (originalDeck[i] == i) {                    keeptrackpositionsDeck[i] = lShuffles;                } else {                    bNeedToShuffleAgain = true;                }            }        }        if (!bNeedToShuffleAgain) {            bOrdered = true;        }    }    // don't need these anymore    delete []topDeck;    delete []bottomDeck;    delete []originalDeck;     lShuffles = findLowestCommonMultiple(keeptrackpositionsDeck, nSize);    delete []keeptrackpositionsDeck;     return lShuffles;}long long findLowestCommonMultiple(int *arrayNumbers, int nSize){    long long lLCM = arrayNumbers[0];    long long smaller, larger;    for (int j = 1; j < nSize; j++) {        if (lLCM == (long long) arrayNumbers[j]) {            continue;        } else {            if (lLCM < (long long) arrayNumbers[j]) {                smaller = lLCM;                larger = (long long) arrayNumbers[j];            } else {                smaller = (long long) arrayNumbers[j];                larger = lLCM;            }        }        lLCM = larger;        for (int k = 2; (lLCM % smaller) != 0; k++) {            lLCM = larger * k;        }/* This is where I figured out operating on the larger number resulted   in a performance increase.   The above code is a cleaned up version of below.        if ((larger % smaller) == 0) {            lLCM = larger;        } else {            for (int k = 2;  ; k++) {//                lLCM = smaller * k;                lLCM = larger * k;//                if ((lLCM % larger) == 0) {                if ((lLCM % smaller) == 0) {                    break;                }            }       }*/    }    return lLCM;}`

## DSC01683

Ethan making faces to me! How?! hehe

## DSC01682

Another snap of Brandon.

## DSC01681

Trying to snap Brandon, but he saw it coming!

## DSC01680

Back in car and taking pic of Ethan's messy hair after wearing the cap! hehe

## DSC01679

Whoops, heading back now. Didn't even walk much of the bridge. hehe

## DSC01678

Still at the entrance... and look at the crowd!

## DSC01676

Having to look up to Ethan

## DSC01675

Walking on GG Bridge #2, notice the signboard in the background, haven't made much distance. hehe

## DSC01674

Walking on GG Bridge

## DSC01673

Surprising Ethan! Also we're on way to Golden Gate Bridge.

## DSC01672

Ethan camera shy, but moments later got in trouble for something I forgot.

## DSC01671

Never seen this before: spam and rice(and soy sauce in between) wrapped in seaweed. Chris told me this is Hawaiian.

## For reference, baby pigeon weeks ago

software cropped and zoomed shot #2

## For reference, baby pigeon weeks ago

software cropped and zoomed, shot #1