384. Shuffle an Array - cocoder39/coco39_LC GitHub Wiki

class Solution:

    def __init__(self, nums: List[int]):
        self.original = nums[:]
        
    def reset(self) -> List[int]:
        """
        Resets the array to its original configuration and return it.
        """
        return self.original
        
    def shuffle(self) -> List[int]:
        """
        Returns a random shuffling of the array.
        """
        n = len(self.original)
        res = self.original[:]
        for i in range(n):
            j = random.randrange(i, n)
            res[i], res[j] = res[j], res[i]
        return res

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

proof:
step 1: In case that ith element (includes last element) goes to last index, p = 1/n
step 2: In case that ith element goes to second last index, p = 1/n:
I ith element is the last element (index at n - 1)
  I.A move to any index j except staying at index n - 1: p = (n - 1)/n    
  I.B j is chosen again when shuffling element at index n - 2: p = 1 / (n - 1)
  I.C p = (n-1)/n * 1/(n-1) = 1/n
II 0 < i < n - 1, non-last element
  II.A not be chosen at shuffling last element, p = (n - 1) / n
  II.B be chosen at shuffling second last element, p = 1 / (n - 1)
  II.C p = (n-1)/n * 1/(n-1) = 1/n