在 O(1) 空间中从流中选择随机项

使用恒定空间以均匀概率从流中随机选择一个项目

该流提供以下操作：

class Stream:

  def __init__(self, data):
    self.data = list(data)

  def read(self):
    if not self.data:
      return None

    head, *self.data = self.data
    return head

  def peek(self):
    return self.data[0] if self.data else None

流中的元素（因此元素data）的大小恒定，并且它们都不是None, so None信号流结束。流的长度只能通过消耗整个流来了解。请注意，计算元素数量会消耗O(log n) space.

我相信没有办法均匀地使用以下命令从流中随机选择一个项目O(1) space.

任何人都可以证明这一点吗？

为每个元素生成一个随机数，并记住数字最小的元素。

这是我最喜欢的答案，但您可能正在寻找的答案是：

如果流是N项目长，则返回的概率Nth项目是1/N。因为这个概率对于每个N，任何能够完成这个任务的机器在读取不同长度的流后都必须进入不同的状态。由于可能的长度数量是无限的，因此所需的可能状态的数量也是无限的，并且机器将需要无限量的内存来区分它们。