数据结构与算法寻法致用算法

随机算法总结

2016-04-22  本文已影响2595人  __七把刀__

随机算法涉及大量概率论知识，有时候难得去仔细看推导过程，当然能够完全了解推导的过程自然是有好处的，如果不了解推导过程，至少记住结论也是必要的。本文总结最常见的一些随机算法的题目，是几年前找工作的时候写的。需要说明的是，这里用到的随机函数都假定它能随机的产生范围[a,b]内的整数，即产生每个整数的概率相等。（虽然在实际中并不一定能实现，不过，谁在乎呢？这个世界都是这么随机）

1 随机排列数组

假设给定一个数组A，它包含元素1到N，我们的目标是构造这个数组的一个随机排列。

一个常用的方法是为数组每个元素A[i]赋一个随机的优先级P[i]，然后依据优先级对数组进行排序。比如我们的数组为A={1， 2， 3， 4}，如果选择的优先级数组为P={36， 3， 97， 19}，那么就可以得到数列B={2, 4, 1, 3}，因为3的优先级最高（为97），而2的优先级最低（为3）。这个算法需要产生优先级数组，还需使用优先级数组对原数组排序，这里就不详细描述了，还有一种更好的方法可以得到随机排列数组。

产生随机排列数组的一个更好的方法是原地排列给定数组（in-place），可以在O(N)的时间内完成。伪代码如下：

RANDOMIZE-IN-PLACE ( A , n ) for i ←1 to n do swap A[i] ↔ A[RANDOM(i , n )]

如代码中所示，第i次迭代时，元素A[i]是从元素A[i]到A[n]中随机选取的，在第i次迭代后，我们就再也不会改变A[i]。

A[i]位于任意位置j的概率为1/n。这个是很容易推导的，比如A[1]位于位置1的概率为1/n，这个显然，因为A[1]不被1到n的元素替换的概率为1/n，而后就不会再改变A[i]了。而A[1]位于位置2的概率也是1/n，因为A[1]要想位于位置2，则必须在第一次与A[k]交换(k=2...n)，同时第二次A[2]与A[k]替换，第一次与A[k]交换的概率为(n-1)/n，而第二次替换概率为1/(n-1)，所以总的概率是(n-1)/n * 1/(n-1) = 1/n。同理可以推导其他情况。

当然这个条件只能是随机排列数组的一个必要条件，也就是说，满足元素A[i]位于位置j的概率为1/n不一定就能说明这可以产生随机排列数组。因为它可能产生的排列数目少于n！，尽管概率相等，但是排列数目没有达到要求，算法导论上面有一个这样的反例。

算法RANDOMIZE-IN-PLACE可以产生均匀随机排列，它的证明过程如下：

考虑一个特殊的i排列p = {x1, x2, ... xi}，它由一个i-1排列p' =�{x1, x2,..., xi−1�}后面跟一个xi构成。设定两个事件变量E1和E2：

扩展

如果上面的随机排列算法写成下面这样，是否也能产生均匀随机排列？

PERMUTE-WITH-ALL( A , n ) for i ←1 to n do swap A[i] ↔A[RANDOM(1 , n )]

注意，该算法不能产生均匀随机排列。假定n=3，则该算法可以产生3*3*3=27个输出，而3个元素只有3!=6个不同的排列，要使得这些排列出现概率等于1/6，则必须使得每个排列出现次数m满足m/27=1/6，显然，没有这样的整数符合条件。而实际上各个排列出现的概率如下，如{1,2,3}出现的概率为4/27，不等于1/6。

2 随机选取一个数字

题目

给定一个未知长度的整数流，如何随机选取一个数？（所谓随机就是保证每个数被选取的概率相等）

解法1

如果数据流不是很长，可以存在数组中，然后再从数组中随机选取。当然题目说的是未知长度，所以如果长度很大不足以保存在内存中的话会很麻烦。这种解法有其局限性。

解法2

