Random Permutation

So, I’ve totally been writing this blog for almost a week, but so far I haven’t talked about how an actual algorithm works. Here’s a classic algorithm.

Let’s say you have an array of n elements a[0] through a[n-1]. You would like to generate a random permutation of this array. This means that any ordering of the array is equally probable, which means that if you look at any position in a, any element has an equal chance of being there: 1 in n (1/n). We assume that we have the function r(n) which generates a uniform random integer between 0 and n-1, inclusive. (In C, you could do this with random() % n, and in Java you’d do (int)(Math.random() * n).)

On two occasions while interviewing, I have been asked for an algorithm to permute an array. Both times the interviewer was amazed when I showed them this algorithm. Many people assume that a second storage array is necessary for remembering numbers you have picked, but you can do it in place with no memory. The algorithm (usually credited to Knuth, but see below) is quite simple:

For i = 1 to n-1:

• Let j = r(i+1)


• Swap a[i] and a[j]

My guess as to why more people don’t know it is due to its interesting use of induction. Software engineers generally learn of induction in college, fear it, learn how to parrot back enough to pass the classes that use it, then promptly forget it. But recursion is ubiquitous and unavoidable. Whether explicitly recursing with a function calling itself, or implicitly in a loop, any time later steps assume that earlier steps have done their work over part of the data, you need induction. Instead of fearing induction, learn how it works and learn how you can rely on it to do more with your data.

So how does the algorithm use induction? Suppose we are in iteration i. Assume inductively that a[0]…a[i-1] are a random permutation of that part of the array. As a base case, a[0] starts as being a permutation of itself. Now consider what the array will look like after the swap. Element i has an equal chance of being in any position 0…i. What about the remaining elements? Each one has a (i-1)/i chance of standing still and a 1/i chance of being put in the ith spot. If it stands still, it had a 1/(i-1) chance of being there by the induction hypothesis. But multiplying this by the stand-still probability, we get a 1/i chance of it being there after the swap. Together with the swap probability, this means that it has a 1/i chance of being in any spot, which is the definition of a uniform permutation.

As a side note, Wikipedia gives a different version:

• For i = 0 to n-2:
  
  
  
  • Let j = i + r(n-i)
  
  
  • Swap a[i] and a[j]
  
  

This has the advantage that as soon as the i-loop visits a location, its value is finalized so you can output the permutation as it is being created. The disadvantage is that it’s “less inductive” in that, after the ith iteration, you don’t have a true permutation of the first i elements, but only part of a permutation of all n elements. Also, if you are simply generating a random permutation of the numbers 0…n-1 (or analogously the result of some function), you can replace a[i] with i (or f(i)) in the first version and you don’t need to initialize the array. This doesn’t work in the second because of its “future swaps”. This is the version that most people give. A proof of its correctness is given here.

What are some uses of random permutations? They can be good for generating test data, e.g. for a sorting function or any other function which should be able to deal with random data. They can be good as a starting point for a hill-climbing algorithm, e.g. with Traveling Salesman. And, of course, they’re great for asking about in interviews.

http://www.algoblog.com/2007/06/04/permutation/