Knuth-Shuffle算法

发表于 更新于 分类于 阅读次数： Valine：
本文字数： 1.1k 阅读时长 ≈ 1 分钟

问题描述：现在有\(n\)个元素存放在一个数组里，给出一种算法能够生成它们的一个排列，使得生成每种排列的概率相等。

主要参考：《数据结构与算法分析——C语言描述》 Mark Allen Weiss

Knuth-Shuffle算法

不失一般性，可以记这n个元素就是整数1到n，存放在数组\(A[0...n-1]\)里。并且假设计算模型里有取随机数的基本操作：

1
2
// 能够以相等概率随机返回一个范围在[i,j]的整数
int randint(int i, int j);

这里直接给出算法的伪代码：

1
2
3
4
5
void Knuth_Shuffle(int A[], int n)
{
    for(int i = n - 1; i >= 0; i--)
        swap(&A[i], &A[randint(0,i)]);
}

不难分析得到这个算法的时间复杂度是\(O(n)\)，空间复杂度如果不计原本的数组则是\(O(1)\)的。

算法正确性的证明

首先这个算法涉及的操作就是对\(A[0...n-1]\)里的元素进行swap()，最后得到的当然是这n个元素的一个排列。

记任意一个排列为\(a_0,a_1,...a_{n-1}\)，为了得到这个排列，算法必须第一步用元素\(A[n-1]\)和元素\(a_{n-1}\)交换，实现这一步的概率显然是\(\frac{1}{n}\)；第二步必须用元素\(a_{n-2}\)和元素\(A[n-2]\)交换，而这一步实际上是一个条件概率\(\frac{1}{n-1}\)；以此类推，第k步必须用元素\(a_{n-k}\)和元素\(A[n-k]\)交换。

设事件\(E_k\)为算法的第k次迭代时用元素\(a_{n-k}\)和元素\(A[n-k]\)交换，则生成排列\(a_0,a_1,...a_{n-1}\)就是事件\(\prod_{k=0}^{n-1} E_k\)。展开一下就有

\[ P\{\prod_{k=0}^{n-1} E_k\} = P\{E_k\}P\{E_{k-1}|E_{k}\}...P\{E_{0}|E_{k}E_{k-1}...E_{1}\} \] 根据上面的分析不难发现这个结果就是\(\frac{1}{n!}\)，所以每种排列生成的概率是一样的。

其他

在《数据结构与算法分析——C语言描述》中译本P27给出的算法其实是

1
2
3
4
5
void Knuth_Shuffle(int A[], int n)
{
    for(int i = 1; i < n; i++)
    swap(&A[i], &A[randint(0,i)]);
}

和最开头给出的有一点点区别，但不难证明结论是一样的。

(Hint:从最后一次迭代往前分析即可)

相关文章