一次遍历等概率选取字符串中的某个字符

http://blog.chinaunix.net/uid-7921481-id-3022614.html

存在一个等概率的0、1发生器。
给一个文本流，给定一个指定的字符'x'，写一个函数，等概率地返回'x'的一个文本流偏移（就是'x'在字符串中的位置，比如文本为 axbx，那么x的偏移为{1, 3}，最后你需要获得1或者3，概率分别为1/2
假设文本流每个字符1字节）

============================基本问题=========================================
-----------------------------------------------------------------------------
已知等概率的0-1生产器uint make0~1()，求等概率的0~n生产器uint make0~n(uint n)
uint make0~n(uint n)
{
//...
//make0~1();
//...
return ?; //
}
具体什么方法使得make0~n最高效还是大家去想吧。。。
这里高效的意思是很快就能够返回结果。

-----------------------------------------------------------------------------
=============================================================================

【方法一】
设共有N个字符.
for(;;)
{
产生0~N-1的随机数r
if(A[r]=='x') return r;
}

分析：因为0~N-1是等概率的，产生'x'的位置也是等概率的.
缺陷：循环return的概率是R/N (R为'x'的个数)
若N超级大R很小,for循环很难return.

【方法二】
1：vector<uint> a_pos;//从头到尾记录'x'出现的位置
2：这里有R==a_pos.size(). 产生0~R-1的随机数r
3：取a_pos[r]即可。

缺陷：当R很大时空间开销很大。
比方法一的优势在于： 这个无须循环一下就可return.

【方法三】
先遍历一遍字符串，记下有'x'出现的次数为R；
产生0~R-1 的随机数 r
再遍历一遍字符串获取第r个'x'的位置

缺陷：最坏情况要遍历两遍字符串
优势：克服了方法一和二的缺陷

=========面试官会问，还有没有更好的方法=========================
【方法四】
有没有只遍历一遍就OK的方法呢？
直观的，我们每碰到一个'x'，设当前碰到的'x'的位置是i，我们可以以某个概率p去获取这个
'x'。此时获取'x'的概率绝对不是1/R，因为我们还不知道R的确切数字呢。
我们仍然需要继续遍历i之后的字符串，然后覆盖之。。。

于是列个方程组（*），获取第一个的概率是P(1)，获取第i个的概率是P(i)，获取第R个的概率是P(R)
满足：
P(1)(1-P(2))(1-P(3))...(1-P(R))=1/R
P(2)(1-P(3))...(1-P(R))=1/R
P(3)(1-P(4))...(1-P(R))=1/R
...
P(R-1)(1-P(R))=1/R
P(R)=1/R

上述方程组的思想是：每个字符获取的概率为1/R,遍历到它时能获取它，其后的所有该字符都不会获取。

求P(i)，得：
P(R)=1/R
P(R-1)=1/(R-1)
P(R-2)=1/(R-2)
...
P(2)=1/2
P(1)=1

于是乎，碰到第一个'x'就取，碰到第二个就以1/2的概率去取（若概率发生，就更新当前的'x'的位置），
...第R个'x'就以1/R的概率去取，于是乎完成操作。

优势：遍历一遍
缺陷：每碰到一个指定的字符都需要产生相应的随机数（产生等概率的随机数的最高效的算法是什么呢？）

注意了：对于一个文本流，在该流没有流完之前，你不知道该流总共有多少个字符，你也不知道总共有多少个指定的字符，并且只流一次（不会再流一次），因此，方法一和方法三都不行不通。

 

http://www.cnblogs.com/DeadKnight/archive/2010/06/21/1762190.html

题：
给你一个字符串（可能有几亿个字符），给定一个特殊的字符'a'，再给定一个可以产生0和1的随机数发生器，然后让你写一个函数，等概率地返回'a'的一个索引（就是'a'在字符串中的位置，比如字符串为 aaba，那么a的索引为{0, 1, 3}，等概率地返回0、1或者3）

想：
最简单的想法：这个如果产生随机数，再把该随机数哈希到字符串长度范围内，再把得到的哈希值作为下标去看对应的字符满足不满足条件，满足条件则返回下标，不满足条件的话重新随机。缺点——如果满足条件的字符很少，那么完全不靠谱！
稍微容易想到的方法：遍历这个字符串，对满足条件的下标建立索引，然后根据索引大小产生随机数，随机访问索引，返回索引所对应的下标值。这个可以有，但是也有明显缺点——如果满足条件的字符很多，那么索引很大，占用大量存储！
最后就是完美的解答了：

答：

 

#include <sstream>
#include <iostream>
#include <string>
#include <time.h>

using namespace std;

int given_rand()
{
    return rand() % 2;
}

unsigned int my_rand()
{
    int i, result;
    for( i = 0, result = 0 ; i < 32 ; i++ )
    {
        result <<= 1;
        result += given_rand();
    }
    return result;
}

int main()
{    
    int index = 0, cnt = 0;
    stringstream strstring("aabbbaaabbbbabbbbabbbbbbbbbbbaabbbbbbb");
    int ret = 0;
    char c;

    srand(time(NULL));
    while (strstring >> c)
    {
        index++;
        if (c == 'a') {
            ++cnt;
            
            int rr = my_rand() % (cnt);            
            if (rr < 1)
                ret = index;
        }
        
    }
    cout << ret;
    return 0;
}