algorithm - 在随机抽取 : how to insure that a value is not re-drawn too soon

Question

当从连续的一组值中随机抽取时，允许抽取的值 再次绘制，给定的值(当然)有很小的机会被立即连续绘制两次(或更多)，但这会导致问题(对于给定的应用程序)，我们希望消除这种机会。关于如何做到这一点(简单/高效)的任何算法想法？

理想情况下，我们希望将阈值设置为数据集大小的百分比:

假设值集的大小N=100，阈值T=10%，那么如果给定的值在当前绘制中被绘制，它保证不会在接下来的 N*T=10 抽奖中再次出现。

显然，此限制会在随机选择中引入偏差。我们不介意 所提出的算法在选择的随机性中引入了进一步的偏差，真正 这个应用程序的问题是选择是足够随机的 对于人类观察者。

作为一个实现细节，这些值存储为数据库记录，因此可以使用数据库表标志/值，或者可能是外部存储器结构。也欢迎有关抽象案例的回答。

编辑:

我刚刚遇到了另一个 SO 问题 here ，这与我自己的有很好的重叠。回顾那里的优点。

Answer 1

这是一个在 O(1) 中完成整个过程的实现(对于单个元素)，没有任何偏差:

想法是将数组 A 中的最后 K 个元素(其中包含所有值)视为一个队列，我们​​从前 N-k 个值中提取一个值A中的随机值，与N-Pointer位置的一个元素交换，当Pointer代表队列的头部，当Pointer代表队列头部时，重置为1它跨越了 K 个元素。

为了消除前 K 次抽取中的任何偏差，随机值将在 1 和 N-Pointer 之间而不是 N-k 之间抽取，所以这个虚拟队列的大小在每次绘制时都在增加，直到达到 K 的大小(例如，在 3 次绘制之后，可能值的数量出现在索引 1 之间的 A 中 和 N-3，挂起的值出现在索引 N-2 到 N 中。

绘制单个元素的所有操作都是O(1)，并且在整个过程中没有偏差。

void DrawNumbers(val[] A, int K)
{
    N = A.size;
    random Rnd = new random;
    int Drawn_Index;
    int Count_To_K = 1;
    int Pointer = K;

    while (stop_drawing_condition)
    {
        if (Count_To_K <= K)
        {
            Drawn_Index = Rnd.NextInteger(1, N-Pointer);
            Count_To_K++;
        }

        else
        {
            Drawn_Index = Rnd.NextInteger(1, N-K)
        }

        Print("drawn value is: " + A[Drawn_Index])

        Swap(A[Drawn_Index], A[N-Pointer])
        Pointer--;
        if (Pointer < 1) Pointer = K; 
    }
}

我之前的建议，通过使用一个列表和一个实际的队列，依赖于列表的remove方法，我相信它最多可以是O(logN) 通过使用数组实现自平衡二叉树，因为列表必须直接访问索引。

void DrawNumbers(list N, int K)
{
    queue Suspended_Values = new queue;
    random Rnd = new random;
    int Drawn_Index;

    while (stop_drawing_condition)
    {
          if (Suspended_Values.count == K)
                N.add(Suspended_Value.Dequeue());

          Drawn_Index = Rnd.NextInteger(1, N.size) // random integer between 1 and the number of values in N

          Print("drawn value is: " + N[Drawn_Index]);          

          Suspended_Values.Enqueue(N[Drawn_Index]);
          N.Remove(Drawn_Index);
    }
}