|
http://www.searchtb.com/2010/12/random-algorithm.html
void SelectMNumberFromN(int arr[], int n, int m)
{
for (int i = 0; i < n && m; ++i)
{
// p(i) < m / (n - i)
if (rand() % (n - i) < m)
{
cout << arr[i] << endl;
--m;
}
}
}
// 这个可能比较好理解
void SelectMNumberFromN(int arr[], int n, int m)
{
// 余下的数
int remainN = n;
// 剩余的要选择的个数
int remainM = m;
for (int i = 0; i < n && remainM; ++i)
{
// p(i) < remainM / remainN
if (rand() % remainN < remainM)
{
cout << arr[i] << endl;
--remainM;
}
--remainN;
}
}
void SelectMNumberUnknownN(Iterator itr, int m, int arr)
{
int count = 0;
while (itr.hasNext())
{
int value = itr.getNext();
++count;
if (count <= m)
{
arr[count - 1] = value;
}
else
{
// p(i) < m/count or p(i) % count < m
int num = rand() % count;
if (num < m)
{
arr[num] = value;
}
}
}
}
在日常工作中，经常需要使用随机算法。比如面对大量的数据， 需要从其中随机选取一些数据来做分析。 又如在得到某个分数后， 为了增加随机性， 需要在该分数的基础上， 添加一个扰动， 并使该扰动服从特定的概率分布。本文主要从这两个方面出发， 介绍一些算法， 供大家参考。
首先假设我们有一个使用的随机函数float frand()， 返回值在(0, 1)上均匀分布。大多数的程序语言库提供这样的函数。 在其他的语言如C/C++中， 可以通过间接方法得到。如 frand()= ((float)rand() ) / RAND_MAX;
1, 随机选取数据
假设我们有一个集合A(a_1,…,a_n), 对于数m，0≤m≤n, 如何从集合A中等概率地选取m个元素呢？
通过计算古典概率公式可以得到， 每个元素被选取的概率为m/n。 如果集合A里面的元素本来就具有随机性， 每个元素在各个位置上出现的概率相等， 并且只在A上选取一次数据，那么直接返回A的前面m个元素就可以了， 或者可以采取每隔k个元素取一个等类似的方法。这样的算法局限很大， 对集合A的要求很高， 因此下面介绍两种其他的算法。
1.1 假设集合A中的元素在各个位置上不具有随机性， 比如已经按某种方式排序了，那么我们可以遍历集合A中的每一个元素a_i, 0<=n 根据一定的概率选取ai。如何选择这个概率呢？
设m’为还需要从A中选取的元素个数， n’为元素a_i及其右边的元素个数， 也即n’=(n-i+1)。那么选取元素a_i的概率为 m’/n’。
由于该算法的证明比较繁琐， 这里就不再证明。
我们简单计算一下前面两个元素(2<=m<=n)各被选中的概率。
1) 设p(a_i=1)表示a_i被选中的概率。显而易见， p(a_1=1)=m/n, p(a_1=0)为(n-m)/n;
2)第二个元素被选中的概率为
p(a_2=1)= p(a_2=1,a_1=1)+p(a_2=1,a_1=0)
= p(a_1=1)*p(a_2=1│a_1=1)+ p(a_1=0)* p(a_2=1│a_1=0)
= m/n * (m-1)/(n-1) + (n-m)/n*m/(n-1)
= m/n
我们用c++语言， 实现了上述算法
template<class T>
bool getRand(const vector<T> vecData, int m, vector<T>& vecRand)
{
int32_t nSize = vecData.size();
if(nSize < m || m < 0)
return false;
vecRand.clear();
vecRand.reserve(m);
for(int32_t i = 0, isize = nSize; i < isize ; i++){
float fRand = frand();
if(fRand <=(float)(m)/nSize){
vecRand.push_back(vecData[i]);
m--;
}
nSize --;
}
return true;
}
利用上述算法， 在m=4， n=10， 选取100w次的情况下， 统计了每个位置的数被选取的概率
| 位置 | 概率 | | 1 | 0.399912 | | 2 | 0.400493 | | 3 | 0.401032 | | 4 | 0.399447 | | 5 | 0.399596 | | 6 | 0.39975 | | 7 | 0.4 | | 8 | 0.399221 | | 9 | 0.400353 | | 10 | 0.400196 |
还有很多其他算法可以实现这个功能。比如对第i个数， 随机的从a_i, …, a_n中， 取一个数和a_i交换。这样就不单独介绍了。
1.2 在有些情况下，我们不能直接得到A的元素个数。比如我们需要从一个很大的数据文件中随机选取几条数据出来。在内存不充足的情况下，为了知道我们文件中数据的个数， 我们需要先遍历整个文件，然后再遍历一次文件利用上述的算法随机的选取m个元素。
又或者在类似hadoop的reduce方法中， 我们只能得到数据的迭代器。我们不能多次遍历集合， 只能将元素存放在内存中。 在这些情况下， 如果数据文件很大， 那么算法的速度会受到很大的影响， 而且对reduce机器的配置也有依赖。
这个时候，我们可以尝试一种只遍历一次集合的算法。
1) 取前m个元素放在集合A’中。
2) 对于第i个元素(i>m), 使i在 m/i的概率下， 等概率随机替换A’中的任意一个元素。直到遍历完集合。
3) 返回A’
下面证明在该算法中，每一个元素被选择的概率为m/n.
1) 当遍历到到m+1个元素时， 该元素被保存在A’中的概率为 m/(m+1), 前面m个元素被保存在A’中的概率为 1- (m/m+1 * 1/m) = m/m+1
2) 当遍历到第i个元素时，设前面i-1个元素被保存在A’中的概率为 m/(i-1)。根据算法， 第i个元素被保存在A’中的概率为m/i , 前面i-1各个元素留在A’中的概率为 m/(i-1) * (1-(m/i* 1/m) = m/i;
3) 通过归纳，即可得到每个元素留在A’中的概率为 m/n;
我们在类似 hadoop的reduce函数中， 用java实现该算法。
public void reduce(TextPair key, Iterator value, OutputCollector collector, int m)
{
Text[] vecData = new Text[m];
int nCurrentIndex = 0;
while(value.hasNext()){
Text tValue = value.next();
if(nCurrentIndex < m){
vecData[nCurrentIndex] = tValue;
}
else if(frand() < (float)m / (nCurrentIndex+1)) {
int nReplaceIndex = (int)(frand() * m);
vecData[nReplaceIndex] = tValue;
}
nCurrentIndex ++;
}
//collect data
…….
}
利用上述算法，在m=4， n=10， 经过100w次选取之后， 计算了每个位置被选择的选择的概率
| 位置 | 概率 | | 1 | 0.400387 | | 2 | 0.400161 | | 3 | 0.399605 | | 4 | 0.399716 | | 5 | 0.400012 | | 6 | 0.39985 | | 7 | 0.399821 | | 8 | 0.400871 | | 9 | 0.400169 | | 10 | 0.399408 |
2. 随机数的计算
在搜索排序中，有些时候我们需要给每个搜索文档的得分添加一个随机扰动， 并且让该扰动符合某种概率分布。假设我们有一个概率密度函数f(x), min<=x<=max, 并且有
那么可以利用f(x)和frand设计一个随机计算器r(frand()), 使得r(frand())返回的数据分布， 符合概率密度函数f(x)。
令
那么函数
符合密度函数为f(x)的分布。
下面对这个以上的公式进行简单的证明：
由于g(x)是单调函数， 并且x在[0,1]上均匀分布，那么
由于上述公式太复杂， 计算运算量大， 在线上实时计算的时候通常采用线性差值的方法。
算法为：
1）在offline计算的时候， 设有数组double A[N+1]；对于所有的i, 0<=i<=N, 令
2）在线上实时计算的时候，
令f = frand()，
lindex = (int) (f* N);
rindex = lindex +1;
那么线性插值的结果为 A[lindex]*(A[rindex]-f) + A[rindex] * (f – A[lindex])
我们做了一组实验，令f(x)服从标准正太分布N(0,1)， N=10000， 并利用该算法取得了200*N个数。对这些数做了个简单的统计， 得到x轴上每个小区间的概率分布图。
3后记
在日常工作中， 还有其他一些有趣的算法。比如对于top 100w的query， 每个query出现的频率不一样， 需要从这100w个query， 按照频率越高， 概率越高的方式随机选择query。限于篇幅， 就不一一介绍了。
http://blog.csdn.net/ssjhust123/article/details/7917685
随机算法涉及大量概率论知识，有时候难得去仔细看推导过程，当然能够完全了解推导的过程自然是有好处的，如果不了解推导过程，至少记住结论也是必要的。本文总结最常见的一些随机算法的题目，也当作面试的准备工作吧。需要说明的是，这里用到的随机函数都假定它能随机的产生范围[a,b]内的整数，即产生每个整数的概率相等。（虽然在实际中并不一定能实现，不过，谁在乎呢？这个世界都是这么随机）
一、随机排列数组
假设给定一个数组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可以产生均匀随机排列，它的证明过程如下：
首先给出k排列的概念，所谓k排列就是从n个元素中选取k个元素的排列，那么它一共有n!/(n-k)!个k排列。
循环不变式：for循环第i次迭代前，对于每个可能的i-1排列，子数组A[1...i-1]包含该i-1排列的概率为(n-i+1)! / n!。
初始化：在第一次迭代前，i=1，则循环不变式指的是对于每个0排列，子数组A[1...i-1]包含该0排列的概率为(n-1+1)! / n! = 1。A[1...0]为空的数组，0排列则没有任何元素，因此A包含所有可能的0排列的概率为1。不变式成立。
维持：假设在第i次迭代前，数组的i-1排列出现在A[1...i-1]的概率为(n-i+1) !/ n!，那么在第i次迭代后，数组的所有i排列出现在A[1...i]的概率为(n-i)! / n!。下面来推导这个结论：
考虑一个特殊的i排列p = {x1, x2, ... xi}，它由一个i-1排列p' ={x1, x2,..., xi1}后面跟一个xi构成。设定两个事件变量E1和E2：
E1为该算法将排列p‘放置到A[1...i-1]的事件，概率由归纳假设得知为Pr(E1) = (n-i+1)! / n!。
E2为在第i次迭代时将xi放入到A[i]的事件。
因此我们得到i排列出现在A[1...i]的概率为Pr {E2 ∩ E1} = Pr {E2 | E1} Pr {E1}.而Pr {E2 | E1} = 1/(n i + 1)，所以
Pr {E2 ∩ E1} = Pr {E2 | E1} Pr {E1}= 1 /(n i + 1) * (n i + 1)! / n! = (n i )! / n!。
结束：结束的时候i=n+1，因此可以得到A[1...n]是一个给定n排列的概率为1/n！。
扩展题
如果上面的随机排列算法写成下面这样，是否也能产生均匀随机排列？
- 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。
二、随机选取一个数字
题目：给定一个未知长度的整数流，如何随机选取一个数？（所谓随机就是保证每个数被选取的概率相等）
解法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。
三、随机选取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) {
- cout << i << endl;
- m--;
- }
- }
解法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个数字并输出即可。代码省略。
四、rand7()生成rand10()问题
五、趣味概率题
1）生男生女问题：在重男轻女的国家里，男女的比例是多少？在一个重男轻女的国家里，每个家庭都想生男孩，如果他们生的孩子是女孩，就再生一个，直到生下的是男孩为止。这样的国家，男女比例会是多少？
答案：还是1：1。在所有出生的第一个小孩中，男女比例是1：1；在所有出生的第二个小孩中，男女比例是1：1；.... 在所有出生的第n个小孩中，男女比例还是1：1。所以总的男女比例是1：1。
2）约会问题：两人相约5点到6点在某地会面，先到者等20分钟后离去，求这两人能够会面的概率。
答案：设两人分别在5点X分和5点Y分到达目的地，则他们能够会面的条件是|X-Y| <= 20，而整个范围为S={(x, y): 0 =< x <= 60, 0=< y <= 60}，所以会面的情况为图中表示的面积，概率为(60^2 - 40^2) / 60^2 = 5/9。
3）帽子问题：有n位顾客，他们每个人给餐厅的服务生一顶帽子，服务生以随机的顺序归还给顾客，请问拿到自己帽子的顾客的期望数是多少？ 答案：使用指示随机变量来求解这个问题会简单些。定义一个随机变量X等于能够拿到自己帽子的顾客数目，我们要计算的是E[X]。对于i=1, 2 ... n，定义Xi =
I {顾客i拿到自己的帽子}，则X=X1+X2+...Xn。由于归还帽子的顺序是随机的，所以每个顾客拿到自己帽子的概率为1/n，即Pr(Xi=1)=1/n，从而E(Xi)=1/n，所以E(X)=E(X1+X2+...Xn)=E(X1)+E(X2)+...E(Xn)=n*1/n = 1。即大约有1个顾客可以拿到自己的帽子。
4）生日悖论：一个房间至少要有多少人，才能使得有两个人的生日在同一天？
答案：对房间k个人中的每一对(i, j)定义指示器变量Xij = {i与j生日在同一天} ，则i与j生日相同时，Xij=1，否则Xij=0。两个人在同一天生日的概率Pr(Xij=1)=1/n。则用X表示同一天生日的两人对的数目，则E(X)=E(
∑ki=1 ∑kj=i+1 Xij) = C(k,2)*1/n = k(k-1)/2n，令k(k-1)/2n >=1， 可得到k>=28，即至少要有28个人，才能期望两个人的生日在同一天。
5）如果在高速公路上30分钟内看到一辆车开过的几率是0.95，那么在10分钟内看到一辆车开过的几率是多少？(假设常概率条件下)
答案：假设10分钟内看到一辆车开过的概率是x，那么没有看到车开过的概率就是1-x，30分钟没有看到车开过的概率是(1-x)^3，也就是0.05。所以得到方程(1-x)^3 = 0.05 ，解方程得到x大约是0.63。
参考资料
《算法导论》
《编程珠玑2》
http://blog.csdn.net/wxwtj/article/details/6621430
| 
转播
