3

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

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

说这组值的大小N=100和阈值T=10%，那么如果给定的值在当前抽奖中被绘制，则保证不会在下一次N*T=10抽奖中再次出现。

显然，这种限制在随机选择中引入了偏差。我们不介意所提出的算法在选择的随机性中引入了进一步的偏差，对于这个应用程序来说真正重要的是选择是随机的，足以让人类观察者出现。

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

编辑：

我刚刚在这里遇到了另一个 SO 问题，它与我自己的问题有很好的重叠。经历那里的优点。

4

5 回答 5

2

这是一个实现O(1)（对于单个元素）没有任何偏差的整个过程：

想法是将数组中的最后 K 个元素A（包含所有值）视为一个队列，我们​​从 中的第一个N-k值中抽取一个值A，这是随机值，并将其与 position 中的元素交换N-Pointer，当 Pointer表示队列的头部，当它穿过 K 个元素时重置为 1。

为了消除前 K 次抽奖中的任何偏差，随机值将在1和而N-Pointer不是索引和，并且挂起的值出现在索引到 中。N-kKA1N-3N-2N

所有操作都是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);
    }
}
于 2013-10-16T10:57:16.630 回答
2

假设您的列表中有 n 个项目，并且您不希望选择最后 k 个项目中的任何一个。

从大小为 nk 的数组中随机选择，并使用大小为 k 的队列粘贴您不想绘制的项目（添加到前面并从后面删除）。

所有操作都是 O(1)。

---- 澄清 ----

给出 n 个项目，并且目标是不重绘任何最后 k 个绘图，创建一个数组和队列，如下所示。

  1. 创建一个大小为 nk 的数组 A，并将 nk 项放入列表中（随机选择，或随心所欲地播种）。

  2. 创建一个队列（链表）Q 并用剩余的 k 项填充它，再次以随机顺序或您喜欢的任何顺序。

现在，每次你想随机选择一个项目时：

  1. 从你的数组中选择一个随机索引，称之为 i。

  2. 将 A[i] 给任何请求它的人，并将它添加到 Q 的前面。

  3. 把Q后面的元素去掉，存入A[i]。

创建数组和链表后，一切都是O(1)，这是一次O(n)的操作。

现在，您可能想知道，如果我们想更改 n（即添加或删除一个元素）该怎么办。

每次我们添加一个元素时，我们要么想增加 A 的大小，要么增加 Q 的大小，这取决于我们决定什么是 k 的逻辑（即固定值、n 的固定分数等等……）。

如果 Q 增加，那么结果是微不足道的，我们只需将新元素附加到 Q。在这种情况下，我可能会将其附加到 Q 的末尾，以便它尽快发挥作用。你也可以把它放在 A 中，从 A 中踢出一些元素并将其附加到 Q 的末尾。

如果 A 增加，您可以使用标准技术在摊销常数时间内增加数组。例如，每次 A 填满时，我们将它的大小加倍，并跟踪 A 的活细胞数量。（如果不熟悉，请在 Wikipedia 中查找“Dynamic Arrays”）。

于 2013-10-16T13:45:13.363 回答
2

我假设您有一个数组 ，A其中包含您要绘制的项目。在每个时间段，您从 中随机选择一个项目A。

您希望防止任何给定项目 ,在某些迭代中i再次被绘制。k

假设您的阈值是 10% A。

所以创建一个队列，调用它drawn，它可以容纳threshold项目。还要创建一个包含绘制项目的哈希表。调用哈希表hash。

然后：

do
{
    i = Get random item from A
    if (i in hash)
    {
        // we have drawn this item recently. Don't draw it.
        continue;
    }
    draw(i);
    if (drawn.count == k)
    {
        // remove oldest item from queue
        temp = drawn.dequeue();
        // and from the hash table
        hash.remove(temp);
    }
    // add new item to queue and hash table
    drawn.enqueue(i);
    hash.add(i);
} while (forever);

哈希表的存在只是为了提高查找速度。如果您愿意对队列进行顺序搜索以确定最近是否已绘制项目，则可以不使用哈希表。

于 2013-10-16T15:58:46.050 回答
1

