惰性洗牌算法

我有一个很大的元素列表，我想以随机顺序迭代它们。但是，我无法修改该列表，也不想创建它的副本，因为 1) 它很大，2) 可以预期迭代会提前取消。

List<T> data = ...;
Iterator<T> shuffled = shuffle(data);
while (shuffled.hasNext()) {
    T t = shuffled.next();
    if (System.console().readLine("Do you want %s?", t).startsWith("y")) {
        return t;
    }
}
System.out.println("That's all");
return t;

我正在寻找一种算法，上面的代码可以在O(n)（并且最好只需要O(log n)space），因此缓存之前生成的元素不是一种选择。我不在乎算法是否有偏见（只要它不明显）。

（我在问题中使用了伪Java，但如果您愿意，也可以使用其他语言）

这是迄今为止我得到的最好的。

Iterator<T> shuffle(final List<T> data) {
    int p = data.size();
    while ((data.size() % p) == 0) p = randomPrime();
    return new Iterator<T>() {
        final int prime = p;
        int n = 0, i = 0;
        public boolean hasNext() { return i < data.size(); }
        public T next() {
            i++; n += prime;
            return data.get(n);
        }
    }
}

迭代中的所有元素O(n)，恒定空间，但显然有偏差，因为它只能产生data.size()排列。

我所知道的最简单的洗牌方法与索引一起使用。如果List不是一个ArrayList，如果您尝试使用以下之一（aLinkedList确实有一个get通过 ID，但它是 O(n)，所以你最终会得到 O(n^2) 时间）。

如果 O(n) 空间没问题（我假设不是），我会推荐费舍尔-耶茨/高德纳洗牌，时间复杂度为 O(n)，并且易于实现。您可以对其进行优化，这样您只需执行单个操作即可获取第一个元素，但您需要随时跟踪修改后的列表的其余部分。

我的解决方案：

好吧，所以这根本不是很随机，但如果你想要小于 O(n) 的空间，我看不到更好的方法。

它需要 O(1) 空间和 O(n) 时间。

可能有一种方法可以稍微提高空间使用量并获得更多随机结果，但我还没有弄清楚。

这与相对素数。这个想法是，给定 2 个相对素数a（发电机）和b，当你循环通过a % b, 2a % b, 3a % b, 4a % b，...，您将看到每个整数 0、1、2、...、b-2、b-1，并且这也会在看到任何整数两次之前发生。不幸的是，我没有证明的链接（维基百科链接可能提到或暗示它，我没有检查太多细节）。

我首先增加长度，直到得到一个素数，因为这意味着任何其他数字都将是相对素数，这限制要少得多（并且只需跳过任何大于原始长度的数字），然后生成一个随机数数，并将其用作生成器。

我正在迭代并打印出所有值，但应该很容易修改以在给定当前值的情况下生成下一个值。

注意我正在跳过1 and len-1和我的nextInt，因为这些会产生1,2,3,... and ...,3,2,1分别，但您可以包含这些，但如果长度低于某个阈值，则可能不会包含这些。

您可能还想生成一个随机数，将生成器乘以（模长度）作为起始值。

Java代码：

static Random gen = new Random();

static void printShuffle(int len)
{
  // get first prime >= len
  int newLen = len-1;
  boolean prime;
  do
  {
     newLen++;
     // prime check
     prime = true;
     for (int i = 2; prime && i < len; i++)
        prime &= (newLen % i != 0);
  }
  while (!prime);

  long val = gen.nextInt(len-3) + 2;
  long oldVal = val;
  do
  {
     if (val < len)
        System.out.println(val);
     val = (val + oldVal) % newLen;
  }
  while (oldVal != val);
}