1. 简述
本文主要是关于均匀随机排列数组的一个学习总结，主要参考资料是算法导论。
2. 相关题目
据说腾讯一个题目：对于一个斗地主游戏，给出一个发牌的算法，让每个人的牌确保随机。
分析：考虑假设有N张牌，要分出来M张牌，给K个人。我能想到的是，N张牌有N种排列，随机产生一种排列，将产生排列的前M张牌依次分给K个人。使用均匀随机排列算法，能够保证：对于N张牌的N！种排列，且得到的任意一种排列的概率都是相同的，即都为1/(N!)。
3. 判定方法
对于一个算法能否保证均匀随机排列数组，主要考查两点：
· 产生的排列个数是N！个
· 每种排列的概率相同，即都为1/N!
4. 两个算法
·方法一：首先，得到一个优先级数组P，然后根据优先级数组P来排序原数组A。关键在于优先级数组P，要保证能够得到n!种排列，且每种排列的概率相等。
n <- length[A]
for i <- 1 to n // 产生优先级
do P[i] = RANDOM(1, n*n*n)
sort A, using P as sort keys // 根据优先级排序
return A
RANDOM中使用n的立方是为了使得产生的优先级尽量是唯一的，因此对这个方法的证明的前提是分配的优先级是唯一的。
考虑优先级数组正好是升序的这一个特殊序列，概率为(1/n) * (1/(n-1)) * ... * (1/1) = 1 / (n!)
对于优先级数组的其他情况，也能得到类似结果（具体看算法导论）。
因此一共能得到n!个序列，每个序列的概率都是相同的，满足判定方法。
·方法二：第一次交换A1与Rand(1,n)，第二次交换A2与Rand(2,n),...,第n次交换An与Rand(n,n)
n <- length(A)
for i<- 1 to n
do swap A[i]<->A[RANDOM(i,n)]
概率分析忽略了，说实话证明较为复杂，先不看了，下次再说了。
方法一的时间复杂度为O(N+N*LogN)，方法二的时间复杂度为O(N)。
5. 一个反例
n-<length[A]
for i<- 1 to n-1
do swap A[i] <-> A[RANDOM(i+1, n)]
感觉上对于升序的概率是：1/(n-1) * 1/(n-2) * ... * 1 = 1 / (n-1)！每个排序的概率都一样，那么也就是只有(n-1)！种排列。其实对于A[i]交换的元素下标是在[i+1, n]这个范围内，即每个元素肯定是与后面的元素交换，不会与自己交换，所以对于A1肯定越交换越往后，无论多少次随机都不会被换到原来的位置了，因此不能保证n!中排列，不是均匀随机排列。
6. 参考
算法导论，第二版，5.3节，随机算法，Page58
腾讯大厦面试经历 http://www.iweber.org/weber/?tag=%e8%85%be%e8%ae%af