随机排列生成算法的一些随想

本文主要讨论一些随机排列生成算法。从普通算法之道推演出实用的算法。

这篇文章主要是一个闲文。如果您正在寻求一个理想的随机排列生成算法，直接阅读方法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 交换

这正是上面代码做的事情。