C++ 从 0 :n-1 (n > k) without replacement 范围内随机抽取 k 个数

Question

我正在努力将 MATLAB 模拟移植到 C++ 中。为此，我试图复制 MATLAB 的 randsample() function .我还没有想出一个有效的方法来做到这一点。

所以我问大家，在 C++ 中，如何最好地从 0:n-1(对于 n > k)范围内随机抽取 k 个数字而不进行替换？

我考虑过以下伪代码(灵感来自 cppreference.com 上的第三个示例)，但我觉得它有点 hacky:

initialize vect<int> v of size n
for i = 0 to n-1
    v[i] = i
shuffle v
return v[0 to k-1]

这里的缺点也是需要先构建一个庞大的数组。这似乎是缓慢/笨拙的矫枉过正。

如果您能提供帮助，我很乐意在这里提供一些指导。我对理论不太感兴趣(算法很有趣，但现在与我的需求不相关)，我更感兴趣的是用 C++ 实现它的最佳方法。

提前致谢!

Answer 1

如果 N 很大但 k 不是，这里有一种方法不需要生成和洗牌一个巨大的列表:

std::vector<int> pick(int N, int k) {
    std::random_device rd;
    std::mt19937 gen(rd());

    std::unordered_set<int> elems = pickSet(N, k, gen);

    // ok, now we have a set of k elements. but now
    // it's in a [unknown] deterministic order.
    // so we have to shuffle it:

    std::vector<int> result(elems.begin(), elems.end());
    std::shuffle(result.begin(), result.end(), gen);
    return result;
}

现在实现 pickSet 的简单方法是:

std::unordered_set<int> pickSet(int N, int k, std::mt19937& gen)
{
    std::uniform_int_distribution<> dis(1, N);
    std::unordered_set<int> elems;

    while (elems.size() < k) {
        elems.insert(dis(gen));
    }

    return elems;
}

但如果 k 相对于 N 较大，则该算法可能会导致大量冲突并且可能会非常慢。我们可以通过保证可以在每次插入时添加一个元素来做得更好(由 Robert Floyd 提供给您):

std::unordered_set<int> pickSet(int N, int k, std::mt19937& gen)
{
    std::unordered_set<int> elems;
    for (int r = N - k; r < N; ++r) {
        int v = std::uniform_int_distribution<>(0, r)(gen);

        // there are two cases.
        // v is not in candidates ==> add it
        // v is in candidates ==> well, r is definitely not, because
        // this is the first iteration in the loop that we could've
        // picked something that big.

        if (!elems.insert(v).second) {
            elems.insert(r);
        }   
    }
    return elems;
}