2026-10-13
sample.cpp
template <class Pick>
std::vector<int> sample(std::istream& in, std::size_t k, Pick pick) {
}
in の整数を終わりまで読み、そのうち k 個を、どの値も同じ確率で残るように選んで返す sample を書いてください。何個読むことになるかは前もって分かりません。pick(i) は、i 番目(0から数える)の値を読んだときに呼ぶ関数で、0以上 i 以下の整数を一様に返します。値が k 個に満たないときは、読んだ値をすべて返します。例の in は、入力例1と2では "1 2 3 4 5"、入力例3では "7 8" を読む std::istringstream です。
入力例 1
sample(in, 2, [](std::size_t i) { return i; })
出力例 1
{1, 2}
入力例 2
sample(in, 2, [](std::size_t) { return std::size_t{0}; })
出力例 2
{5, 2}
入力例 3
sample(in, 3, [](std::size_t i) { return i; })
出力例 3
{7, 8}
Reference
template <class Pick>
std::vector<int> sample(std::istream& in, std::size_t k, Pick pick) {
std::vector<int> kept;
std::size_t i = 0;
for (int x; in >> x; ++i) {
if (kept.size() < k)
kept.push_back(x);
else if (std::size_t j = pick(i); j < k)
kept[j] = x;
}
return kept;
}
最初の k 個はそのまま kept に入れます。i 番目の値は、pick(i) が返す i + 1 通りの番号のうち、0から k - 1 の k 通りに当たったときだけ、その番号の位置に入ります。入る確率は k / (i + 1) で、あとから来た値に追い出される確率まで掛け合わせると、読み終えたときにはどの値も「k ÷ 読んだ個数」の確率で残っています。
各値の扱いは、それまでに読んだ個数 i だけで決まるので、全体の件数を知る必要がありません。ループの条件 in >> x は、読めなくなった時点で偽になり、入力の終わりでループを抜けます。
実際に使うときは std::mt19937 gen; を用意し、[&](std::size_t i) { return std::uniform_int_distribution<std::size_t>(0, i)(gen); } のように渡します。掲載したのは参考実装で、唯一の正解ではありません。