RANDOMIZE-IN-PLACE随机排列算法

给定一个长度为 $n$ 的数组，如何构造出一个随机排列呢？《算法导论》给了我们一个名为RANDOMIZE-IN-PLACE的随机算法，该算法在数组原址上进行排序，时间复杂度为 $O (n)$ 。下面本文将介绍RANDOMIZE-IN-PLACE的设计思想及代码实现。

1. 背景知识

在介绍RANDOMIZE-IN-PLACE的设计思想之前，我们首先来了解一些背景知识，什么是随机算法，什么是随机排列数组，以及为什么要随机排列数组。

1.1 随机算法

如果一个算法的行为不只是由输入决定，同时也由随机数生成器所产生的数值决定，则称这个算法是随机的。

1.2 随机排列数组

随机排列数组的目标是产生一个均匀随机排列，使得 $n!$ 种排列中的每一种被取到的概率相等，等于 $\frac{1}{n!}$ 。

许多随机算法通过排列给定的输入数组使得输入随机化。

2. 随机排列数组的两种算法

PERMUTE-BY-SORTING和RANDOMIZE-IN-PLACE是实现随机排列数组的两种算法。

2.1 PERMUTE-BY-SORTING

设数组 $A = [1, 2, \dots, n]$ ，PERMUTE-BY-SORTING为其中的每个元素 $A [i]$ 赋一个随机数优先权 $P [i]$ ，然后根据这些优先权对数组 $A$ 进行排序。伪码如下：

PERMUTE-BY-SORTING(A)
n = length[A]
for(i=1; i<=n; i++)
	P[i] = RANDOM(1, n^3)
sort A, using P as sort keys
return A

在上述伪码中，使用 $1～n^3$ 间的 $n$ 个随机优先权的原因有两点：

能在 $O(n\log{n})$ 时间内排序完成。
以很高的概率使得 $n$ 个优先权都不相同。

2.2 RANDOMIZE-IN-PLACE

RANDOMIZE-IN-PLACE也称为Fisher-Yates Shuffle或Knuth Shuffle算法，与PERMUTE-BY-SORTING算法相比，它有三方面优势：

省去了排序的代价，时间复杂度为 $O (n)$ 。
随机数产生器所需范围更小（从 $1～n^3$ 降为 $1 ～ n$ ）。
不需要额外的辅助空间。

伪码如下：

RANDOMIZE-IN-PLACE(A, n)
for(i=1; i<=n; i++)
	swap(A[i], A[RANDOM(i, n)])

即在第 $i$ 次迭代时，从 $A [i \dots n]$ 随机选取元素与 $A [i]$ 交换位置；在第 $i$ 次迭代后， $A [i]$ 不再发生改变。

3. RANDOMIZE-IN-PLACE的正确性证明

下面我们来证明RANDOMIZE-IN-PLACE确实可以产生一个均匀随机排列。

证明：
循环不变式： 在for循环的第 $i$ 次迭代之前，对每个可能的 $(i - 1)$ -排列，子数组 $A [1 \dots i - 1]$ 包含这个 $(i - 1)$ -排列的概率为 $(n - i + 1)! / n!$ 。

初始化： 对 $i = 1$ ， $A [1 \dots 0]$ 包含某个0排列的概率为 $(n - i + 1)! / n! = 1$ ，其中 $A [1 \dots 0]$ ，0排列则是不包含任何元素的序列。

保持： 假设第 $i$ 次迭代前，任一可能的 $(i - 1)$ -排列出现在 $A [1 \dots i - 1]$ 中的概率为 $(n - i + 1)! / n!$ ，则需证明在第 $i$ 次迭代后，任一 $i$ -排列出现在 $A [1 \dots i]$ 中的概率为 $(n - i)! / n!$ 。

考虑一个特殊的 $i$ -排列 $R=[x_1, x_2, … , x_i]$ ，其中包含一个 $(i - 1)$ -排列 $x_1, x_2, … , x_{i-1}]$ ，算法在 $A [i]$ 放置 $x_i$ 。
令事件 $E_1$ 表示算法实际输出 $(i - 1)$ -排列 $R^{*}$ 为 $A [1 \dots i - 1]$ ，根据循环不变量， $Pr(E_1)=(n-i+1)!/n!$ 。
令事件 $E_2$ 表示第 $i$ 次迭代后输出 $A [i]$ 为 $x_i$ ，则当且仅当 $E_1$ 和 $E_2$ 同时发生时我们得到 $i$ -排列 $R$ 为 $A [1 \dots i]$ ，其概率 $Pr(E_2\cap{E_1})=Pr(E_2|E_1)·Pr(E_1)$ 。
- 给定 $E_1$ 的条件下， $A [i]$ 有 $(n - i + 1)$ 种取法，取到 $x_i$ 的概率为 $1/ (n - i + 1)$ ，即 $Pr(E_2|E_1) = 1/(n-i+1)$ 。
- 因此， $Pr(E_2\cap{E_1})=Pr(E_2|E_1)·Pr(E_1)=\frac{1}{n-i+1}·\frac{(n-i+1)!}{n!}=(n-i)! / n!$ 。

终止： 终止时， $i = n + 1$ ， $A [1 \dots n]$ 是一个给定 $n$ -排列的概率为 $(n - (n + 1) + 1)! / n! = 1/ n!$ 。

4. 代码

#include <stdio.h>
#include <stdlib.h>
#include <time.h>

#define N 10       //定义数组的长度为10 

void randomizeInPlace(int array[], int length) {  //对长度为length的数组array[]进行随机排列 
	int i;
	for (i = 0; i < length; i++) {
		int rnd = i + (rand() % (length - i));  //生成[i, length-1)范围内的一个随机下标 
		//交换 array[i]与array[rnd] 
		int temp = array[i];          
		array[i] = array[rnd];
		array[rnd] = temp;
	}	
}

int main() {
	srand(time(NULL));  //设置时间函数time(NULL)为随机数种子 
	int array[N];
	int i, j;
	for (i = 0; i < N; i++) {  //为原数组赋初值 
		array[i] = i + 1;
	}
	printf("原数组为：");      //打印输出原数组 
	for (i = 0; i < N; i++) {
		printf("%d ", array[i]);
	}
	printf("\n");
	int times;
	printf("请输入随机重排的次数：");
	scanf("%d", &times);       //用户指定随机重排的次数
	for (j = 0; j < times; j++) {
		randomizeInPlace(array, N);  //每次随机排列都是在上次随机排列的数组基础之上  
		printf("随机重排%d次的数组为：", j + 1); 
		for (i = 0; i < N; i++) {
			printf("%d ", array[i]);
		}
		printf("\n");
	}
	return 0;
}