Shuffle an Array

Problem Statement

In this problem, we are tasked with creating a Solution class that manages an array of integers and allows for two main operations: shuffling and resetting. The shuffle method should output a randomly shuffled version of the array where each permutation is equally likely, capturing the essence of true randomness without any bias towards particular arrangements. The reset method, on the other hand, should restore the array to its original order as it was upon initialization. These operations facilitate the ability to toggle back and forth between a fixed and a randomized sequence of the array elements.

Examples

Example 1

Input:

["Solution", "shuffle", "reset", "shuffle"]
[[[1, 2, 3]], [], [], []]

Output:

[null, [3, 1, 2], [1, 2, 3], [1, 3, 2]]

Explanation:

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

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

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

Constraints

• 1 <= nums.length <= 50
• -10^6 <= nums[i] <= 10^6
• All the elements of nums are unique.
• At most 10^4 calls in total will be made to reset and shuffle.

Approach and Intuition

Understanding the given example and the constraints outlined helps us establish an approach. Let's step through the logic:

1. Initialization:

   • When an instance is created, the original array is stored. This can be done by maintaining a private copy of the array that remains unaltered, serving as a reference for the reset operation.

2. Shuffle Algorithm:

   • To ensure each element has an equal probability of occupying any position in the array, we can employ the Fisher-Yates shuffle algorithm. This efficient technique works in an in-place manner by iterating through the array and swapping each element with another randomly chosen element that has not been locked into place yet. By methodically locking elements from one end of the array to another, this algorithm ensures a fair shuffle in O(n) time complexity.

3. Reset Operation:

   • The reset operation is straightforward, where the method simply returns a copy of the initially stored array, thus ensuring the array's original order is maintained and can be recalled after any number of shuffle operations.

4. Performance Considerations:

   • Given that the constraints allow for up to 10^4 calls in total to both reset and shuffle, the implementation of both methods must be efficient. Resetting is inherently quick since it involves returning a pre-stored value. The shuffle, using Fisher-Yates, ensures that we handle each element just once per shuffle call, thereby maintaining linear time complexity, which is ideal given the potential frequency of operations.

Understanding this setup and approach assures us that the system will operate efficiently under the constraints stipulated, providing robust and equitable shuffling while allowing for instant resets to the baseline order.

Solutions

class Solution {
    private int[] numsArray;
    private int[] initialArray;
    
    Random randomGenerator = new Random();
    
    private int generateRandom(int low, int high) {
        return randomGenerator.nextInt(high - low) + low;
    }
    
    private void exchangeIndices(int index1, int index2) {
        int temp = numsArray[index1];
        numsArray[index1] = numsArray[index2];
        numsArray[index2] = temp;
    }
    
    public Solution(int[] nums) {
        numsArray = nums;
        initialArray = nums.clone();
    }
        
    public int[] reset() {
        numsArray = initialArray;
        initialArray = initialArray.clone();
        return initialArray;
    }
        
    public int[] shuffle() {
        for (int i = 0; i < numsArray.length; i++) {
            exchangeIndices(i, generateRandom(i, numsArray.length));
        }
        return numsArray;
    }
}