# Shuffle an Array
**Difficulty:** MEDIUM
[External](https://leetcode.com/problems/shuffle-an-array)
Canonical: https://scaleengineer.com/dsa/problems/shuffle-an-array
**Patterns:** [Math](https://scaleengineer.com/dsa/patterns/math), [Design](https://scaleengineer.com/dsa/patterns/design), [Randomized](https://scaleengineer.com/dsa/patterns/randomized)
**Data structures:** Array
**Companies:** [J.P. Morgan](https://scaleengineer.com/companies/j.p.-morgan), [LinkedIn](https://scaleengineer.com/companies/linkedin), [Nvidia](https://scaleengineer.com/companies/nvidia)
---
## Problem
\[Fetch error\]

# Approaches
## Brute Force: Pre-computation of all Permutations
This approach involves generating every possible permutation of the input array beforehand. When a shuffle is requested, one of these pre-computed permutations is chosen at random.
**Time:** O(n * n!) for the one-time pre-computation to generate all permutations. Each subsequent call to `shuffle()` is O(1) (or O(n) to copy the array). The `reset()` is O(1) or O(n). The dominant factor is the pre-computation. · **Space:** O(n * n!) to store all `n!` permutations, each of length `n`. This is prohibitively large for most inputs.
**Pros:** Guarantees a uniform distribution if the random index is chosen uniformly.; Once pre-computation is done, subsequent shuffles are very fast.
**Cons:** Extremely high time complexity for pre-computation.; Extremely high space complexity.; Impractical for arrays with more than a few elements (e.g., n > 10).
### Explanation
In this method, we first generate all unique permutations of the original array. This is a one-time operation, typically done during the initialization of the object or on the first call to `shuffle()`. A standard backtracking algorithm can be used to generate these permutations.

Once we have a list containing all `n!` permutations, the `shuffle()` method becomes very simple: it just needs to pick a random index from this list and return the corresponding permutation. The `reset()` method simply returns the original, unmodified array.

While conceptually straightforward, this approach is highly impractical due to its factorial time and space complexity. It's only feasible for very small arrays.

```java
import java.util.ArrayList;
import java.util.List;
import java.util.Random;

class Solution {
    private int[] original;
    private List<int[]> allPermutations;
    private Random rand;

    public Solution(int[] nums) {
        this.original = nums.clone();
        this.rand = new Random();
        this.allPermutations = new ArrayList<>();
        // Pre-computation is too slow to do here, so we do it on the first shuffle call.
    }

    // Helper to generate all permutations using backtracking
    private void generatePermutations(List<Integer> current, boolean[] used, int[] nums) {
        if (current.size() == nums.length) {
            allPermutations.add(current.stream().mapToInt(i -> i).toArray());
            return;
        }
        for (int i = 0; i < nums.length; i++) {
            if (!used[i]) {
                used[i] = true;
                current.add(nums[i]);
                generatePermutations(current, used, nums);
                current.remove(current.size() - 1);
                used[i] = false;
            }
        }
    }

    public int[] reset() {
        return original;
    }

    public int[] shuffle() {
        if (allPermutations.isEmpty()) {
            // One-time expensive setup
            generatePermutations(new ArrayList<>(), new boolean[original.length], original);
        }
        int randomIndex = rand.nextInt(allPermutations.size());
        return allPermutations.get(randomIndex);
    }
}
```
### Algorithm
- 1. In the constructor, store a copy of the original array.
- 2. On the first call to `shuffle()`, generate all `n!` permutations of the array using a recursive backtracking algorithm and store them in a list.
- 3. For subsequent `shuffle()` calls, pick a random index from `0` to `n!-1` and return the permutation at that index.
- 4. The `reset()` method returns the stored original array.

## Brute Force: Sorting with Random Values
This approach shuffles the array by associating each element with a random number and then sorting the elements based on these random numbers. This effectively reorders the array in a random fashion.
**Time:** O(n log n) for each `shuffle()` call, dominated by the sorting step. · **Space:** O(n) to store the list of pairs and the resulting shuffled array.
**Pros:** Much more efficient than generating all permutations.; Relatively easy to implement.
**Cons:** Slower than the optimal Fisher-Yates shuffle.; May not produce a perfectly uniform distribution of permutations due to potential random number collisions and the behavior of the sorting algorithm on ties.
### Explanation
To shuffle the array, we first create a copy of the original array to avoid modifying it. Then, we create a list of pairs, where each pair consists of an element from the array and a randomly generated number that will act as its sorting key.

After populating this list, we sort it based on the random keys. The sorted list now has the original elements in a new, random order. We then extract these elements in their new order to form the shuffled array.

This method is much more efficient than generating all permutations. However, it has a potential flaw: if two elements are assigned the same random number (a collision), the sorting algorithm's behavior for ties (e.g., stable vs. unstable sort) can introduce bias, meaning not all permutations are equally likely. Using floating-point random numbers reduces the probability of collisions but doesn't eliminate it.

```java
import java.util.ArrayList;
import java.util.Collections;
import java.util.List;
import java.util.Random;

class Solution {
    // A simple Pair class for demonstration
    private static class Pair<K, V> {
        private K key;
        private V value;
        public Pair(K key, V value) { this.key = key; this.value = value; }
        public K getKey() { return key; }
        public V getValue() { return value; }
    }

    private int[] original;
    private Random rand;

    public Solution(int[] nums) {
        this.original = nums.clone();
        this.rand = new Random();
    }

    public int[] reset() {
        return original;
    }

    public int[] shuffle() {
        List<Pair<Integer, Integer>> pairedList = new ArrayList<>();
        for (int num : original) {
            pairedList.add(new Pair<>(num, rand.nextInt()));
        }

        // Sort the list based on the random keys
        Collections.sort(pairedList, (a, b) -> a.getValue().compareTo(b.getValue()));

        int[] shuffled = new int[original.length];
        for (int i = 0; i < original.length; i++) {
            shuffled[i] = pairedList.get(i).getKey();
        }
        return shuffled;
    }
}
```
### Algorithm
- 1. Store the original array.
- 2. In the `shuffle()` method, create a list of pairs.
- 3. Iterate through the original array. For each element, create a pair consisting of the element and a new random number, and add it to the list.
- 4. Sort the list of pairs based on the random numbers.
- 5. Create a new result array and populate it with the elements from the sorted list of pairs.
- 6. Return the result array.

## Fisher-Yates Shuffle (Optimal)
This is the canonical and most efficient algorithm for generating a random permutation of a finite sequence. It works by iterating through the array and, for each element, swapping it with another element chosen randomly from the part of the array that has not yet been shuffled.
**Time:** O(n) for each `shuffle()` call. The loop runs `n-1` times, and each operation inside (random number generation, swap) is O(1). `reset()` is O(n) to return a copy or O(1) to return a reference. · **Space:** O(n) to store the original array. The `shuffle()` method also uses O(n) auxiliary space to create a copy to shuffle, so the original array is preserved.
**Pros:** Optimal time complexity of O(n).; Guarantees a perfectly uniform random permutation.; Efficient in terms of space.; It is the standard, industry-accepted algorithm for this problem.
**Cons:** Slightly more complex to understand the proof of correctness compared to the sorting approach, but the implementation is simple.
### Explanation
The Fisher-Yates algorithm (also known as the Knuth shuffle) provides an unbiased permutation in linear time. The core idea is to shuffle the array in place.

We iterate through the array from the last element down to the second element. In each iteration `i`, we generate a random index `j` from `0` to `i` (inclusive). We then swap the element at the current index `i` with the element at the random index `j`. By doing this, the element that was originally at index `i` is now randomly placed somewhere in the prefix `0...i`, and an element from that prefix is moved to position `i`.

After the first step (for `i = n-1`), any of the `n` elements has a `1/n` chance of being in the last position. After the second step (for `i = n-2`), any of the remaining `n-1` elements has a `1/(n-1)` chance of being in the second-to-last position, and so on. This process guarantees that every permutation is equally likely.

For our implementation, we store the original array. The `shuffle` method first creates a copy of the original array and then applies the Fisher-Yates algorithm to this copy before returning it. This ensures the original array remains unchanged for future `reset` calls.

```java
import java.util.Random;

class Solution {
    private int[] original;
    private Random rand;

    public Solution(int[] nums) {
        this.original = nums.clone();
        this.rand = new Random();
    }

    /** Resets the array to its original configuration and return it. */
    public int[] reset() {
        return original;
    }

    /** Returns a random shuffling of the array. */
    public int[] shuffle() {
        int[] shuffled = original.clone(); // Always start with a fresh copy
        // Fisher-Yates shuffle algorithm
        for (int i = shuffled.length - 1; i > 0; i--) {
            // Pick a random index from 0 to i (inclusive)
            int j = rand.nextInt(i + 1);
            
            // Swap shuffled[i] with the element at random index j
            int temp = shuffled[i];
            shuffled[i] = shuffled[j];
            shuffled[j] = temp;
        }
        return shuffled;
    }
}
```
### Algorithm
- 1. Store the original array configuration.
- 2. For the `shuffle()` method, create a copy of the original array.
- 3. Iterate from the last index `n-1` down to `1`.
- 4. In each iteration `i`, generate a random index `j` in the range `[0, i]`.
- 5. Swap the elements at indices `i` and `j` in the copied array.
- 6. After the loop, return the shuffled copy.
- 7. The `reset()` method simply returns the original array.

# Solutions
### Java

```java
class Solution {
private
  int[] nums;
private
  int[] original;
private
  Random rand;
public
  Solution(int[] nums) {
    this.nums = nums;
    this.original = Arrays.copyOf(nums, nums.length);
    this.rand = new Random();
  }
public
  int[] reset() {
    nums = Arrays.copyOf(original, original.length);
    return nums;
  }
public
  int[] shuffle() {
    for (int i = 0; i < nums.length; ++i) {
      swap(i, i + rand.nextInt(nums.length - i));
    }
    return nums;
  }
private
  void swap(int i, int j) {
    int t = nums[i];
    nums[i] = nums[j];
    nums[j] = t;
  }
} /** * Your Solution object will be instantiated and called as such: * Solution
     obj = new Solution(nums); * int[] param_1 = obj.reset(); * int[] param_2 =
     obj.shuffle(); */

```

### JavaScript

```javascript
/** * @param {number[]} nums */ const Solution = function (nums) {
  this.nums = nums || [];
};
/** * Resets the array to its original configuration and return it. * @return {number[]} */ Solution.prototype.reset =
  function () {
    return this.nums;
  };
/** * Returns a random shuffling of the array. * @return {number[]} */ Solution.prototype.shuffle =
  function () {
    let a = this.nums.slice();
    for (let i = 0; i < a.length; i++) {
      let rand = Math.floor(Math.random() * (a.length - i)) + i;
      let tmp = a[i];
      a[i] = a[rand];
      a[rand] = tmp;
    }
    return a;
  }; /** * Your Solution object will be instantiated and called as such: * var obj = Object.create(Solution).createNew(nums) * var param_1 = obj.reset() * var param_2 = obj.shuffle() */

// lexicographical-numbers
/** * @param {number} n * @return {number[]} */ var lexicalOrder = function (
  n,
) {
  let ans = [];
  function dfs(u) {
    if (u > n) {
      return;
    }
    ans.push(u);
    for (let i = 0; i < 10; ++i) {
      dfs(u * 10 + i);
    }
  }
  for (let i = 1; i < 10; ++i) {
    dfs(i);
  }
  return ans;
};

```

### CPP

```cpp
class Solution {
public:
  vector<int> nums;
  vector<int> original;
  Solution(vector<int> &nums) {
    this->nums = nums;
    this->original.resize(nums.size());
    copy(nums.begin(), nums.end(), original.begin());
  }
  vector<int> reset() {
    copy(original.begin(), original.end(), nums.begin());
    return nums;
  }
  vector<int> shuffle() {
    for (int i = 0; i < nums.size(); ++i) {
      int j = i + rand() % (nums.size() - i);
      swap(nums[i], nums[j]);
    }
    return nums;
  }
}; /** * Your Solution object will be instantiated and called as such: *
      Solution* obj = new Solution(nums); * vector<int> param_1 = obj->reset();
      * vector<int> param_2 = obj->shuffle(); */

```

### Python

```python
class Solution:
    # Your Solution object will be instantiated and called as such: # obj = Solution(nums) # param_1 = obj.reset() # param_2 = obj.shuffle()
    def __init__(self, nums: List[int]): self . nums = nums self . original = nums . copy() def reset(self) -> List[int]: self . nums = self . original . copy() return self . nums def shuffle(self) -> List[int]: for i in range(len(self . nums)): j = random . randrange(i, len(self . nums)) self . nums[i], self . nums[j] = self . nums[j], self . nums[i] return self . nums

```