Shuffle an Array
Problem
Implement reset() and shuffle() for an integer array, where shuffle() returns a uniformly random permutation of the original array.
nums = [1, 2, 3, 4, 5]any of 5! = 120 permutations with equal probabilityimport random
class Solution:
def __init__(self, nums):
self.original = nums[:]
self.arr = nums[:]
def reset(self):
self.arr = self.original[:]
return self.arr
def shuffle(self):
for i in range(len(self.arr)):
j = random.randint(i, len(self.arr) - 1)
self.arr[i], self.arr[j] = self.arr[j], self.arr[i]
return self.arrclass Solution {
constructor(nums) {
this.original = nums.slice();
this.arr = nums.slice();
}
reset() { this.arr = this.original.slice(); return this.arr; }
shuffle() {
const a = this.arr;
for (let i = 0; i < a.length; i++) {
const j = i + Math.floor(Math.random() * (a.length - i));
[a[i], a[j]] = [a[j], a[i]];
}
return a;
}
}class Solution {
private int[] original;
private int[] arr;
private Random rng = new Random();
public Solution(int[] nums) {
original = nums.clone();
arr = nums.clone();
}
public int[] reset() { arr = original.clone(); return arr; }
public int[] shuffle() {
for (int i = 0; i < arr.length; i++) {
int j = i + rng.nextInt(arr.length - i);
int t = arr[i]; arr[i] = arr[j]; arr[j] = t;
}
return arr;
}
}class Solution {
vector<int> original, arr;
public:
Solution(vector<int>& nums) : original(nums), arr(nums) {}
vector<int> reset() { arr = original; return arr; }
vector<int> shuffle() {
for (int i = 0; i < (int)arr.size(); i++) {
int j = i + rand() % (arr.size() - i);
swap(arr[i], arr[j]);
}
return arr;
}
};Explanation
We need shuffle() to return a truly random ordering where every possible arrangement is equally likely. The clean way to do this is the Fisher–Yates shuffle.
We also keep a saved copy of the input in original so that reset() can restore the array to its starting order at any time.
The shuffle walks position i from the front to the back. At each step it picks a random index j somewhere between i and the end, then swaps arr[i] with arr[j]. Once a position is filled, it is never touched again.
Why is this fair? Each element has an equal chance of landing in each slot because the random pick for slot i chooses uniformly from all elements not yet placed. No value is favored.
Example: with [1,2,3,4,5], at i=0 we might pick j=2 and swap, giving [3,2,1,4,5]. We continue for i=1,2,3,4, each time choosing from the remaining tail, ending with a uniformly random permutation.