Generating a Random Permutation in Excel
The other day, I was modeling something in Excel ("data scientists" out there: laugh all you want, but you too might find this post interesting) and needed to generate a random permutation.
Casual Googling resulted in pretty disappointing information: many suggested to generate a bunch of random integers in [1, N], possibly with repeats, until you cover all N integers. Then, pick the previously unseen unique numbers to extract a subsequence.
The above method actually generates a uniformly random permutation within a reasonable time: the standard coupon collector argument shows that you need ~N*logN random numbers.
But you can actually do this with N random numbers. It's called Fisher-Yates/Knuth shuffling.
Starting with the ordered sequence 1, 2, 3...N, the shuffling algorithm goes like this:
for k = 1 to N-1 pick a random integer m from [k, N] (inclusive) swap the k-th and m-th number endfor
This is easy to verify for N = 2: You are just flipping a coin to decide if you swap 1 with 2. For N > 2, you just need to show that each of 1 through N has an equal chance of getting the k-th slot for 1 through N. In the first step, every number has a 1/N probability of getting into the first slot. For all other slots: the number has (1-1/N) chance of getting/staying there, then by induction, all slots are equally likely, hence (1-1/N)*(1/N-1) = 1/N. This completes the proof.
Anyway, we can use Knuth's shuffle to generate random permutations in Excel.
The issue is, Excel is barely a programming language, and there is no "for loop". But that doesn't mean you can't do iterations! (Ok, we will end up using N^2 space, which kind of defeats the purpose of the algorithm...)
In the rest of this post, I will show you how to implement Knuth's shuffling in Excel. For simplicity, we assume N = 5, but this methodology works with any N (as long as Excel can hold it!)
First, you need to set up k's and m's. The trick here is we pre-generate the random m's. We are using Excel's RANDBETWEEN functions for Column B here.
Also, notice that in C1:G1, we have the sequence 1,2,3,4,5 initialized.
The next step is a bit tricky. Here is what the formula looks like:
For each row, we swap the k-th (Column A) and m-th (Column B) numbers in the previous row. This is what the gigantic IF statement is doing. Furthermore, since we want to run this calculation more than once, I have an extra condition: If the value of k is 1, then instead of the previous row, we use 1,2,3,4,5 to re-initialize the permutation (EDIT: on second thought, you actually do not have to re-initialize this and can keep running against different seed sequences without skewing the overall distribution since it's a 120-state Markov-chain with equal-probability transitions).
(Aside: INDEX function is very useful, but not that many people seem to know about its existence.)
Finally, we drag and expand the formula to populate the rest of the cells. I personally find this step most satisfying when I program in Excel.
C5:G5 is the random permutation.
Running it over and over and over
Now, let's verify this is indeed working. This step is very easy in Excel. We just keep populating Column A through G for subsequent rows. The only thing to watch out for is Column A should repeat 1,2,3,4,1,2,3,4...This can be achieved by using relative reference.
When everything is said and done, here is the distribution of 5! = 120 different permutations of [1,2,3,4,5] with 2,500 samples.
As you can see, it's fairly evenly distributed! The intercept for the line is 21, which is close to 2,500/5! = 20.833...
You can get the spreadsheet here
My employer Treasure Data is also hiring. Most pertinent to the reader: we are looking for a data scientist to help our customers discover more value from their data. Email me at kiyoto-at-treasuredata-dot-com.