首页 > 代码库 > 数组的RandomShuffle算法

数组的RandomShuffle算法


试题:

random(a,b)是可以产生[a,b]之间一个随机整数的函数。请使用random(a,b)写一个算法将长度为n的整型数组随机打乱。

void random_shuffle(int a[], int n);

 

分析:

不考虑数组中元素是否重复,长度为n的数组,其全排列共有n!种。要做到概率上的随机打乱,打乱后的排列的概率需要是1/n!。

 

答案一、《算法导论》中的做法:

void random_shuffle(int a[], int n){    int temp_index, temp_val;    for (int i = 0; i < n; i++)    {        temp_index = random(i, n-1);        temp_val = a[temp_index];        a[temp_index] = a[i];        a[i] = temp_val;    }} 

 

证明:

(证明时,使用1-n的下标,注意与实现区分)。

使用如下的循环不等式:在for循环的第k次迭代之后,对每个可能的k排列,子数组a[1,k]包含这个k排列的概率是(n-k)!/n!

 初始:当k=1时,第一个元素的概率是1/n,而循环不等式(n-1)!/n!=1/n。循环不等式成立。

 保持:假设当k=i时,循环不等式也成立。则当k=i+1时,k排列的概率=(k-1)排列的概率 * 第k个元素的概率。

((n-i)!/n!) * (1/(n-i)) = (n-i-1)!/n! = (n-(i+1))!/n!

循环不等式成立。 

 终止:当k=n时,((n-(n-1))!/n!) * 1 = 1/n!

 由此证明算法random_shuffle产生的数组排列是均匀随机的。

更多内容可参考《算法导论》引理5.5

 

答案二: VC STL中algorithm的做法:

void random_shuffle(int a[], int n){    int temp_index, temp_val;    // 注意这里i是从1开始,i=0时不需要交换    for (int i = 1; i < n; i++)    {        temp_index = random(0, i);        temp_val = a[temp_index];        a[temp_index] = a[i];        a[i] = temp_val;    }}

 

证明:

(证明时,使用1-n的下标,注意与实现区分)。

使用如下的循环不等式:在for循环的第k次迭代之后,对每个可能的k排列,子数组a[1,k]包含这个k排列的概率是1/k!

 初始:当k=2时,第一个元素的概率是1/2,而循环不等式1/k!=1/2。循环不等式成立。

 保持:假设当k=i时,循环不等式也成立。则当k=i+1时,k排列的概率=(k-1)排列的概率 * 第k个元素的概率。

(1/i!) * (1/(i+1)) = 1/(i+1)!

循环不等式成立。

 终止:当k=n时,(1/(n-1)!) * (1/n) = 1/n!

 由此证明算法random_shuffle产生的数组排列是均匀随机的。

 

小结:

《算法导论》是本很经典的书,给出了均匀排列的证明。而vc的stl算法给出了另外一种实现。对比之下,stl的算法更工程一些,因为i是1开始,而不是从0开始,当i=0时,random(0,0)还是自己,不需要交换,stl直接省却了这一步。同样《算法导论》的实现,for循环中的i<n,也可以改为i<n-1。