Q384. Shuffle an Array

Shuffle a set of numbers without duplicates.

Example:

// Init an array with set 1, 2, and 3.
int[] nums = {1,2,3};
Solution solution = new Solution(nums);

// Shuffle the array [1,2,3] and return its result. Any permutation of [1,2,3] must equally likely to be returned.
solution.shuffle();

// Resets the array back to its original configuration [1,2,3].
solution.reset();

// Returns the random shuffling of array [1,2,3].
solution.shuffle();

This is about generating random permutation when we have a random integer generator.

As it sounds, it is not a typical question but definitely something need to know (here I’d rather treat it as something good to know).

The solution mentions about Fisher-Yates shuffle (which I’m not aware before). The approach is straight forward. Suppose we have N integers, the way to generate a random permutation is:

• For jth position, randomly select one from the remaining (N - j + 1) elements.
• Do it from position 1 to N.

Why it works? Since for permutation n1, …, nN,

• n1 has 1 / N probability to be positioned at the first position.
• n2 has 1 / (N - 1) probability to be positioned at the second position.
• And so on so forth.

So, n1, …, nN has 1 / N! probability to be drawn. As there are N! number of permutations, each one of them has the same probability to be drawn.

OK, the important thing is how to implement it efficiently. For a naive implementation, we need to remove the elements that have been selected. It requires $O(N)$ time complexity at each draw and overall it needs $O(N^2)$ time complexity to obtain a permutation.

How to improve? All we need is to maintain the subarray containing the unselected elements. This can be done by swapping. Specifically, at position j (the place we want to fill in), suppose subarray nums[j:] contains the unselected elements, we can swap the selected one (with index j + random_idx where random_idx is among 0:(N-j)) and the current jth element. By doing so, the new subarray nums[j+1:] still contains only the unselected elements. With this approach, we have time complexity $O(1)$ at each draw and overall it takes $O(N)$ time complexity to get one permutation.