384. Shuffle an Array

The idea is, first of all, we draw a number out of the array, the probability for this number is 1/n, then the rest numbers have probability of (n-1)/n. Then we draw another number out of the rest n-1 numbers, so its probability is (n-1)/n * 1/(n-1) = 1/n. And we repeat this procedure until all the numbers have been drawn.

1:  class Solution {  
2:  private:  
3:    vector<int> nums;  
4:  public:  
5:    Solution(vector<int> nums) {  
6:      this->nums = nums;  
7:    }  
8:    /** Resets the array to its original configuration and return it. */  
9:    vector<int> reset() {  
10:      return nums;  
11:    }  
12:    /** Returns a random shuffling of the array. */  
13:    vector<int> shuffle() {  
14:      vector<int> res = nums;  
15:      int size = nums.size();  
16:      int i = 0;  
17:      while (size) {  
18:        int j = rand() % size;  
19:        swap(res[i], res[i+j]);  
20:        i++, size--;  
21:      }  
22:      return res;  
23:    }  
24:  };  
25:  /**  
26:   * Your Solution object will be instantiated and called as such:  
27:   * Solution obj = new Solution(nums);  
28:   * vector<int> param_1 = obj.reset();  
29:   * vector<int> param_2 = obj.shuffle();  
30:   */