C++ 从 0:n-1 (n > k) 范围内随机采样 k 个数字，无需放回

我正在致力于将 MATLAB 模拟移植到 C++ 中。为此，我尝试复制 MATLABrandsample() 函数 http://www.mathworks.com/help/stats/randsample.html。我还没有找到有效的方法来做到这一点。

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

我考虑了以下伪代码（受到第三个示例的启发cppreference.com http://en.cppreference.com/w/cpp/algorithm/random_shuffle），但我觉得这有点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++ 中实现这一点的最佳方法更感兴趣。

提前致谢！

这是一种不需要生成和洗牌一个巨大列表的方法，以防万一N很大但是k is not:

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 is:

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;
}

But if k相对于N，该算法可能会导致大量冲突，并且速度可能相当慢。我们可以做得更好，保证我们可以在每次插入时添加一个元素（由罗伯特·弗洛伊德 http://www.nowherenearithaca.com/2013/05/robert-floyds-tiny-and-beautiful.html):

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;
}