C++-不存储数据流的前提下,从输入流中获得这 n 个等概率的随机数据呢?

Question

假设有一个长度未知的数据流,监控程序需要随机地返回其中的 n 个数据进行检查,采用何种方法,
才能在不需要存储数据流的基础上,获得这 n 个等概率的随机数据呢?

#include <iostream>
#include <cstdlib>
using namespace std;

void quyang(int n,int* output)
{
    int m=0;
    int val;
    while(m<n && cin>>val)
        output[m++]=val;
    
    while(cin>>val)
    {
        m++;
        if(rand()%m<n)
            output[rand()%n]=val;
    }
}

int main()
{
    int output[5];
    quyang(5,output);
    for(int i=0;i<5;i++)
        cout<<output[i]<<" ";
}

Answer 1

此方法正确性证明：
1.由于一共n个元素被存储，所以选取其中一个元素的概率为1/n（这个暂时放着，后面要用到）
2.如图

我们先求n个数据中，一个数据被最终取到的概率，显然需要所有s个数据（假设数据总数为s）中每个数字被取得的概率均等，即为1/s。
如果要n个数据中的第一个数据被取得，就是没有被后续数据的任何一个数据所替换。
先来求没有被第n+1个数据替换的概率：
先求取相关概率吧，以n/k概率判断是否取，即为：
取得的概率——n/(n+1)
不取得的概率——1/(n+1)
取得并与第一个数据交换的概率(n/(n+1)) * (1/n)
所以：第一个数据不被第n+1个数据替换的概率为(1 - (n/(n+1)) * (1/n))
化简为：n/(n+1)
这是第n+1个数据，那么 后续数据呢？依次可得
不被第n+2个数据替换的概率：(n+1) / (n+2)
不被第n+3个数据替换的概率：(n+2) / (n+3)
…………………………………………………………………………………………………
不被第s-1个数据替换的概率: (s-2) / (s-1)
不被第s个数据替换的概率： (s-1) / s
综合起来，第一个数据不被替换的概率为各个概率的乘积，也就是：
(n/(n+1)) * ((n+1)/(n+2)) * ((n+2)/(n+3)) * …… * ((s-2)/(s-1)) * ((s-1)/s)
这个，前后项上下约分咯，结果化简后是： n/s。
3.可以用到第一步的那个概率咯，因为第一个数据为前n个数据中的一个，而最终的结果是n个数据中随机的一个，所以第二步求得的概率还需要乘以第一步中的1/n，结果就是(n/s) * (1/n)即为1/s，果然是我们期待的结果。既然每个数据取得的概率都是1/s，那么，等概率咯，恭喜，方法成立。