没有替换的采样算法？

Question

我试图测试特定数据集群偶然发生的可能性.一种强有力的方法是蒙特卡罗模拟,其中数据和组之间的关联被随机重新分配很多次(例如10,000),并且使用聚类度量来比较实际数据与模拟以确定ap值.

我已经完成了大部分工作,使用指针将分组映射到数据元素,因此我计划随机重新分配指向数据的指针.问题:在没有替换的情况下采样的快速方法是什么,以便在复制数据集中随机重新分配每个指针？

例如(这些数据只是一个简化的例子):

数据(n = 12值) - A组:0.1,0.2,0.4/B组:0.5,0.6,0.8/C组:0.4,0.5/D组:0.2,0.2,0.3,0.5

对于每个复制数据集,我将具有相同的簇大小(A = 3,B = 3,C = 2,D = 4)和数据值,但会将值重新分配给簇.

为此,我可以生成1-12范围内的随机数,分配A组的第一个元素,然后生成1-11范围内的随机数,并分配A组中的第二个元素,依此类推.指针重新分配很快,我将预先分配所有数据结构,但没有替换的采样似乎是一个可能已经解决过很多次的问题.

逻辑或伪代码首选.

Answer 1

这里有一些基于Knuth的书籍Seminumeric Algorithms的算法3.4.2S的无需替换的代码.

void SampleWithoutReplacement
(
    int populationSize,    // size of set sampling from
    int sampleSize,        // size of each sample
    vector<int> & samples  // output, zero-offset indicies to selected items
)
{
    // Use Knuth's variable names
    int& n = sampleSize;
    int& N = populationSize;

    int t = 0; // total input records dealt with
    int m = 0; // number of items selected so far
    double u;

    while (m < n)
    {
        u = GetUniform(); // call a uniform(0,1) random number generator

        if ( (N - t)*u >= n - m )
        {
            t++;
        }
        else
        {
            samples[m] = t;
            t++; m++;
        }
    }
}

Jeffrey Scott Vitter在"An Efficient Algorithm for Sequential Random Sampling",ACM Transactions on Mathematical Software,13(1),1987年3月,58-67中有一种更有效但更复杂的方法.

Answer 2

基于John D. Cook答案的 C++工作代码.

#include <random>
#include <vector>

double GetUniform()
{
    static std::default_random_engine re;
    static std::uniform_real_distribution<double> Dist(0,1);
    return Dist(re);
}

// John D. Cook, https://stackoverflow.com/a/311716/15485
void SampleWithoutReplacement
(
    int populationSize,    // size of set sampling from
    int sampleSize,        // size of each sample
    std::vector<int> & samples  // output, zero-offset indicies to selected items
)
{
    // Use Knuth's variable names
    int& n = sampleSize;
    int& N = populationSize;

    int t = 0; // total input records dealt with
    int m = 0; // number of items selected so far
    double u;

    while (m < n)
    {
        u = GetUniform(); // call a uniform(0,1) random number generator

        if ( (N - t)*u >= n - m )
        {
            t++;
        }
        else
        {
            samples[m] = t;
            t++; m++;
        }
    }
}

#include <iostream>
int main(int,char**)
{
  const size_t sz = 10;
  std::vector< int > samples(sz);
  SampleWithoutReplacement(10*sz,sz,samples);
  for (size_t i = 0; i < sz; i++ ) {
    std::cout << samples[i] << "\t";
  }

  return 0;
}

Answer 3

看到我对这个问题的回答O(1)中的唯一(非重复)随机数？.同样的逻辑应该完成你想要做的事情.