選択サンプリング法(selection sampling technique)

N個の中からランダムにn個のを選択するためのアルゴリズム

1. t = 0, m = 0とする。
2. [0, 1]の一様乱数uを生成する。
3. もし、 (N - t) * u >= n - m ならば5へ。それ以外ないなら4へ。
4. tを採用し、++t, ++mとする。もしm < nなら、1へ。　そうでないなら終了。
5. ++tとし、2へ。

template <typename U>
void generate(U& u, int size, int n, int t = 0, int m = 0)
{
	if ((size - t) * u() > n - m) {
		return generate(u, size, n, ++t, m);
	}
	std::cout << t << std::endl;
	if (m + 1 < n) {
		return generate(u, size, n, ++t, ++m);
	}
}


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

	int size = 100;
	int n = 10;
	generate([&]() {return d(mt); }, size, n);

	return 0;
}