Proof Random Sampling Interview

Question

Got this algorithm in an interview. To prove that the algorithm randomly shuffles the array. The random sampling algorithm works as follows:

Given an array, B of length N:
   pick a random number from the list and swap it with B[0].   
   Now pick a random element from the remaining of the list
   Swap with the item at index i
   Repeat till no items left

E.g.: B = [1,2,3,4]. Pick random element suppose it is 4. Swap with B[0] to get [4, 2, 3, 1]. Pick items from second index till end e.g. 3 is picked swap with 2 to get [4, 3, 2, 1] and so on.

Code: Index starts from zero

for i = 0 ... N-1:
    random_index = get_random_index(i, N - 1)
    swap(B[i], B[random_index])

I tried to prove that the above algorithm randomly shuffles the array B using Proof by induction: (similar to Fisher Yates Algo. )

Base case either no item or only one item.
Suppose the above works for the range 0 till k-1 and now we are at the kth index.
This means that we have the first k as a random permutation 1/k!
Let R be the random index that is chosen from k to N - 1.
Either :
    If R == k, this can occur with probability `1/(N - k).
Or:
    If R == j for k > j. We chose B[R] with probability 1(N-k)

And then I got stuck and did not know how to create k! * k + 1 to get (k+1)! Could anyone help me prove the above?

Answer 1

It's enough to prove that any shuffling appears with probability $\frac{1}{N!}$. Given a shuffling $[b_1, \cdots, b_N]$, $b_1$ has probability $\frac{1}{N}$ of being first, $b_2$ then has probability $\frac{1}{N-1}$ of being second, and as you remarked $b_i$ had probability $\frac{1}{N-i}$ of being in the $i$th position given the first $i-1$ elements are where they are. So the probability of getting exactly this arrangement is $\frac{1}{N(N-1)(N-2)\cdots(2)(1)} = \frac{1}{N!}$, as desired.