# [LeetCode 384. Shuffle an Array ](https://leetcode.com/explore/challenge/card/july-leetcoding-challenge-2021/610/week-3-july-15th-july-21st/3820/)
### Daily challenge Jul 20, 2021 (MEDIAN)

>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 array nums.
>* **`int[] reset()`** Resets the array to its original configuration and returns it.
>* **`int[] shuffle()`** Returns a random shuffling of the array.

:::info
**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]
:::

:::warning
**Constraints:**
* 1 <= nums.length <= 200
* -106 <= nums[i] <= 106
* All the elements of nums are **unique**.
* At most 5 * 104 calls **in total** will be made to reset and shuffle.
:::

---

### Approach 1 : Fisher-Yates Algorithm ( 洗牌演算法 ) :book:
**`96 ms ( 73.89% )`** **`O(N)`**

* **`最初`** 的演算法步驟 :
> 想把原始陣列 `nums`隨機排序
> 1. 生成 `0 ~ nums.size()` 之間的隨機數 `j`。
> 2. 將 `nums[j]` 放入新陣列的最後，並移除 `nums[j]`。
> 3. 重複 `第 1、2 步` 直到所有數字都被移除。
> 4. 最後得到的新陣列就是原始陣列的隨機排序。
>
> 因為去除 `nums` 的數值時，都需要移位，時間複雜度 **`O(N^2)`**。

* **`現代`** 演算法改進 :
> 利用 **`swap()`** 來達到重排的效果，時間複雜度 **`O(N)`**。
> * 原理與最初相同，可以分為兩種方式
> 1. **`i = 0 ~ (N-2)`** ( `nums[N-1]` 無須排列 ) ---> 生成 **`i ~ (N-1)`** 之間的隨機數。
>```cpp=21
> for(int i=0; i<size-1; i++){
> int j = rand() % (size - i);
> swap(current[i], current[i+j]);
> }
>```
> 2. **`i = (N-1) ~ 1`** ( `nums[0]` 無須排列 ) ---> 生成 **`0 ~ i`** 之間的隨機數。
>```cpp=29
> for(int i=size-1; i>0; i--){
> int j = rand() % (i+1);
> swap(current[i], current[j]);
> }
>```

class Solution {
public:
    vector<int> current;
    vector<int> original;
    
    Solution(vector<int>& nums) {
        srand(time(NULL));
        current = original = nums;
    }
    
    /** Resets the array to its original configuration and return it. */
    vector<int> reset() {
        current = original;
        return original;
    }
    
    /** Returns a random shuffling of the array. */
    vector<int> shuffle() {
        // version 1 //
        int size = current.size();
        for(int i=0; i<size-1; i++){
            int j = rand() % (size - i);
            swap(current[i], current[i+j]);
        }
        return current;
        
        // version 2
        /*
        for(int i=size-1; i>0; i--){
            int j = rand() % (i+1);
            swap(current[i], current[j]);
        }
        return current;
        */
    }
};

/**
 * 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();
 */