随机排列生成算法的一些随想
这篇文章主要是一个闲文。如果您正在寻求一个理想的随机排列生成算法，直接阅读方法3。
另外请注意，这里所讨论的算法并不是新的。
什么是随机排列？
一个随机排列是一组位于随机位置的对象。
给定一个对象，1, 2, 3 ... n，随机排列看起来就是，
p1, p2, p3 ... pn
其中px是从原来的对象集合中选取的随机值。
随机排列对于扑克牌洗牌，随机产生益智游戏，产生随机序列，或者生成一个随机子集合集（从 n 个对象中随机选出 k 个对象），非常有用。
随机排列生成算法从天真到成熟，我的真实经验
为了解释算法，我会用一个辅助函数来产生随机数。
int random(int min, int max);
其结果是一个大于或等于 min 且小于 max 的一个随机数。
也就是说，结果是位于左闭右开区间内。
方法1，天真的方式
?
在随机位置交换两个元素。重复足够的次数。
伪代码：
array data(1..n);for(enough iterations) { swap(data[random(0, n)], data[random(0, n)]);}?
这种方法非常直观，很简单，它真的有效，前提是有足够的迭代，比如对10个元素迭代100次。没错，它真的可以工作，我用过很多次。
但最大的问题是，迭代次数要远远高于对象数（N），因为在两次中选择相同位置的两个元素的概率是相当大的，概率为1 /（n * n）相当的高。
因此，用这种方法，我们要么得到糟糕的性能（使用非常高的迭代），要么是比较差的随机性（低迭代）。
方法2，从篮子里取小球
?
假设所有的对象都是球。我们把所有的球到一个篮子，然后从篮子里随机拿出一个球，如是重复直到篮子变空。
伪代码：
array data(1..n);basket = new array;for(i = 0 to N - 1) { basket.push(data[i]);}for(i = 0 to N - 1) { int index = random(0, basket.length); data[i] = basket[index]; basket.remove(index);}?
这种方法也很直观，因为在现实中，彩票抽奖正是用这种方法，而且用的是真正的篮子和球。
而且这种方法性能很好，具有O（n）的时间复杂度。
理论上，其结果是能保证足够随机的，因为所有的球是从篮子里随机选择。
方法3，演进 - 在篮球里原地选择
?
第二种方法是很好的实现，而且很容易操作。但是，在计算机世界中，它有一个缺点：它需要一个额外的临时缓冲区来作为篮子。
在大多数情况下这没什么，不是个问题，但我们是否可以做得更好呢？
当然可以！我们可以在就在篮子里选择。
实际的 C++ 代码：
int random(int minValue, int maxValue){ assert(minValue <= maxValue); if(minValue != maxValue) { return rand() % (maxValue - minValue) + minValue; } else { return minValue; }} template <typename T>void randomPermutation(T & data, int count){ using std::swap; for(int i = 0; i < count; ++i) { swap(data[i], data[random(i, count)]); }}?
C 版本的非模板randomPermutation（用你需要的数据类型替换 "int" ，并自行实现 swap 函数）
void randomPermutation(int * data, int count){ for(int i = 0; i < count; ++i) { swap(&data[i], &data[random(i, count)]); }}?
上面的代码正是篮子方法的实现，不过比较隐晦。
了解原理
?
让我们假设篮子是有N个槽的长形篮子。则篮子是线性的。
那么初始篮子的样子，
1，2，3，4，5，6，...，N
现在假设我们随机选择5，那么篮子里的样子，
1，2，3，4，E，6，...，N
E表示空的槽。
接下来我们不删除E，我们把 5 之前的所有槽向后移动一个位置，并把 5 放在第一个槽里
5，1，2，3，4，6，...，N
下次如果我们选择3，我们只是移动 3 之前 5 之后的所有槽，然后把3个在那里，
5，3，1，2，4，6，...，N
重复N次
很好，是吗？我们不需要一个额外的缓冲区。但是，我们必须移动很多槽，不好玩。
如果第 C 次选择，我们只是把候选的元素与第 C 个元素交换，怎么样？
上面的迭代会进行以下变化，
1, 2, 3, 4, 5, 6, ..., N // 初始
5, 2, 3, 4, 1, 6, ..., N // 随机选择 5, 和 1 交换
5, 3, 2, 4, 1, 6, ..., N // 随机选择 3, 和 2 交换
这正是上面代码做的事情。
?
1 楼 bestchenwu 2011-05-26 好东西~