>想象一个标准的置换函数，它接受一个整数，并以随机排列的方式返回前 N 个自然数的向量。如果你只需要其中的k(<= N)，但事先不知道k，你还需要执行排列的O(N)生成吗？有没有比以下更好的算法：
for x in permute(N):
if f(x):
break
我正在想象一个 API，例如：
p = permuter(N)
for x = p.next():
if f(x):
break
其中初始化为 O(1)(包括内存分配)。
这个问题通常被视为两种竞争算法之间的选择：
-
策略 FY：费舍尔-耶茨洗牌的变体，其中对每个所需数字执行一个洗牌步骤，以及
-
策略HT：将所有生成的数字保存在哈希表中。在每一步中，都会生成随机数，直到找到不在哈希表中的数字。
选择取决于k和N之间的关系：如果k足够大，则使用策略 FY;否则，使用策略 HT。其论点是，如果k相对于n而言很小，那么维护大小n数组是浪费空间，并且会产生很大的初始化成本。另一方面，随着k的临近n越来越多的随机数需要被丢弃，并且最终产生新值的速度将非常缓慢。
当然，您可能事先不知道将请求的样品数量。在这种情况下，您可能会悲观地选择FY，或者乐观地选择HT，并希望最好。
事实上，并没有真正的需要权衡，因为 FY 算法可以通过哈希表有效地实现。无需初始化N整数数组。相反，哈希表仅用于存储数组中值与其索引不对应的元素。
(以下描述使用基于 1 的索引;这似乎是问题要查找的内容。希望它不会充满逐一错误。因此，它会生成[1, N]范围内的数字。从这里开始，我使用k来表示迄今为止请求的样本数量，而不是最终将请求的数量。
在增量 FY 算法的每个点，从范围[k, N]中随机选择一个索引r。然后交换索引k和r处的值，之后k递增以进行下一次迭代。
作为效率点，请注意，我们实际上并不需要进行交换：我们只需在r处产生值，然后将r处的值设置为k处的值。我们再也不会查看索引k的值，因此没有必要更新它。
最初，我们使用哈希表模拟数组。要查找(虚拟)数组中索引i处的值，我们查看哈希表中是否存在i：如果是，那就是索引i处的值。否则，索引i处的值将i自身。我们从一个空哈希表(节省初始化成本)开始，它表示一个数组，其每个索引的值都是索引本身。
为了进行 FY 迭代，对于每个示例索引k，我们生成一个随机索引r如上所述，生成该索引处的值，然后将索引r处的值设置为索引k处的值。这正是上述 FY 的过程，除了我们查找值的方式。
这需要两次哈希表查找，一次插入(在已经查找的索引处，理论上可以更快地完成)，并且每次迭代都会生成一次随机数。这比策略 HT 的最佳情况多了一个查找，但我们有一点节省，因为我们永远不需要循环来产生价值。(当我们重新散列时，还有另一个小的潜在节省，因为我们可以删除任何小于当前值的键k。
随着算法的进行，哈希表将增长;使用标准的指数重新哈希策略。在某些时候，哈希表将达到N-k个整数向量的大小。(由于哈希表开销，该点将以远小于N的值达到k，但即使没有开销，此阈值也会在N/2时达到。此时，哈希不是重新散列，而是用于创建现在非虚拟数组的尾部，此过程比重新散列花费的时间更少，并且永远不需要重复;其余样本将使用标准增量 FY 算法进行选择。
如果k最终达到阈值点，则此解决方案比 FY 稍慢，如果k永远不会大到足以拒绝随机数，则此解决方案比 HT 稍慢。但无论哪种情况，它都不会慢多少，如果从来没有遭受病理性减速，当k有一个尴尬的价值时。
如果不清楚，这里有一个粗略的Python实现：
from random import randint
def sampler(N):
k = 1
# First phase: Use the hash
diffs = {}
# Only do this until the hash table is smallish (See note)
while k < N // 4:
r = randint(k, N)
yield diffs[r] if r in diffs else r
diffs[r] = diffs[k] if k in diffs else k
k += 1
# Second phase: Create the vector, ignoring keys less than k
vbase = k
v = list(range(vbase, N+1))
for i, s in diffs.items():
if i >= vbase:
v[i - vbase] = s
del diffs
# Now we can generate samples until we hit N
while k <= N:
r = randint(k, N)
rv = v[r - vbase]
v[r - vbase] = v[k - vbase]
yield rv
k += 1
注意：N // 4可能是悲观的;计算正确的值需要对哈希表实现了解太多。如果我真的关心速度，我会用编译语言编写自己的哈希表实现，然后我就会知道:)