用於N個整數的隨機置換的在線算法

Question

想象一下，一個標準置換函數需要一個整數並返回一個隨機置換中前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）（包括內存分配）。

Answer 1

這個問題經常兩個競爭的算法之間視爲選擇：

• 策略FY：上，其中對於每個期望數量的執行一個混洗步驟費 - 耶茨洗牌的變種，和

• 策略HT：將所有生成的數字保存在散列表中。在每一步中，都會產生隨機數字，直到找到不在散列表中的數字。

的選擇取決於k和N之間的關係進行的：如果k是足夠大，則策略FY被使用;否則，策略HT。我們的觀點是，如果k相對於n較小，則維護一個大小爲n的數組會浪費空間，並且會產生較大的初始化成本。另一方面，隨着k接近n越來越多的隨機數字需要被丟棄，並且最終產生新的數值將會非常緩慢。

當然，您可能並不知道將要求的樣本數量。在這種情況下，你可能會悲觀地選擇FY，或樂觀地選擇HT，並希望最好。

事實上，沒有真正需要權衡，因爲FY算法可以通過散列表高效地執行。不需要初始化整數的數組。相反，散列表僅用於存儲數組的值與其索引不一致的元素。

（以下描述使用了基於1的索引;這似乎是問題所在，希望它沒有填滿偏移錯誤，因此它生成的數字範圍爲[1, N]。 ，我使用k作爲迄今爲止請求的樣本數量，而不是最終要求的樣本數量。）

在增量風雲算法的每個點上，從範圍中隨機選擇單個索引r[k, N]。然後交換k和r索引處的值，之後k遞增以進行下一次迭代。

作爲一個效率點，請注意我們並不需要進行交換：我們只需產生r的值，然後將r處的值設置爲k處的值。我們不會再看索引k的值，所以沒有意義更新它。

最初，我們用哈希表模擬數組。要查找（虛擬）數組中的索引i的值，我們看看散列表中是否存在i：如果是這樣，那就是索引i處的值。否則，指數i處的值爲i本身。我們從一個空的哈希表開始（這節省了初始化成本），它表示一個數組，其索引本身就是索引本身。

要做到FY迭代中，針對每個樣本索引k我們生成如上述隨機索引r，該索引處產生的值，然後在索引k在索引r的值設置爲的值。除了我們查找數值的方式外，這正是上述FY所描述的過程。

這需要恰好兩個哈希表查找，一個插入（在已經查找的索引處，理論上可以更快地完成）以及每次迭代生成一個隨機數。這比戰略HT的最佳案例多一個查找，但是我們有一點省錢，因爲我們從不需要循環來產生一個值。 （由於我們可以丟棄小於當前值k的任何密鑰，因此我們重新散列時會節省另一個小的潛力。）

隨着算法的進行，哈希表將會增長;使用標準的指數重新哈希策略。在某些時候，哈希表將達到整數的向量大小。 （由於散列表的開銷，這個點將會達到k的值，遠小於N，但即使沒有開銷，這個閾值也會達到N/2。）在這一點上，不是重新哈希，而是使用散列創建現在非虛擬數組的尾部，這個過程比重複使用花費更少的時間，並且永遠不需要重複;剩餘的樣本將使用標準增量風雲算法進行選擇。

如果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可能是悲觀的;計算正確的值需要了解太多關於哈希表的實現。如果我真的關心速度，我會用編譯語言編寫自己的散列表實現，然後我知道:)