Description
Given an integer array nums, design an algorithm to randomly shuffle the array. All permutations of the array should be equally likely as a result of the shuffling.
Implement the Solution class:
Solution(int[] nums)Initializes the object with the integer arraynums.int[] reset()Resets the array to its original configuration and returns it.int[] shuffle()Returns a random shuffling of the array.
Examples:
Example 1:
Input
["Solution", "shuffle", "reset", "shuffle"]
[[[1, 2, 3]], [], [], []]
Output
[null, [3, 1, 2], [1, 2, 3], [1, 3, 2]]Solution in Python
To design this algorithm in Python, we’ll create a Solution class that manages the original array and provides methods to reset and shuffle it. To ensure all permutations are equally likely during shuffling, we’ll use the Fisher-Yates shuffle algorithm (also known as the Knuth shuffle), which is efficient and unbiased.
Key Concepts
- Fisher-Yates Shuffle: This algorithm generates a random permutation of an array in place, with a time complexity of O(n).
- The algorithm works by iterating through the array from the end to the beginning, and for each position iii, swapping the element at iii with a random element from index 0 to i.
- This ensures that each element has an equal probability of ending up in any position.
- Reset Function: The reset function simply returns the array to its original configuration, which can be achieved by storing a copy of the original array.
Python
class Solution:
def __init__(self, nums: List[int]):
# Store the original array to reset it later
self.original = nums[:]
# Create a working copy of the array for shuffling
self.array = nums[:]
def reset(self) -> List[int]:
# Reset the array to the original configuration
self.array = self.original[:]
return self.array
def shuffle(self) -> List[int]:
# Implement the Fisher-Yates shuffle algorithm
for i in range(len(self.array) - 1, 0, -1):
# Pick a random index from 0 to i
j = random.randint(0, i)
# Swap elements at indices i and j
self.array[i], self.array[j] = self.array[j], self.array[i]
return self.arrayExplanation of the Code
__init__Constructor:- Takes an integer array
numsand initializes two copies:self.original: A copy ofnumsthat holds the original configuration.self.array: A mutable copy that will be used for shuffling.
- Takes an integer array
resetMethod:- Resets
self.arraytoself.originalby creating a fresh copy. - Returns the array in its original order.
- Resets
shuffleMethod:- Uses the Fisher-Yates shuffle to rearrange
self.arrayin a random order. - For each index
ifrom the end of the array to the start, a random indexjbetween0andiis chosen. - The elements at indices
iandjare swapped, creating a uniform random permutation. - Returns the shuffled array.
- Uses the Fisher-Yates shuffle to rearrange
Solution in C++
C++
class Solution {
private:
std::vector<int> original; // Stores the original configuration of the array
std::vector<int> shuffled; // Stores the current shuffled state of the array
public:
// Constructor initializes the Solution object with a given integer array nums
Solution(std::vector<int>& nums) : original(nums), shuffled(nums) {}
// Resets the array to its original configuration and returns it
std::vector<int> reset() {
shuffled = original; // Copy the original array back to shuffled
return shuffled;
}
// Returns a random shuffling of the array
std::vector<int> shuffle() {
// Use the Fisher-Yates shuffle algorithm
int n = shuffled.size();
for (int i = n - 1; i > 0; --i) {
// Generate a random index from 0 to i
int j = rand() % (i + 1);
// Swap shuffled[i] with shuffled[j]
std::swap(shuffled[i], shuffled[j]);
}
return shuffled;
}
};Solution in Javascript
JavaScript
var Solution = function(nums) {
// Store the original array to reset it later
this.original = nums;
// Make a copy of the array for shuffling purposes
this.shuffled = nums.slice();
};
/**
* Resets the array to its original configuration and returns it.
* @return {number[]} - The original array.
*/
Solution.prototype.reset = function() {
// Reset shuffled array to its original form and return it
this.shuffled = this.original.slice();
return this.shuffled;
};
/**
* Returns a random shuffling of the array.
* @return {number[]} - A randomly shuffled array.
*/
Solution.prototype.shuffle = function() {
// Iterate over the array, swapping each element with another random element
for (let i = 0; i < this.shuffled.length; i++) {
// Generate a random index from the current index to the end of the array
const randomIndex = Math.floor(Math.random() * (this.shuffled.length - i)) + i;
// Swap the current element with the randomly chosen element
[this.shuffled[i], this.shuffled[randomIndex]] = [this.shuffled[randomIndex], this.shuffled[i]];
}
return this.shuffled;
};Solution in Java
Java
class Solution {
private int[] original; // Stores the original array to reset later
private int[] array; // Working array that we will shuffle
private Random rand; // Random number generator for shuffling
// Constructor that initializes the object with the integer array nums
public Solution(int[] nums) {
this.original = nums.clone(); // Store a copy of the original array
this.array = nums.clone(); // Initialize the working array
this.rand = new Random(); // Initialize the random number generator
}
// Resets the array to its original configuration and returns it
public int[] reset() {
array = original.clone(); // Reset the working array to the original configuration
return array;
}
// Returns a random shuffling of the array
public int[] shuffle() {
// Loop through each element of the array
for (int i = 0; i < array.length; i++) {
// Generate a random index between i and the end of the array
int j = i + rand.nextInt(array.length - i);
// Swap elements at indices i and j
int temp = array[i];
array[i] = array[j];
array[j] = temp;
}
return array;
}
}