Randomized Queue 实现 - 随机性的想法
Randomised Queue implementation - ideas for randomness
我正在 coursera 学习算法课程。其中一项作业如下：
Randomized queue. A randomized queue is similar to a stack or queue,
except that the item removed is chosen uniformly at random among items
in the data structure.
我正在尝试找到一种在恒定时间内实现出队（随机删除项目）的方法。我想到了一个想法来做到这一点需要一个双端队列（它支持在恒定时间内从前面和后面删除和添加一个项目）。我的想法是：
- 使用双端队列作为随机队列中的底层数据结构
- Enqueue - 使用库函数生成介于 0 和 1 之间的整数（含 0 和 1）。如果整数为 0，则将该项目添加到双端队列的前面。否则，将其添加到后面。
- 出队 - 任何方向都可以。
随机性发生在入队而不是出队的原因是因为我发现它不是完全随机的（例如 n 对入队的调用将仅 return 第一个或第 n 个项目出队）。因此，为了确保项目被随机移除，我决定将它们随机排列。
这个想法对我来说似乎很好，因为我找不到它的漏洞，但问题是我无法证明我的想法真的有效。我对随机性了解不多。事实上，这只是我第 5 次使用随机数据结构。
我的想法对吗？它会生成随机删除项目的数据结构吗？
由于一致性要求，我认为您提出的方法行不通。均匀性意味着队列中的每个项目都有相同的出队可能性。您的提案总是向其中一端添加元素，并从一端或另一端出队。因此，在任何给定的出队请求中，非结束元素被选中的概率为零。
另一种方法可能是使用基于数组的堆栈。在堆栈的末尾添加元素，但要出队随机选择一个元素，将其与最后一个元素交换，然后将其弹出。这样就会有选择的统一性，所有的组件操作都是常数时间
仅在末端排队不会产生均匀随机的序列。最后一个入队的项目必然在两端，第一个入队的项目更有可能在中间某处而不是在入队其他项目后的两端。
为了说明，以三个项目的集合 {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]
这四种结果是唯一的可能性，而且可能性均等。正如您所看到的，最后一项永远不会在中间，而第一项和第二项都在中间两次。
你想要的是在一个随机的地方出队。但是您不需要保留其他项目的顺序，因为它们是均匀分布的。这意味着您可以将最后一项与随机一项交换，然后将该项出列（成为最后一项）。
我正在 coursera 学习算法课程。其中一项作业如下：
Randomized queue. A randomized queue is similar to a stack or queue, except that the item removed is chosen uniformly at random among items in the data structure.
我正在尝试找到一种在恒定时间内实现出队（随机删除项目）的方法。我想到了一个想法来做到这一点需要一个双端队列（它支持在恒定时间内从前面和后面删除和添加一个项目）。我的想法是：
- 使用双端队列作为随机队列中的底层数据结构
- Enqueue - 使用库函数生成介于 0 和 1 之间的整数（含 0 和 1）。如果整数为 0，则将该项目添加到双端队列的前面。否则，将其添加到后面。
- 出队 - 任何方向都可以。
随机性发生在入队而不是出队的原因是因为我发现它不是完全随机的（例如 n 对入队的调用将仅 return 第一个或第 n 个项目出队）。因此，为了确保项目被随机移除，我决定将它们随机排列。
这个想法对我来说似乎很好，因为我找不到它的漏洞，但问题是我无法证明我的想法真的有效。我对随机性了解不多。事实上，这只是我第 5 次使用随机数据结构。
我的想法对吗？它会生成随机删除项目的数据结构吗？
由于一致性要求，我认为您提出的方法行不通。均匀性意味着队列中的每个项目都有相同的出队可能性。您的提案总是向其中一端添加元素，并从一端或另一端出队。因此，在任何给定的出队请求中，非结束元素被选中的概率为零。
另一种方法可能是使用基于数组的堆栈。在堆栈的末尾添加元素，但要出队随机选择一个元素，将其与最后一个元素交换，然后将其弹出。这样就会有选择的统一性，所有的组件操作都是常数时间
仅在末端排队不会产生均匀随机的序列。最后一个入队的项目必然在两端，第一个入队的项目更有可能在中间某处而不是在入队其他项目后的两端。
为了说明，以三个项目的集合 {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]
这四种结果是唯一的可能性，而且可能性均等。正如您所看到的，最后一项永远不会在中间，而第一项和第二项都在中间两次。
你想要的是在一个随机的地方出队。但是您不需要保留其他项目的顺序，因为它们是均匀分布的。这意味着您可以将最后一项与随机一项交换，然后将该项出列（成为最后一项）。