如果数据流在第1个数字后结束，那么必选第1个数字。
如果数据流在第2个数字后结束，那么我们选第2个数字的概率为1/2，我们以1/2的概率用第2个数字替换前面选的随机数，得到新的随机数。
.........
如果数据流在第n个数字后结束，那么我们选择第n个数字的概率为1/n，即我们以1/n的概率用第n个数字替换前面选的随机数，得到新的随机数。

一个简单的方法就是使用随机函数f(n)=bigrand()%n，其中bigrand()返回很大的随机整数，当数据流到第n个数时，如果f(n)==0，则替换前面的已经选的随机数，这样可以保证每个数字被选中的概率都是1/n。如当n=1时，则f(1)=0,则选择第1个数，当n=2时，则第2个数被选中的概率为1/2，以此类推，当数字长度为n时，第n个数字被选中的概率为1/n。

3 随机选取M个数字

题目

程序输入包含两个整数m和n，其中m<n，输出是0~n-1范围内的m个随机整数的有序列表，不允许重复。从概率角度来说，我们希望得到没有重复的有序选择，其中每个选择出现的概率相等。

解法1

先考虑个简单的例子，当m=2，n=5时，我们需要从0~4这5个整数中等概率的选取2个有序的整数，且不能重复。如果采用如下条件选取：bigrand() % 5 < 2，则我们选取0的概率为2/5。但是我们不能采取同样的概率来选取1，因为选取了0后，我们应该以1/4的概率来选取1，而在没有选取0的情况下，我们应该以2/4的概率选取1。选取的伪代码如下：

select = m
remaining = n
for i = [0, n)
    if (bigrand() % remaining < select)
         print i
         select--
    remaining--

只要满足条件m<=n，则程序输出m个有序整数，不多不少。不会多选，因为每选择一个数，select--，这样当select减到0后就不会再选了。同时，也不会少选，因为每次都会remaining--，当select/remaining=1时，一定会选取一个数。每个子集被选择的概率是相等的，比如这里5选2则共有C(5,2)=10个子集，如{0，1}，{0，2}...等，每个子集被选中的概率都是1/10。更一般的推导，n选m的子集数目一共有C(n,m)个，考虑一个特定的m序列，如0...m-1，则选取它的概率为m/n * (m-1)/(n-1)*....1/(n-m+1)=1/C(n,m)，可以看到概率是相等的。C++语言实现代码如下，该算法时间复杂度为O(n)。

void genknuth(int m, int n)
{
    for (int i=0; i<n; i++)
    if (bigrand() % (n-i) < m) {  //n-i中i每次加1，相当于remaining每次减1
      cout << i << endl;
      m--;  //选取的数目减1
    }
}

解法2

在初始为空的集合中插入随机整数，直到数目达到m。由于每次插入操作需要O(logm)的时间，遍历集合需要O(m)的时间，该算法总共需要O(mlogm)的实际。代码：

void gensets(int m, int n)
{
     set<int> S;
     while (S.size() < m)
          S.insert(bigrand() % n);
     set<int>::iterator it;
     for (it = S.begin(); it != S.end(); it++)
          cout << *it << endl;
}

解法3

采用前面随机排列数组的思想，先对前m个数字进行随机排列，然后排序这m个数字并输出即可。代码省略。

4 rand7()生成rand10()问题

请参见http://blog.csdn.net/sgbfblog/article/details/7753012

5 趣味概率题

1）生男生女问题：在重男轻女的国家里，男女的比例是多少？在一个重男轻女的国家里，每个家庭都想生男孩，如果他们生的孩子是女孩，就再生一个，直到生下的是男孩为止。这样的国家，男女比例会是多少？

2）约会问题：两人相约5点到6点在某地会面，先到者等20分钟后离去，求这两人能够会面的概率。

3）帽子问题：有n位顾客，他们每个人给餐厅的服务生一顶帽子，服务生以随机的顺序归还给顾客，请问拿到自己帽子的顾客的期望数是多少？

5）如果在高速公路上30分钟内看到一辆车开过的几率是0.95，那么在10分钟内看到一辆车开过的几率是多少？(假设常概率条件下)

参考资料

上一篇 下一篇

猜你喜欢

热点阅读