我将所有“值”放入大小为 N 的“列表”中，然后打乱列表并从列表顶部检索值。然后，您将检索到的值“插入”到任意索引 >= N*T 的随机位置。

不幸的是，我并不是真正的数学专家：​​（所以我只是尝试了一下（在 VB 中，所以请把它当作伪代码；））

Public Class BiasedRandom

Private prng As New Random
Private offset As Integer
Private l As New List(Of Integer)

Public Sub New(ByVal size As Integer, ByVal threshold As Double)

    If threshold <= 0 OrElse threshold >= 1 OrElse size < 1 Then Throw New System.ArgumentException("Check your params!")
    offset = size * threshold
    ' initial fill
    For i = 0 To size - 1
        l.Add(i)
    Next
    ' shuffle "Algorithm p"
    For i = size - 1 To 1 Step -1
        Dim j = prng.Next(0, i + 1)
        Dim tmp = l(i)
        l(i) = l(j)
        l(j) = tmp
    Next

End Sub

Public Function NextValue() As Integer

    Dim tmp = l(0)
    l.RemoveAt(0)
    l.Insert(prng.Next(offset, l.Count + 1), tmp)
    Return tmp

End Function

结束类

然后是一个简单的检查：

Public Class Form1
Dim z As Integer = 10
Dim k As BiasedRandom

Private Sub Form1_Load(sender As Object, e As EventArgs) Handles MyBase.Load
    k = New BiasedRandom(z, 0.5)
End Sub

Private Sub Button1_Click(sender As Object, e As EventArgs) Handles Button1.Click

    Dim j(z - 1)
    For i = 1 To 10 * 1000 * 1000
        j(k.NextValue) += 1
    Next
    Stop
End Sub

结束类

当我检查分布时，它看起来还不错，没有武装的眼睛；）

编辑：在考虑了 RonTeller 的论点之后，我不得不承认他是对的。我不认为有一种性能友好的方式来实现想要的并保持一个好的（不比要求的更偏向）随机顺序。我想到了以下想法：

给定一个这样的列表（无论是数组）：

0123456789 ' 没有洗牌以明确我的意思

我们返回第一个元素 0。这个元素不能再出现 4 次（例如）更多的平局，但我们也希望避免强烈的偏差。为什么不简单地将它放在列表的末尾，然后打乱列表的“尾部”，即最后 6 个元素？

1234695807

我们现在返回 1 并重复上述步骤。

2340519786

等等等等。由于删除和插入是一种不必要的工作，因此可以使用一个简单的数组和一个指向实际元素的“指针”。我已经更改了上面的代码以提供示例。它比第一个慢，但应该避免提到的偏见。

Public Function NextValue() As Integer

    Static current As Integer = 0
    ' only shuffling a part of the list
    For i = current + l.Count - 1 To current + 1 + offset Step -1
        Dim j = prng.Next(current + offset, i + 1)
        Dim tmp = l(i Mod l.Count)
        l(i Mod l.Count) = l(j Mod l.Count)
        l(j Mod l.Count) = tmp
    Next
    current += 1

    Return l((current - 1) Mod l.Count)

End Function

编辑2：

最后（希望如此），我认为解决方案非常简单。下面的代码假设有一个由 N 个元素组成的数组，TheArray它包含随机顺序的元素（可以重写以使用排序数组）。该值DelaySize决定了一个值在绘制后应该暂停多长时间。

Public Function NextValue() As Integer

    Static current As Integer = 0

    Dim SelectIndex As Integer = prng.Next(0, TheArray.Count - DelaySize)
    Dim ReturnValue = TheArray(SelectIndex)
    TheArray(SelectIndex) = TheArray(TheArray.Count - 1 - current Mod DelaySize)
    TheArray(TheArray.Count - 1 - current Mod DelaySize) = ReturnValue
    current += 1
    Return ReturnValue

End Function
于 2013-10-16T11:05:21.170 回答
1

基于集合的方法：

如果阈值很低（比如低于 40%），建议的方法是：

  • 有一组最后N*T生成的值的队列。
  • 生成值时，请不断重新生成它，直到它不包含在集合中。
  • 推送到队列时，弹出最旧的值并将其从集合中删除。

