Lazy Shuffle算法

Question

我有一大堆我想按隨機順序迭代的元素。但是，我不能修改列表，也不想創建它的副本，因爲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)空間），所以高速緩存被較早產生的不是一個選項的元素。我不關心算法是否有偏差（只要它不明顯）。

（我使用假的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()排列。

Answer 1

我知道與索引一起工作的最簡單的洗牌方法。如果List不是ArrayList，如果您嘗試使用下面的其中一個（LinkedList確實有一個ID爲get，但它是O（n），那麼最終的算法效率會非常低，所以您最終會得到O（n^2）時間）。

如果O（n）空間很好，我假設它不是，我建議Fisher-Yates/Knuth shuffle，這是O（n）時間，很容易實現。您可以優化它，因此您只需要在獲取第一個元素之前執行單個操作，但是您需要隨時跟蹤修改後的列表的其餘部分。

我的解決辦法：

好了，這是不是很隨意可言，但我不能看到一個更好的方式，如果你要小於O（n）的空間。

它需要O（1）空間和O（n）時間。

可能有辦法將它的使用量稍微增加一些，並得到更多的隨機結果，但我還沒有想到。

它與relative primes有關。這個想法是，當你通過a % b,2a % b,3a % b,4a % b，...循環時，你會看到每個整數0,1,2，...，並且給出2個相對的素數a（發生器）和b。，b-2，b-1，並且在看到任何整數兩次之前也會發生這種情況。不幸的是，我沒有鏈接到一個證明（維基百科鏈接可能會提及或暗示它，我沒有檢查太多細節）。

我從增加長度開始，直到我們得到一個素數，因爲這意味着任何其他數字都將是一個相對的素數，這是一個很小的限制（並且跳過任何大於原始長度的數字），然後生成一個隨機數，並將其用作生成器。

我遍歷並打印出所有的值，但它應該很容易修改，以生成下一個給定的當前值。

注意我跳過1和len-1我nextInt，因爲這些東西會分別產生1,2,3,...和...,3,2,1，但你可以包括這些，但可能不是如果長度低於某一閾值。

您可能還想生成一個隨機數乘以發生器（mod長度）以開始。

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); 
} 

Answer 2

您可以嘗試使用緩衝區來執行此操作。迭代一組有限的數據並將其放入緩衝區。從該緩衝區提取隨機值並將其發送到輸出端（或任何您需要的地方）。迭代下一組並覆蓋這個緩衝區。重複這一步。

您將以n + n操作結束，這仍然是O（n）。不幸的是，結果實際上並不是隨機的。如果您正確選擇了緩衝區大小，它將接近於隨機數。

在不同的音符，檢查這兩個：Python - run through a loop in non linear fashion，random iteration in Python

也許有一個更優雅的算法來做到這一點更好。雖然我不確定。期待在這個線程中的其他答覆。

Answer 3

這是不是一個完美的回答你的問題，但也許是有用的。

的想法是使用可逆的隨機數發生器和懶惰地完成的，基於陣列通常混洗算法：得到i「個混洗產品，交換a[i]與和一個隨機選擇的a[j]其中j是在[i..n-1]，然後返回a[i]。這可以在迭代器中完成。

完成迭代後，通過使用RNG反方向的「無刷」重置數組爲原始順序。

非混洗重置永遠不會比原始迭代花費更多時間，因此它不會改變漸近成本。迭代次數仍然是線性的。

如何構建可逆RNG？只需使用加密算法。加密先前生成的僞隨機值繼續前進，解密後退。如果你有一個對稱的加密算法，那麼你可以在每一步向前添加一個「鹽」值，以防止循環爲2，並且爲每一步向後減去它。我提到這一點是因爲RC4簡單，快速和對稱。我之前用它來完成這樣的任務。加密4字節值然後計算mod以使它們處於期望的範圍內確實很快。

您可以通過擴展Iterator來將其壓入Java迭代器模式以允許重置。見下文。用法如下：

ShuffledList<Integer> lst = new SuffledList<>(); 

... build the list with the usual operations 

ResetableInterator<Integer> i = lst.iterator(); 
while (i.hasNext()) { 
    int val = i.next(); 

    ... use the randomly selected value 

    if (anyConditinoAtAll) break; 
} 
i.reset(); // Unshuffle the array 

我知道這並不完美，但它會很快，並給予很好的洗牌。請注意，如果您不需要reset，則下一個迭代器仍將是一個新的隨機洗牌，但原始順序將永遠丟失。如果循環體可以生成異常，則需要在finally塊中重置。

class ShuffledList<T> extends ArrayList<T> implements Iterable<T> { 

    @Override 
    public Iterator<T> iterator() { 
     return null; 
    } 

    public interface ResetableInterator<T> extends Iterator<T> { 
     public void reset(); 
    } 

    class ShufflingIterator<T> implements ResetableInterator<T> { 

     int mark = 0; 

     @Override 
     public boolean hasNext() { 
      return true; 
     } 

     @Override 
     public T next() { 
      return null; 
     } 

     @Override 
     public void remove() { 
      throw new UnsupportedOperationException("Not supported."); 
     } 

     @Override 
     public void reset() { 
      throw new UnsupportedOperationException("Not supported yet."); 
     } 
    } 
}