洗牌算法（Fisher-Yates Shuffle）

92 阅读 0 评论 61 点赞

我是靠谱客的博主孝顺外套，最近开发中收集的这篇文章主要介绍洗牌算法（Fisher-Yates Shuffle），觉得挺不错的，现在分享给大家，希望可以做个参考。

概述

1938年，Ronald Fisher 和 Frank Yates在《Statistical tables for biological》书中首次提出The Fisher–Yates shuffle。

1964年，Richard Durstenfeld 和 Donald E. Knuth在《The Art of Computer Programming》书中 "Algorithm P (Shuffling)"篇提出改进。

让我们看下他们的方案：

预想方案：反复从牌组中拉出一张随机牌并将其放在一边，逐步建立一个新筹码。只要您以相同的概率从牌组中挑选每张剩余的牌，当您完成时，您将获得完全无偏的随机堆栈（动画效果）。

实现：

但是，让我们说代替物理卡片组，你想编写代码来执行与n个元素的内存数组相同的任务。听起来很简单（部分），但你如何从原始套牌中挑选一个随机的剩余元素呢？

原始方案（慢）：从数组中选择一个随机元素（在[0，n - 1]中），然后检查你是否已经改组了那个元素。

创建两个数组，原始数组A存放按顺序排好的牌（" A[0]~A[53] "分别为 " 黑桃A~大王"），排序数组B暂时为空。
利用随机函数，产生0~53的整数，假设第一次产生了随机数3，而3对应数组A中的梅花A，于是梅花A存放到数组B首位。
不断循环，如果出现重复的随机数则抛弃。

这有效，但随着剩余元素的减少，它变得越来越慢; 你会随机选择已经洗过的元素。观察这些重复选择（红色）如何导致shuffle爬行停止：

改进方案：

不断剔除数组A中的元素

这很好用，但它仍然具有相对较差的二次性能。原因是，当您从原始数组（array.splice）中删除每个元素时，您必须将所有后续元素向下移动以压缩数组。平均而言，每个元素需要移动的O(n/2)，总复杂度为O（ $n^{2}$ ）。

仔细观察我们会发现：洗牌元素的数量（n - m）加上剩余元素的数量（m）总是等于n。这意味着我们可以在没有任何额外空间的情况下就地进行整个洗牌！我们使用数组的后面来存储混洗元素，并使用数组的前面来存储剩余的元素。只要我们在采摘时均匀采样，我们不关心剩余元素的顺序！

最终版本：

代码：

#include <algorithm>
#include <iostream>
#include <iterator>
#include <random>
#include <vector>

int main()
{
	// seed the RNG
	std::random_device rd;
	std::mt19937 mt(rd());

	std::vector<int> elements{ 1, 2, 3, 4, 5, 6, 7, 8, 9 };

	std::cout << "Before: ";
	std::copy(elements.cbegin(), elements.cend(),
		std::ostream_iterator<int>(std::cout, " "));

	//std::vector<int>::size_type currentIndexCounter = elements.size();
	auto currentIndexCounter = elements.size();

	//for (std::vector<int>::reverse_iterator iter = elements.rbegin(); iter != elements.rend();
	for (auto iter = elements.rbegin(); iter != elements.rend();
		++iter, --currentIndexCounter)
	{
		// get int distribution with new range
		std::uniform_int_distribution<> dis(0, currentIndexCounter);
		const int randomIndex = dis(mt);

		if (*iter != elements.at(randomIndex))
		{
			std::swap(elements.at(randomIndex), *iter);
		}
	}

	std::cout << "nAfter: ";
	std::copy(elements.cbegin(), elements.cend(),
		std::ostream_iterator<int>(std::cout, " "));

	return 0;
}