梁剑的Blog

这是今天看的第二篇和概率有关的文章——《数学之美番外篇：进化论中的概率论》。

文章的开始就提到了：

偶然性在进化中确实存在（例如，偶然性的突变可以产生新的特征），但是进化并不依赖偶然性来产生新的器官、蛋白质或其他实体。截然相反的是，自然选择，作为进化中已知的最主要机制，却会明确保留“需要的”（能适应的）特性，消除“不需要的”（无法适应的）特性。只要选择的影响力存在，自然选择就能把进化向一个方向推进，在出乎意料的短时间内产生复杂的结构。举个例子，现有由13个字母构成的序列“TOBEORNOTTOBE”，假设有几百万只猴子，每只猴子每秒钟挑一条短语，需要78,800年才能从26^13种可能中选出这样的排列。不过，Glendale College的Richard Hardison在20世纪80年代写过一个程序，它能够在随机产生序列的同时，保证那些已经出现在正确位置上的字母不会变化（这样做倒有点《汉姆雷特》 的味道。译注：这个句子看了大半天才明白，嘿嘿）。这个程序平均只需要336次迭代就能生成上文提到的短语，时间少于90秒。更神奇的是，把莎士比亚的整个剧本重新生成一遍也只需要四天半时间。

很好奇是否真的是336，所以也写了个程序

#include <cstdlib>
#include <iostream>
#include <string>
 
using namespace std;
 
int GenerateRandomString(const string &sTarget, const string &sNow, string &sResult)
{
	char cBase = 'a';
	int iCounter = 0;
	for( unsigned int i = 0; i < sTarget.size(); i++ )
	{
		if( sTarget[i] != sNow[i] )
		{
			int r = rand() % 26;	
			sResult[i] = (cBase+r);	
			iCounter++;
		}
	}
	return iCounter;
}
 
int CountDifference(const string &s1, const string &s2, string &s3)
{
	unsigned int i = 0;
	unsigned int iCount = 0;
	for(; i < s1.size() && i < s2.size(); i++ )
	{
		if( s1[i] == s2[i] && s3[i] != s1[i] )
		{
			iCount++;
			s3[i] = s1[i];
		}
	}
	return iCount;
}
 
int evolution(int iSeed)
{
	string sTarget = "tobeornotobe";
	string sNow;
	for( unsigned int i = 0; i < sTarget.size(); i++ )
	{
		sNow += ' ';
	}
 
	int iNotMatch = sTarget.size();
	int iCounter = 1;
	int iRandTime = 0;
	srand(time(NULL) + getpid() + iSeed);
	while( iNotMatch > 0 )
	{
		string sTemp = "             ";
		iRandTime += GenerateRandomString(sTarget, sNow, sTemp);	
		int iMatch = CountDifference(sTarget, sTemp, sNow);
		iNotMatch -= iMatch;
		cout << iCounter++ << ":t" << iRandTime << "t" << iMatch << "t" << sTemp << "t" << sNow << endl;
	}
	return iRandTime;
}
 
int main(int c, char **v)
{
	unsigned int iLoop = ( c == 2 )? atoi(v[1]) : 100;
	int iRandTime = 0;
	for( unsigned int i = 0; i < iLoop; i++)
	{
		cout << i << "----------------------------" << endl;
		iRandTime += evolution(i);
		cout << iRandTime << " / " << iLoop << " = " << double(iRandTime) / iLoop << endl;
	}
	return 0;
}

而根据这个程序的结果，生成10000次”tobeornottobe”，平均每次需要331次随机，结果还是相当接近的，当然速度就快多了。
另外，原文作者说他自己写的程序是82次，这应该是生成整个句子的次数，而不是random的次数吧。
反映到上面的程序中，就是输出结果的行数均值，也和实际结果吻合。
附上其中一次的结果：

1:	12	1	cmraiithaosb 	         o
2:	23	0	pvzordffr ha 	         o
3:	34	0	bxyneoxtr hx 	         o
4:	45	0	pdxyfkmly lc 	         o
5:	56	0	nifwqerkv tt 	         o
6:	67	0	khhcrjsep en 	         o
7:	78	0	huvvzxphl du 	         o
8:	89	0	ppkcrewns kt 	         o
9:	100	0	qzaqfoilf ky 	         o
10:	111	0	cghkflbzz vo 	         o
11:	122	1	wvopvraux df 	     r   o
12:	132	0	flvlw lwy yi 	     r   o
13:	142	0	wprip wsx db 	     r   o
14:	152	0	mpigu cub oo 	     r   o
15:	162	1	lmjwn fdt pd 	     r  to
16:	171	0	kwegg xz  fd 	     r  to
17:	180	0	vxaku tf  iv 	     r  to
18:	189	1	gtbka sm  vc 	  b  r  to
19:	197	0	ac gk qb  nd 	  b  r  to
20:	205	0	hz oc dx  gy 	  b  r  to
21:	213	0	lf xz sx  kz 	  b  r  to
22:	221	1	fe ph qo  hu 	  b  r oto
23:	228	0	pp ql b   qv 	  b  r oto
24:	235	0	ug yn g   vg 	  b  r oto
25:	242	0	uj my i   jt 	  b  r oto
26:	249	0	nq rd p   fg 	  b  r oto
27:	256	1	pw oo b   ta 	  b or oto
28:	262	0	xc x  g   jk 	  b or oto
29:	268	0	yt r  y   mt 	  b or oto
30:	274	0	el d  v   jz 	  b or oto
31:	280	0	ls l  e   wm 	  b or oto
32:	286	1	tt m  u   vn 	t b or oto
33:	291	0	 p d  z   wa 	t b or oto
34:	296	0	 r n  f   gb 	t b or oto
35:	301	1	 a t  r   se 	t b or oto e
36:	305	0	 q b  p   y  	t b or oto e
37:	309	0	 c p  e   x  	t b or oto e
38:	313	0	 e y  b   r  	t b or oto e
39:	317	0	 x p  s   f  	t b or oto e
40:	321	0	 l x  w   o  	t b or oto e
41:	325	0	 n n  i   l  	t b or oto e
42:	329	0	 q c  t   o  	t b or oto e
43:	333	0	 l b  t   y  	t b or oto e
44:	337	1	 i s  n   k  	t b ornoto e
45:	340	0	 s c      e  	t b ornoto e
46:	343	0	 m v      z  	t b ornoto e
47:	346	0	 x c      q  	t b ornoto e
48:	349	0	 r m      u  	t b ornoto e
49:	352	0	 x h      r  	t b ornoto e
50:	355	0	 z o      p  	t b ornoto e
51:	358	0	 y m      z  	t b ornoto e
52:	361	0	 e m      g  	t b ornoto e
53:	364	0	 q w      g  	t b ornoto e
54:	367	0	 q l      f  	t b ornoto e
55:	370	0	 t o      i  	t b ornoto e
56:	373	0	 k d      p  	t b ornoto e
57:	376	0	 q v      c  	t b ornoto e
58:	379	0	 z i      h  	t b ornoto e
59:	382	0	 n t      i  	t b ornoto e
60:	385	0	 a j      d  	t b ornoto e
61:	388	0	 q y      e  	t b ornoto e
62:	391	0	 s t      f  	t b ornoto e
63:	394	0	 a r      u  	t b ornoto e
64:	397	1	 o j      o  	tob ornoto e
65:	399	0	   b      a  	tob ornoto e
66:	401	2	   e      b  	tobeornotobe