《大学算法教程Algorithms》笔记--Chapter1--Part2

书中提到一个打乱数组的算法:

下面假设传入的数组满足 a[i]=i

伪代码如下:

shuffle(a)
{
     for i=1 to a.last-1
            swap( a[i], a[rand(i,a.last)] )
}

这个算法的巧妙之处在于它可以实现所有可能的排列.

所以第i个元素,必须与第i个到数组结尾的所有元素随机交换, 必须包括i本身才能实现所有可能的排列

数学上来说就是 n*(n-1)*......*2种可能的交换,这实际上就是n!,也就对应着n个元素的所有排列的可能性

(注意,保持数组不变,也就是不交换任何元素的可能性也包含在其中)

如果rand的随机性足够好,这也就会等概率的产生所有1到n的排列.

这也算是习题1.2的一个证明吧.

另外,习题1.3中所算法改成

new_shuffle(a)
{
     for i=1 to a.last
            swap( a[i], a[rand(1,a.last)] )
}

新的算法会让每个元素和所有元素随机交换,这应该有n^n种可能性,若想等概率的产生所有的n!种排列,这个数字应该是n!的整数倍,这是不可能的.

因为,若n是偶数,则n-1是奇数,n^n无法被n!整除,若n是奇数,也得出同样的结论

所以新的算法无法等概率的产生1到n的所有排列.

所以,现在可以写一个简单的算法,来随机产生n个数的一个排列

random_permutation(n,a)
{    
      for i = 1 to n
            a[i] = i
      for i = 1 to n-1
            swap( a[i], a[rand(i,n)] )
}