C ++随机抽取范围0：n-1（n> k）中的k个数字，无需替换

Question

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

所以我问你们所有人，如何在0 + n-1（n> k）范围内随机抽样k数而不用C ++替换？

我考虑过以下伪代码（受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<>(1, 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;
}

Answer 2

Bob Floyd创建了一个使用集合的随机样本算法。中间结构大小与您要采用的样本大小成比例。

它的工作原理是随机生成K个数字并将它们添加到一个集合中。如果生成的数字恰好存在于集合中，则会放置计数器的值，而不是保证尚未看到。因此，保证在线性时间内运行并且不需要大的中间结构。它仍具有相当好的随机分布属性。

这个代码基本上是从编程珍珠中解除了一些修改，以使用更现代的C ++。

unordered_set<int> BobFloydAlgo(int sampleSize, int rangeUpperBound)
{
     unordered_set<int> sample;
     default_random_engine generator;

     for(int d = rangeUpperBound - sampleSize; d < rangeUpperBound; d++)
     {
           int t = uniform_int_distribution<>(0, d)(generator);
           if (sample.find(t) == sample.end() )
               sample.insert(t);
           else
               sample.insert(d);
     }
     return sample;
}

此代码尚未经过测试。