不先随机排序，随机排出元素列表

Question

如果我有一个包含10K个元素的列表，我想随机遍历它们，有没有一种算法可以让我随机访问每个元素，而不是先随机排序?

换句话说，这不是理想的:

const sorted = list
              .map(v => [math.random(), v])
              .sort((a,b) => a[0]- b[0]);

最好避免sort调用和映射调用。我唯一的想法是将所有内容存储在哈希映射中，并以某种方式随机访问哈希键?虽然这只是回到了同样的问题，是。

Answer 1

我刚刚玩了一下，发现Fisher-Yates洗牌法在"在线"上运行得很好。例如，如果你有一个大的列表，你不需要花时间在开始迭代项之前对整个列表进行洗牌，或者，同样地，你可能只需要从一个大列表中取出几个项。

我在问题中没有看到语言标签，所以我选择Python。

from random import randint
def iterrand(a):
    """Iterate over items of a list in a random order.
    Additional items can be .append()ed arbitrarily at runtime."""
    for i, ai in enumerate(a):
        j = randint(i, len(a)-1)
        a[i], a[j] = a[j], ai
        yield a[i]

这是列表长度中的O(n)，通过允许.append() s (Python中的O(1))，可以在后台构建列表。

一个例子是:

l = [0, 1, 2]
for i, v in enumerate(iterrand(l)):
    print(f"{i:3}: {v:<5} {l}")
    if v < 4:
        l.append(randint(1, 9))

可能产生如下输出:

  0: 2     [2, 1, 0]
  1: 3     [2, 3, 0, 1]
  2: 1     [2, 3, 1, 1, 0]
  3: 0     [2, 3, 1, 0, 1, 3]
  4: 1     [2, 3, 1, 0, 1, 3, 7]
  5: 7     [2, 3, 1, 0, 1, 7, 7, 3]
  6: 7     [2, 3, 1, 0, 1, 7, 7, 3]
  7: 3     [2, 3, 1, 0, 1, 7, 7, 3]
  8: 2     [2, 3, 1, 0, 1, 7, 7, 3, 2]
  9: 3     [2, 3, 1, 0, 1, 7, 7, 3, 2, 3]
 10: 2     [2, 3, 1, 0, 1, 7, 7, 3, 2, 3, 2]
 11: 7     [2, 3, 1, 0, 1, 7, 7, 3, 2, 3, 2, 7]

更新:为了测试正确性，我会这样做:

# trivial tests
assert list(iterrand([])) == []
assert list(iterrand([1])) == [1]
# bigger uniformity test
from collections import Counter
# tally 1M draws
c = Counter()
for _ in range(10**6):
    c[tuple(iterrand([1, 2, 3, 4, 5]))] += 1
# ensure it's uniform
assert all(7945 < v < 8728 for v in c.values())
# above constants calculated in R via:
#   k<-120;p<-0.001/k;qbinom(c(p,1-p), 1e6, 1/k))

Answer 2

Fisher-Yates应该做得很好，这篇文章真的很好:https://medium.com/@oldwestaction randomness-is-hard-e085decbcbb2

相关的JS代码非常简短:

const fisherYatesShuffle = (deck) => {
  for (let i = deck.length - 1; i >= 0; i--) {
    const swapIndex = Math.floor(Math.random() * (i + 1));
    [deck[i], deck[swapIndex]] = [deck[swapIndex], deck[i]];
  }
  return deck
}

生成结果，这样就不必遍历列表两次，使用如下生成器函数:

const fisherYatesShuffle = function* (deck) {
    for (let i = deck.length - 1; i >= 0; i--) {
        const swapIndex = Math.floor(Math.random() * (i + 1)); // * use ;
        [deck[i], deck[swapIndex]] = [deck[swapIndex], deck[i]];
        yield deck[i];
    }
};

(注意不要忘记一些分号，当下一行是括号符号时)。