Random Permutation Generation

Given an array A of items, come up with an algorithm that produces a random permutation of A on every run

Approach 1

Our main objective is here is to generate permutations with good randomness. For an array with $n$ items, we need to ensure every one of the $n!$ permutations will be producible by our algorithm with probability exactly $1/n!$.

Does the following algorithm work?

for (i from 1 to n) do
	j = random(1,n)
	swap(A, i, j)

No. The above algorithm does not ensure that each permutation of A has equal probability of being generated. This can be proved as follows:

For each iteration, there are $n$ possible outcomes of $j$. So, there are a total of $n^n$ outcomes that can be generated (obviously many of them will give rise to the same permutation). But the crucial point to note is that it is (in general) not possible to divide each of the $n^n$ outcomes equally among the $n!$ permutations. In particular, $n^n/n!$ is not necessarily an integer (eg. $n = 3$). So, there is no way that each permutation has equal chance of being chosen).

Approach 2

What about the algorithm below? (Note that once we mark an element as picked, we don’t select it again)

randomPermutation(A)
	create new array B[] of size = A.length;
	for (i = 0 to i = n-1)
		do
			choose j = random(1,n)
		while A[j] is picked // keep trying to find a j such that A[j] has not been picked yet
		// once you have found your A[j],
		B[i] = A[j]
		mark A[j] as picked
	// for every value of i from 0 to n-1, you are essentially picking a random element from A and assigning it to B[i] 
	// you need to mark as picked to make sure that B is ultimately a permutation of A (and you have not added the same
	// element multiple times or forgotten to add some element)

The above algorithm is in fact "random" in the sense that each of the $n!$ permutations have equal chance of being generated. But there are some problems with this algorithm too:

1. Firstly, we are using an additional $O(n)$ space.

2. More importantly, the probability of randomly selecting a previously picked item increases as we progress, leading to more and more time spent on re-picking the random index. As $n$ gets very large, the probability of having to keep re-picking a random index for the last slot approaches 100%. (Think about it this way, if $n = 1000$ and you are at the $999^{th}$ iteration. You have only 1 acceptable value of $j$ that has not been picked yet. But you don’t know what that is and you are trying to find it randomly (trial and error). So, the expected number of iterations to find the correct $j$ would be: $E(X) = 1\times \dfrac{1}{1000} + [ 1 +E(X)] \times \dfrac{999}{1000}$ , where $X$ is the number of times you need to call $random()$ to find the correct $j$ (there is a 1/1000 chance that you get it in the first try, if you don’t get it, then you are at your initial stage again and you have to try again - you haven’t even eliminated anything lol)

Solving the above would give you $E(X) = 1000$. In other words, it would take you $1000$ iterations to find the correct value of $j$ for the last slot. As $n$ gets larger, this expected number also increases!

Best Random Permutation Algorithm

for (int i = 0; i < n; i++):
	j = random(1, n-i) // pick a random element
	swap(A, j, n - i + 1); // send it to the back of the array

It can be shown that each permutation has exactly $1/n!$ probability of being generated.

Time: $O(n)$, Space: $O(1)$

Checking Randomness?

To show that an algorithm does not in fact generate a truly random permutation, it suffices to:

1. find a permutation that can never be generated

2. show that the number of possible choices/decisions made by the algorithms is not a multiple of $n!$ and so each permutation cannot be equally likely

Application Question

Assume that we use a truly random permutation algorithm for peer-checking of homework. That is, given an array of distinct student names A, the algorithm generates a permutation of A (say B). Then, student A[i] is told to grade student B[i]'s homework. If the size of the class is 600, what is the expected number of students who have to grade their own homework?

Answer: Only 1 !!! (Moreover, this does not depend on the size of the class)

The question is identical to asking: “After generating a permutation, what is the probability that a specific element remains in its exact spot?”

Each element has $1/n$ probability of being assigned to any position. In particular, it has $1/n$ probability of being assigned to its original spot. (In other words, the probability that a student named John gets to grade his own homework is $1/n$ —> which depends on the class size)

Alternatively, number of permutations of the remaining $n-1$ elements, if we keep one of them fixed in its place: $(n-1)!$. So, the probability that the element stays in its spot is $\dfrac{(n-1)!}{n!} = \dfrac{1}{n}$.

Since there are $n$ students, the expected number of elements which are at their original spot = $n \times 1/n = 1$

It is interesting that for any student, the probability that they get to grade their own homework is inversely proportional to the total class size but the expected number of such students is independent of the class size.

Alternatively, we can solve it without thinking of permutations at all (and simply using linearity of expectation). Suppose we have $n$ students. Then, for any student $x_i$, the probability that she has to grade her own homework is $\frac{1}{n}$, and this probability is the same for any student.

Let $I_i$ be an indicator variable that is 1 iff student $i$ grades her own homework. Then, we want to calculate $E[I] = E[\sum_i I_i]$.

By linearity (recall that this applies even though the variables are not independent!), we have:

$$E[I] = \sum_{i=1}^n E[I_i] = \sum_{i=1}^n \frac{1}{n}\cdot 1 = 1$$

and so, we get the same answer as before.