Psuedo隨機遍歷一組

Question

我一直在閱讀遊戲編碼完成（第4版）和我有幾個問題，理解「僞隨機遍歷一組」路徑在「抓包袋有用的東西」在第三章第3節

你有沒有想過如何在‘你的CD播放機隨機作品’按鈕？它會隨機播放CD上的每首歌曲，而不會播放同一首歌曲兩次。這是一個非常有用的解決方案，可以確保遊戲中的玩家在有機會再次看到相同的遊戲之前，看到最多種類的功能，例如對象，效果或角色。

在描述之後，它繼續討論我試圖用Java實現的C++實現，但一直無法成功複製。它也簡要描述了它是如何工作的，但我也不明白。

我找到了this StackOverflow對類似問題的回答，但不幸的是，答案中的示例鏈接已死亡，我也不理解維基百科文章，儘管關於它所做的描述似乎描述了我尋找。

要清楚，我是而不是正在尋找一種隨機重新排序集合的方式。我正在尋找一種方法在重複之前從集合中隨機選擇一個元素。

有人可以解釋這種行爲是如何工作的並在Java中提供一個例子嗎？謝謝！

[編輯]我想這可能是有用的，在這裏有一個執行摘錄來幫助解釋我在說什麼。

這是它的工作原理。通過選擇三個大於零的隨機值來計算跳過值。這些值成爲二次係數，和域值（x）被設定爲所述組的順序值：

Skip = RandomA * (members * members) + (RandomB * members) + RandomC 

武裝與此跳過值，則可以使用這一段代碼遍歷整個集合恰好一次，以僞隨機順序：

nextMember += skip; 
nextMember %= prime; 

跳躍的值是如此比你的組所選擇的val的成員的數目大得多你似乎隨意跳過。當然，這段代碼是在一個while循環中，以便捕獲所選值大於您的集合但仍小於素數的情況。

Answer 1

下面是什麼，這看起來像在得到一組字符的隨機排列的情況下，例如：

public static void main(String[] args) { 
    // Setup 
    char[] chars = { 'a', 'b', 'c', 'd', 'e', 'f', 'g', 'h', 'i', 'j' }; 
    int prime = 11; // MUST be greater than the length of the set 
    int skip = 0; 
    int nextMember = 0; 

    // If the skip value is divisible by the prime number, we will only access 
    // index 0, and this is not what we want. 
    while (skip % prime == 0) { 
     // Generate three random positive, non-zero numbers 
     int ra = new Random().nextInt(prime) + 1; 
     int rb = new Random().nextInt(prime) + 1; 
     int rc = new Random().nextInt(prime) + 1; 
     skip = ra * chars.length * chars.length + rb * chars.length + rc; 
    } 

    String result = ""; 
    for (int x = 0; x < chars.length; x++) { 
     do { 
      nextMember += skip; 
      nextMember %= prime; 
     } while (nextMember <= 0 && nextMember > chars.length); 
     result += chars[nextMember - 1]; 
    } 

    // Print result 
    System.out.println(result); 
} 

大多數的例子，從預訂的情況出現在上面的代碼示例，但有一些例外。首先，如果跳過是素數整除，比這個算法並不因爲它只會訪問索引0由於這部分代碼的工作：

  nextMember += skip; 
      nextMember %= prime; 

其次，三個係數是在在1和素數的範圍之間，包括在內，但不一定是這種情況。它可以是任何正數，非零數字，但我發現如果我這樣做，我會有整數溢出，並得到一個負值跳過值，這是行不通的。這個特殊情況可以通過取跳躍值的絕對值來修正。

最後，您需要檢查下一個成員是否爲1和包含集合的長度之間的數字，然後讓索引中的成員小於1。如果你不這樣做（如果你只檢查數字是否小於該集合的長度），那麼每當你運行這個數組時，你將在數組的第一個元素結束時結束程序，這對於隨機遍歷來說是有趣但不期望的。

該程序將選擇一個不同的索引，直到所有索引被訪問，然後它會重複。當它重複時，將產生相同的排列（這是它應該如何工作的），所以如果我們想要一個不同的排列，你需要計算一個新的跳躍值。該程序由於二次方程和素數的性質而起作用。我不能詳細解釋它，而不會懷疑我在說什麼，並且本書中已經存在或多或少類似的描述。

我已經在3和5個字符的集合上運行了這個程序的稍微修改過的版本。對於兩者來說，每個置換均勻地出現，平均絕對差異分別爲0.0413％和0.000000466726％，與平均分配的平均預期次數相比。兩者都生產6000萬個樣品。產生字符重複的排列。

Answer 2

隨機從集合中選擇非重複的元件是相同的混洗並從混洗列表順序選擇。

shuffled = shuffle(my_list); 
first = pop(shuffled); 
second = pop(shuffled); 

Answer 3

，我只想通過將原始列表的成員在隨機位置，像這樣創建列表的副本：

List<T> randomOrder = new ArrayList<T>(original.size()); 
Random rand = new Random(); 
int currentSize = 0; 
for (T member : original) { 
    randomOrder.add(rand.nextInt(++currentSize), member); 
} 

所以randomOrder應該成爲原始列表的副本，但採用不同的隨機順序。原始列表不會受到影響。 （與你的列表的類型替換T，很明顯。）

Answer 4

下面是一個例子：

import java.util.*; 

public class Randy { 

    public static void main(String[] args) { 
     ArrayList<String> list = new ArrayList<String>(); 
     ArrayList<String> copy = new ArrayList<String>(); 
     list.add("Jack"); 
     list.add("Tess"); 
     list.add("Alex"); 
     list.add("Jeff"); 
     list.add("Kelli"); 
     Random randy = new Random(); 
     int size = list.size(); 
     for(int i = 0; i < size; i++) { 
      int r = randy.nextInt(list.size()); 
      System.out.println(list.get(r)); 
      copy.add(list.get(r)); 
      list.remove(r); 
     } 
     list = copy; 
     copy.clear(); 
    } 

} 

在這裏，我有由字符串對象的ArrayList列表。然後在for循環中，我以隨機順序打印出這些字符串，並從列表中刪除隨機選擇的元素，因此沒有重複的輸出。但在刪除元素之前，我將它添加到其他ArrayList中，複製，所以我不會完全丟失元素。在最後我將列表設置爲等於複製，並且所有內容都已恢復，並且您可以一遍又一遍地重複此過程。

Answer 5

該算法實際上離隨機或隨機查找很遠。

此方法只是跳過％prime的週期，然後刪除位於array.length之外的所有值。

有了小的素數，你可以很容易地辨認出模式：

裝滿[0, 1, 2, 3..., 9]數組你，選擇係數3，5，7 - 11黃金，我們得到的753但是跳躍，753 % 11爲5 ，所以實際的步長爲5

結果（使用您的實現）是

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

我們可以看到這裏的步驟：

+5，-6，+5，-6，+5，-6，+5，-6，+5

（-6來自（x + 5）％11，其中6 < = x < = 10與x - 6相同）

無論您選擇哪個號碼，都會看到此模式。