貯蔵庫サンプリング(Reservoir sampling)

入力(数>n)からn個をランダムに選択する方法。

1. 最初のn個をI[0]...I[n-1]にコピーする。t = n - 1。
2. 入力値がなかったら、5へ。
3. ++tとし、[0, t]の一様乱数uを生成する。 u >= nならば、2へ。
4. I[u] = I[t]とし、2へ。
5. Iをソートして終了。

#include <random>
#include <iostream>
#include <vector>
#include <assert.h>
#include <algorithm>

template <typename U>
const std::vector<int>& generate(
	U& u, 
	const std::vector<int>& inputs, 
	std::vector<int>& i, 
	std::size_t n, 
	std::size_t t)
{
	if (inputs.size() <= t) {
		std::sort(i.begin(), i.end());
		return i;
	}
	std::size_t r = static_cast<std::size_t>(t * u());
	++t;
	if (r >= n) return generate(u, inputs, i, n, t);
	i[r] = inputs[t];
	return generate(u, inputs, i, n, t);
}


template <typename U>
std::vector<int> generate(
	U& u,
	const std::vector<int>& inputs,
	std::size_t n)
{
	assert(inputs.size() >= n);
	std::vector<int> results(inputs.begin(), inputs.begin() + n);
	return generate(u, inputs, results, n, n);
}


int main() 
{
	unsigned int seed = 54635;
	std::mt19937 mt(seed);
	std::uniform_real_distribution<double> d;

	std::size_t size = 100;
	std::vector<int> inputs(size);
	for (std::size_t j = 0; j < inputs.size(); ++j) {
		inputs[j] = j;
	}

	std::size_t n = 10;
	std::vector<int> r = generate([&]() {return d(mt); }, inputs, n);

	for (auto x : r) std::cout << x << std::endl;
	return 0;
}