[Algorithm]Fisher-Yates shuffle

如何shuffle一组给定的数据，让每一个数据在每一个位置出现的概率是等概率的。Fisher-Yates shuffle可以帮助我们做到这一点，假设输入为N组数据，其具体步骤为：

• 从下标N - 1到0，对于下标为i的数据，我们生成一个random的数字r，0 <= r <= i，交换下标为r和i的数据

分析，对于下标为i的数据，其出现在下标为m的位置的情况，有以下三种可能：

• m > i，那么下标为i的数据最终出现在位置m的概率是：下标为i的数据在之前没有被换走的概率 * 在遍历到m的时候m和i交换的概率 = ((n - 1) / n) * ((n - 2) / (n - 1)) * ... * ((m + 1) / (m + 2)) * (1 / (m + 1)) = 1 / n
• m == i，那么下标为i的数据最终留在原来位置的概率为：下标为i的数据在之前没有被换走的概率 * 在遍历到i的时候和自身交换的概率 = ((n - 1) / n) * ((n - 2) / (n - 1)) * ... * ((i  +1) / (i + 2)) * (1 / (i + 1)) = 1 / n
• m < i，那么下标为i的数据最终出现在位置m的概率是：下标为i的数据在遍历到i之前没有被换走的概率 * 下标为i的数据在遍历到i的时候被换走的概率(此时数据i已经被换走但其还没有确定最后的位置，其下边在[0, i - 1]的范围中) * 在遍历到(m, i)的下标时不换到原来在位置i的数据的概率 * 在遍历到m的时候换到原来在位置i的数据的概率 = ((n - 1) / n) * ((n - 2) / (n - 1)) * ... ((i + 1) / (i + 2)) * (i / (i + 1)) * ((i - 1) / i) * ... *  ((m + 1) / (m + 2)) * (1 / (m + 1)) = 1 / n

代码如下：

	void shuffle(vector<int>& nums) {
	int n = nums.size();
	for(int i = n - 1; i >= 1; --i)
	{
	int random = rand() % (i + 1);
	swap(nums[random], nums[i]);
	}
	}

view raw fisher_yates_shuffle.cxx hosted with ❤ by GitHub