384.Shuffle an Array

Why this work?

I saw some people asking why this algorithm is correct. Here is my understanding. Hope it helps.

Proof: Suppose this algorithm works, i.e. for each position j (starting from 0), the probability of any number in the range[0,j] to be at position j is 1/(1+j).

Let’s look at int i = random.nextInt(j + 1):
(1) If i == j, nums[j] does not need to change its position, which has probability 1/(1+j).
(2) if i !=j, nums[j] needs to be swapped with nums[i]. The probability of any number x in the range [0,j-1] to be at position j = nums[j] changes its position * x is at position i
= (1-1/(1+j)) * (1/j) = 1/(1+j)

Each number has equal probability to be at any position.

class Solution {
    private int[] nums;
    private Random random;

    public Solution(int[] nums) {
        this.nums = nums;
        random = new Random();
    }

    /** Resets the array to its original configuration and return it. */
    public int[] reset() {
        return nums;
    }

    /** Returns a random shuffling of the array. */
    public int[] shuffle() {
        if(nums == null)
            return null;
        int[] a = new int[nums.length];
        for(int i = 0; i < a.length; i++){
            a[i] = nums[i];
        }
        for(int i = 1; i < a.length; i++){
            int randomIndex = random.nextInt(i + 1);
            swap(a, i, randomIndex);
        }
        return a;
    }
    private void swap(int[] a, int i, int j){
        int tmp = a[i];
        a[i] = a[j];
        a[j] = tmp;
        return;
    }
}

/**
 * Your Solution object will be instantiated and called as such:
 * Solution obj = new Solution(nums);
 * int[] param_1 = obj.reset();
 * int[] param_2 = obj.shuffle();
 */