rand_k_in_n.cpp

rand_k_in_n.cpp

#include <algorithm>
#include <random>
#include <iostream>
#include <vector>
using namespace std;

vector<int> random_k_in_n(size_t k, int n) { // generate k distinct number in [0..n-1]
    vector<int> ans;
    ans.reserve(k);
    std::random_device rd;
    std::default_random_engine rng {rd()};
    for (int i = 0; i < n && k; i++) {
        std::uniform_int_distribution<> dist(0, n - i - 1);
        if (dist(rng) < k) {
            ans.push_back(i);
            k--;
        }
    }
    return ans;
}
int main() {
    vector<int>  ans = random_k_in_n(1e5, 1e9);
    for (size_t i = 0; i < ans.size(); i++) {
        // cout << ans[i] << endl;
    }
    return 0;
}