## Generating Random Permutations

Often I have a finite set S of objects which need to be examined in a random order without replacement. A straightforward solution would be to pick a random integer between 0 to n – 1 where n = |S| and then examine r-th element.

while (true) { r = rand() % n; a[r] = 0; // or do some work on a[r] }

That however leaves a possibility of consecutively drawing the same integer – an unacceptable situation in some applications. For example, if you’re trying to randomly play compositions in a music player, you’re leaving a possibility for the user to be served same composition two times in a row – a very disgruntling experience.

So instead of randomly drawing an element from S, we can map S to a sequence from 0 to n-1 and then permute the sequence, thereby generating the random permutation of S.

In the study of computer science, to my astonishment, I learned that the following approach to random permutation (i.e. shuffling) of an array wouldn’t work.

for (int i = 0; i < n; i++){ int r = rand() % n; int t = a[r]; a[r] = a[i]; a[i] = t; }

For one, what is a definition of a genuinely random permutation? Well, given n elements in a set (which must all be distinct by definition of set) you have n! permutations. Thus, if a permutation is genuinely random, it has a chance 1/n! of being generated. That defines random permutation.

Let’s see why the approach above doesn’t cut it in terms of generating a genuinely random permutation of S. Every element from 0 to n-1 is swapped with some other randomly chosen element. Such random selection results in every element having a probability of 1/n to be chosen. At the end, the entire sequence has a total probability of (1/n)^n to be generated, which is smaller than 1/(n!).

Now, the following algorithm actually does the task of generating a genuinely random shuffling and the reason is as follows: every i-th element has a 1/(n-i) of being selected (where 0 <= i < n). This is due to the way how the random element for swapping is selected.

```
for (int i = 0; i < n; i++){
int r = i + rand() % (n - i - 1);
int t = a[i];
a[i] = a[r];
a[r] = t;
}
```