伪代码：

generateNextValue:
  // once we're generated more than N*T elements,
  //   we need to start removing old elements
  if queue.size >= N*T
    element = queue.pop
    set.remove(element)

  // keep trying to generate random values until it's not contained in the set
  do
    value = getRandomValue()
  while set.contains(value)

  set.add(value)
  queue.push(value)

  return value

如果阈值很高，您可以将上面的内容反过来：

  • 让集合代表所有不在最后N*T生成的值中的值。
  • 反转所有集合操作（​​将所有集合添加替换为移除，反之亦然，并将集合替换为contains）!contains。

伪代码：

generateNextValue:
  if queue.size >= N*T
    element = queue.pop
    set.add(element)

  // we can now just get a random value from the set, as it contains all candidates,
  //   rather than generating random values until we find one that works
  value = getRandomValueFromSet()
  //do
  //  value = getRandomValue()
  //while !set.contains(value)

  set.remove(value)
  queue.push(value)

  return value

基于洗牌的方法：（比上面的稍微复杂一些）

如果阈值很高，则上述操作可能需要很长时间，因为它可能会继续生成已经存在的值。

在这种情况下，一些基于 shuffle 的方法可能是一个更好的主意。

  • 随机播放数据。
  • 重复处理第一个元素。
  • 这样做时，将其移除并将其插入到 range 中的随机位置[N*T, N]。

例子：

假设 N*T = 5 并且所有可能的值为[1,2,3,4,5,6,7,8,9,10].

然后我们首先洗牌，给我们，比方说，[4,3,8,9,2,6,7,1,10,5]。

然后我们将其删除4并重新插入到范围内的某个索引中[5,10]（比如索引 5）。

然后我们有[3,8,9,2,4,6,7,1,10,5].

并根据需要继续删除下一个元素并将其重新插入。

执行：

如果我们不关心效率，那么数组就可以了——获取一个元素会花费O(n)时间。

为了提高效率，我们需要使用支持有效随机位置插入和第一个位置删除的有序数据结构。首先想到的是（自平衡）二叉搜索树，按索引排序。

我们不会存储实际的索引，索引将由树的结构隐式定义。

在每个节点上，我们将有一个子节点的计数（自身 + 1）（需要在插入/删除时更新）。

插入可以如下完成：（暂时忽略自平衡部分）

// calling function
insert(node, value)
  insert(node, N*T, value)

insert(node, offset, value)
  // node.left / node.right can be defined as 0 if the child doesn't exist
  leftCount = node.left.count - offset
  rightCount = node.right.count

  // Since we're here, it means we're inserting in this subtree,
  //   thus update the count
  node.count++

  // Nodes to the left are within N*T, so simply go right
  // leftCount is the difference between N*T and the number of nodes on the left,
  //   so this needs to be the new offset (and +1 for the current node)
  if leftCount < 0
    insert(node.right, -leftCount+1, value)
  else
    // generate a random number,
    //   on [0, leftCount), insert to the left
    //   on [leftCount, leftCount], insert at the current node
    //   on (leftCount, leftCount + rightCount], insert to the right
    sum = leftCount + rightCount + 1
    random = getRandomNumberInRange(0, sum)
    if random < leftCount
      insert(node.left, offset, value)
    else if random == leftCount
      // we don't actually want to update the count here
      node.count--
      newNode = new Node(value)
      newNode.count = node.count + 1
      // TODO: swap node and newNode's data so that node's parent will now point to newNode
      newNode.right = node
      newNode.left = null
    else
      insert(node.right, -leftCount+1, value)

在当前节点可视化插入：

如果我们有类似的东西：

    4
   /
  1
 / \
2   3

我们想插入5现在的位置1，它会这样做：

  4
 /
5
 \
  1
 / \
2   3

请注意，例如，当红黑树执行操作以保持自身平衡时，这些操作都不涉及比较，因此它不需要知道任何已插入元素的顺序（即索引）。但它必须适当地更新计数。

整体效率将是O(log n)获得一个元素。

于 2013-10-16T11:08:24.757 回答