# 384. 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();
# Solution
Approach 1: brute force.
Approach 2: Fisher-Yates algorithm -- for every index i from 0 to len - 1, randomly select an index j from i (inclusive, so that it can stay) to len - 1, and swap.
# Code (Python)
Approach 1:
class Solution:
def __init__(self, nums: List[int]):
self.nums = nums
self.original_nums = [_ for _ in nums]
def reset(self) -> List[int]:
"""
Resets the array to its original configuration and return it.
"""
self.nums = [_ for _ in self.original_nums]
return self.nums
def shuffle(self) -> List[int]:
"""
Returns a random shuffling of the array.
"""
nums = [_ for _ in self.nums]
self.nums = []
for i in range(len(nums)):
rand_index = random.randrange(len(nums))
self.nums.append(nums[rand_index])
nums.pop(rand_index)
return self.nums
Approach 2:
import random
class Solution:
# Fisher-Yates. Idea: for every index i from 0 to len - 1, randomly select an index j from i (inclusive, so that it can stay) to len - 1, and swap
def __init__(self, nums: List[int]):
self.nums = nums
self.original_nums = [_ for _ in nums]
def reset(self) -> List[int]:
"""
Resets the array to its original configuration and return it.
"""
self.nums = [_ for _ in self.original_nums]
return self.nums
def shuffle(self) -> List[int]:
"""
Returns a random shuffling of the array.
"""
for i in range(len(self.nums)):
j = random.randrange(i, len(self.nums)) # random.randrange doesn't include the second parameter
self.nums[i], self.nums[j] = self.nums[j], self.nums[i]
return self.nums
# Code (C++)
Approach 1:
Approach 2: