8 years ago
Share this article Reddit Twitter Facebook Google+

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

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

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

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

Add Comment

* Required information
1000000
Powered by Commentics

Comments (0)

No comments yet. Be the first!