# 384. Shuffle an Array 打乱数组

@TOC

## # 题目描述

Shuffle a set of numbers without duplicates.

``````Example:

// Init an array with set 1, 2, and 3.
int[] nums = {1,2,3};
Solution solution = new Solution(nums);

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

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

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

## # 解题方法

### # 库函数

Python代码如下：

``````import random
class Solution(object):

def __init__(self, nums):
"""
:type nums: List[int]
"""
self.nums = nums

def reset(self):
"""
Resets the array to its original configuration and return it.
:rtype: List[int]
"""
return self.nums

def shuffle(self):
"""
Returns a random shuffling of the array.
:rtype: List[int]
"""
nums_s = self.nums[:]
random.shuffle(nums_s)
return nums_s

# Your Solution object will be instantiated and called as such:
# obj = Solution(nums)
# param_1 = obj.reset()
# param_2 = obj.shuffle()
``````

C++代码如下：

``````class Solution {
private:
vector<int> nums_;
vector<int> toshuffle_;
public:
Solution(vector<int> nums) {
nums_ = nums;
toshuffle_ = nums;
}

/** Resets the array to its original configuration and return it. */
vector<int> reset() {
toshuffle_ = nums_;
return nums_;
}

/** Returns a random shuffling of the array. */
vector<int> shuffle() {
random_shuffle(toshuffle_.begin(), toshuffle_.end());
}
};

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

### # Fisher–Yates 洗牌

Fisher–Yates shuffle 的原始版本，最初描述在 1938 年的 Ronald Fisher 和 Frank Yates 写的书中，书名为《Statistical tables for biological, agricultural and medical research》。他们使用纸和笔去描述了这个算法，并使用了一个随机数表来提供随机数。它给出了 1 到 N 的数字的的随机排列，具体步骤如下：

1. 写下从 1 到 N 的数字
2. 取一个从 1 到剩下的数字（包括这个数字）的随机数 k
3. 从低位开始，得到第 k个数字（这个数字还没有被取出），把它写在独立的一个列表的最后一位
4. 重复第 2步，直到所有的数字都被取出
5. 第 3 步写出的这个序列，现在就是原始数字的随机排列

``````import random
class Solution(object):

def __init__(self, nums):
"""
:type nums: List[int]
"""
self.nums = nums

def reset(self):
"""
Resets the array to its original configuration and return it.
:rtype: List[int]
"""
return self.nums

def shuffle(self):
"""
Returns a random shuffling of the array.
:rtype: List[int]
"""
nums_s = self.nums[:]
_len = len(self.nums)
for i in xrange(_len):
rand = random.randrange(i, _len)
nums_s[i], nums_s[rand] = nums_s[rand], nums_s[i]
return nums_s

# Your Solution object will be instantiated and called as such:
# obj = Solution(nums)
# param_1 = obj.reset()
# param_2 = obj.shuffle()
``````

### # 水塘抽样

1. 当K = 1时，数据流中第i个数被保留的概率为 1/i。只要采取这种策略，只需要遍历一遍数据流就可以得到采样值，并且保证所有数被选取的概率均为 1/N 。
2. 当K > 1时，对于前k个数，我们全部保留，对于第i（i>k）个数，我们以K/i的概率保留第i个数，并以 1/K的概率与前面已选择的k个数中的任意一个替换。

C++代码如下：

``````class Solution {
private:
vector<int> nums_;
public:
Solution(vector<int> nums) {
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_;
for (int i = 0; i < res.size(); ++i) {
int t = i + rand() % (res.size() - i);
swap(res[i], res[t]);
}
return res;
}
};

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

## # 日期

2018 年 2 月 27 日 2019 年 2 月 22 日 —— 这周结束了