随机化队列实现-随机化思想

Question

我正在Coursera学习算法课程。其中一项任务如下：

随机队列。随机化队列类似于堆栈或队列，不同之处在于移除的项是在数据结构中的项之间统一随机选择的。

我试图找到一种方法，在固定的时间内实现出列（随机删除项目）。我想到了一个主意，就是重新要求一个deque（它支持在固定时间内从前面和后面删除和添加一个项目）。我的想法如下：

• 在随机化队列中使用deque作为底层数据结构
• 加入-使用库函数生成0到1之间的整数。如果整数为0，则将项目添加到deque的前面。否则，将其添加到后面。
• 出发-任何方向都可以。

随机性发生在排队中而不是在出列中的原因是，我发现它不是完全随机的（例如，对排队的n个调用将使出列只返回第一个或第n个项目）。所以为了确保这些物品被随机移除，我决定将它们随机排队。

这个想法对我来说似乎很好，因为我找不到其中的漏洞，但问题是我无法证明我的想法真的有效。我对随机性知之甚少。事实上，这只是我第五次使用随机数据结构。

我的想法对吗？它会生成一个随机删除项的数据结构吗？

Answer 1

我不认为你提议的方法会起作用，因为一致性要求。一致性意味着队列中的每个项目都有相等的退出队列的可能性。您的建议总是在其中一端添加元素，并从一端或另一端退出。因此，在任何给定的退出请求中，非结束元素被选择的可能性为零。

另一种方法可能是使用基于数组的堆栈。在堆栈的末尾添加元素，但要退出队列，请随机选择一个元素，将其与最后一个元素交换，然后将其弹出。这将具有选择的一致性，并且所有组件操作都是恒定时间。

Answer 2

仅在末端排队不会产生均匀随机序列。最后一个要排队的项目必然在两端，排队后第一个要排队的项目更有可能在中间的某个地方，而不是在其他项目的两端。

举例来说，以三个项目集{1,2,3}为例，这是不导致均匀分布的最小集合。按该顺序将其排队将产生以下可能结果（括号中是下一项排队的位置）。

[1] -> (front) -> [1, 2] -> (front) -> [1, 2, 3]
[1] -> (front) -> [1, 2] -> (back) -> [3, 1, 2]
[1] -> (back) -> [2, 1] -> (front) -> [2, 1, 3]
[1] -> (back) -> [2, 1] -> (back) -> [3, 2, 1]

这四个结果是唯一的可能性，并且都具有同等的可能性。正如你所看到的，最后一个项目从来没有在中间，而第一个项目和第二个项目都在中间两次。

你想要的是在一个随机的地方排队。但是您不需要保留其他项的顺序，因为它们是均匀分布的。这意味着您可以将最后一个项目与随机项目交换，然后将该项目（成为最后一个项目）出列。