Namaran

Code daily. Without assist.

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); } のように渡します。掲載したのは参考実装で、唯一の正解ではありません。