調換一副牌，交換兩個值後的冗餘

Question

我被要求編寫一套用於洗牌的程序（主要是一種方法）。我寫了下面的程序：

public class Deck { 

//////////////////////////////////////// 
// Data Members 
//////////////////////////////////////// 

private Card[] cards; // array holding all 52 cards 
private int cardsInDeck; // the current number of cards in the deck 

public static final int DECK_SIZE = 52; 

/** 
* Shuffles the deck (i.e. randomly reorders the cards in the deck). 
*/ 
public void shuffle() { 
    int newI; 
    Card temp; 
    Random randIndex = new Random(); 

    for (int i = 0; i < cardsInDeck; i++) { 

     // pick a random index between 0 and cardsInDeck - 1 
     newI = randIndex.nextInt(cardsInDeck); 

     // swap cards[i] and cards[newI] 
     temp = cards[i]; 
     cards[i] = cards[newI]; 
     cards[newI] = temp; 
    } 
} 

} 

但在這是如下上述洗牌方法的邏輯錯誤：假設我更換卡號4卡號42，那麼我換 兩次。我想知道有沒有辦法不這樣做？

我籤一個崗位在這裏：Shuffling a deck of cards

但它並沒有道理給我。

Answer 1

我想知道一個片段是存在的不這樣做什麼辦法？

絕對。而不是用其他換一張卡，只需將一張卡換成以後的即可。

所以在任何時候，你真的從「尚未挑選的所有剩餘卡片」中挑選哪張卡片將在i插槽中。它的概念上是相當於從一張卡片開始，隨機取出卡片放置在新的洗牌集合中。事實上，在你做這些事情時你實際上交換了位置是無關緊要的，因爲在任何時候你都會從其餘的位置隨機抽取。

閱讀Wikipedia article on the Fisher-Yates shuffle瞭解更多信息。

（有些實現從年底掉，所以元素x被交換與範圍[0, x]隨機元素。這相當於我的描述，只是鏡像。我個人覺得更容易想到的第一部分集合在任何時候都是混洗部分，但這是我的失敗，而不是固有的差異。）

另外請記住，如果您使用List<Card>，則可以使用Collections.shuffle並避免必須爲此寫下代碼。

Answer 2

您可以比較Collections.shuffle您的實現，一個絕對作品的權利，這是來自SRC

// Shuffle array 
    for (int i=size; i > 1; i--) 
     swap(arr, i-1, rnd.nextInt(i)); 

... 

    private static void swap(Object[] arr, int i, int j) { 
     Object tmp = arr[i]; 
     arr[i] = arr[j]; 
     arr[j] = tmp; 
    } 

Answer 3

有時，洗牌的最佳方式是而不是洗牌。由於您已經知道如何使用隨機數字，因此您可以對Fisher-Yates隨機播放卡進行修改，以隨機順序提取卡片，無需重複播放，所有這些都不需要初始排序。

想象一下這些物理條件（使用真正的一副紙牌時）。不要在前面洗牌，然後連續抽出頂牌，只需按照排序順序離開牌組，然後每次從隨機位置抽出一張牌。

查看here瞭解如何工作的完整說明，但我會介紹從下面的1到9中提取三個數字。

---

開始與（unshuffled）列表{1,2,3,4,5,6,7,8,9}（長度9，很明顯），並生成基於該長度的隨機數（從0到8以下，假設我們使用基於零的索引，其中Java那樣） 。假設第一個隨機數是4.

然後，您將該項目保存在位置編號4（即5），並將列表中的_last項目（9）移動到該位置，將長度減1。這給你{1,2,3,4,9,6,7,8}長度爲8.

然後再次使用基於長度（0到7）的隨機數返回第二個數字。在這種情況下，我們會得到隨機數1

該項目在偏移1 2，我們再調整名單相同的第一步，給{1,8,3,4,9,6,7}與7

長度現在，讓我們說我們得到第三個隨機數，基於7的當前長度，它恰好是4。該項目現在是9，所以我們返回，修改列表後成爲{1,8,3,4,7,6}長度爲6.

您應該能夠看到這是如何發展。不用擔心預先排序整個列表，您可以實現隨機序列（就像隨機數字生成器允許的隨機序列），無需重複。