Any efficient building function in C++/C to fast uniformly sample b entries without replacement from n entries?

Question

It seems that, using shuffle(Index, Index+n, g) before getting the first b entries is still not efficient when n is very big but b is very small, where Index is a vector/array storing 0 ... (n-1).

Answer 1

You can take the standard shuffle algorithm and modify it to stop after shuffling just the first b entries.

Answer 2

Here is a different idea than what sh1 suggests. Unlike a previous answer it is mathematically sound. No % BS.

#include <algorithm>
#include <iostream>
#include <iterator>
#include <ostream>
#include <random>
#include <set>
#include <vector>

int main()
{
    // Configuration.
    auto constexpr n = 100;
    auto constexpr b = 10;

    // Building blocks for randomness.
    auto const seed = std::mt19937::result_type{ std::random_device{}() };
    std::cout << "seed = " << seed << std::endl;
    auto engine = std::mt19937{ seed };
    auto distribution = std::uniform_int_distribution<>{};

    // Creating the data source. Not part of the solution.
    auto reservoir = std::vector<int>{};
    std::generate_n(std::back_inserter(reservoir), n, 
        [i = 0]() mutable { return i++; });

    // Creating the sample.
    // Idea attributed to Bob Floyd by Jon Bentley in Programming Pearls 2nd Edition.
    auto sample = std::set<int>{};
    for (auto i = n - b; i != n; ++i)
    {
        auto const param = std::uniform_int_distribution<>::param_type(0, i);
        auto const j = distribution(engine, param);
        (sample.find(j) == sample.cend()) 
            ? sample.insert(j) 
            : sample.insert(i);
    }

    // Converting the sample to an output vector and shuffle it, if necessary.
    auto output = std::vector<int>(std::cbegin(sample), std::cend(sample));
    std::shuffle(std::begin(output), std::end(output), engine);

    // Print out the result.
    for (auto const x : output) { std::cout << x << " "; }
    std::cout << std::endl;

    return 0;
}