Fisher-Yates 算法

本文介绍原地均匀随机生成排列的 Fisher-Yates 算法。

基础定义

首先定义一下阶乘。

阶乘: 给定非负整数 $n$，其阶乘通过如下方式递归定义： $$ \begin{aligned} n! &= n \times (n - 1) \times \dots \times 1\\ &= \begin{cases} n \times (n - 1)! & n \ge 1 \\ 1 & n = 0 \end{cases} \end{aligned} $$

下面定义一下排列。

排列: 给定正整数 $n$，则称映射 $p\colon \{0, 1, \dots, n-1\} \to \{0, 1, \dots, n-1\}$ 是一个$n$ 元排列，当且仅当 $p$ 是双射。换言之，不存在 $i \neq j$ 使得 $p(i) = p(j)$。

全体 $n$ 元排列构成的集合记为 $S_n$，那么由组合数学的经典结论，有 $|S_n| = n!$。

算法流程

Fisher-Yates 算法的核心是建立 $\{0\} \times \{0, 1\} \times \dots \times \{0, 1, \dots, n-1\}$ 和 $S_n$ 之间的一一对应关系，而后者的均匀分布是平凡的且易于生成：

template<class OutIt, class URNG>
void generate_indices_n(OutIt ind_array, size_t n, URNG &&rng) {
	for(size_t i = 0; i < n; ++i) {
		ind_array[i] = rng() % (i + 1);
	}
}

下面只用考虑怎么基于此数组生成排列。

可行的实现方式显然不是唯一的，但是 Fisher-Yates 算法的精妙之处在于：它只用常数极小的 $O(n)$ 时间和 $O(1)$ 的额外空间就足以实现。直接用代码展示更直观：

#include<algorithm>
template<class RanIt, class URNG>
void my_shuffle_n(RanIt perm, size_t n, URNG &&rng) {
	for(size_t i = 0; i < n; ++i) {
		std::swap(perm[i], perm[rng() % (i + 1)]);
	}
}

如上代码的正确性可以用归纳法简单证明：

如果 $n \le 1$，显然此时的 $n$ 元排列是均匀随机的（因为只有一种可能）。
如果 $n \ge 2$，在假设前 $n - 1$ 个数组成的排列是均匀随机生成的前提下，将第 $n$ 个数等概率地与前 $n$ 个数（包括自己）中的一个交换，能够生成所有的 $n$ 元排列且概率完全相等。

扩展应用

如果要从 $W$ 个数中选取 $n$ 个排成一列，而 $n$ 比较小但 $W$ 特别大时，直接用 Fisher-Yates 算法没有那么多空间存下 $W$ 个数再选取。此时可以适当改造一下避免存取太多的元素。

首先需要一个记录排列的类：

#include<unordered_map>
using u64 = unsigned long long;

struct Perm {
	std::unordered_map<u64, u64> perm;

	u64& operator[](u64 x) {
		// use perm.find(x) != perm.end() instead of perm.contains(x) before C++20
		return perm.contains(x)
			? perm[x]
			: (perm[x] = x); 
	}
};

核心之处在于，只有在需要取用对应元素时才去建立对应的节点。此做法可以大幅压缩空间。

仿照 Fisher-Yates 算法，但是此时选择与后面的元素交换：

#include<algorithm>
template<class RanIt, class URNG>
void my_shuffle_n(RanIt dest, size_t n, u64 W, URNG &&rng) {
	Perm perm;
	for(size_t i = 0; i < n; ++i) {
		std::swap(perm[i], perm[rng() % (W - i)]);
		dest[i] = perm[i];
	}
}

此做法最多生成 $2n$ 个节点，即可从 $W$ 个元素中取出 $n$ 个排成一列。

基础定义

算法流程

扩展应用

Email