5

I was asked to write a program(mainly a method) for shuffling a deck of cards. I wrote the following program:

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

}

But there is a logical error in the above shuffle method which is as follows: Suppose I replace Card Number 4 with Card Number 42, then I'm swapping two times. I'm wondering is there any way of not doing this?

I checked one post here :Shuffling a deck of cards

But it didn't make sense to me.

4

3 回答 3

15

我想知道有没有办法不这样做？

绝对地。无需将一张卡与任何其他卡交换，只需将一张卡与另一张卡交换即可。

因此，在任何时候，您实际上都是i从尚未选择的“所有剩余卡”中选择哪张卡将在插槽中。它在概念上等同于从一张卡片列表开始，然后随机移除卡片以放入新的洗牌集合中。您实际上在交换位置这一事实是无关紧要的，因为在任何时候您都会从剩余的插槽中随机选择。

阅读有关 Fisher-Yates shuffle 的 Wikipedia 文章以获取更多信息。

（一些实现从末尾交换，因此元素x与 range 中的随机元素交换[0, x]。这相当于我所描述的，只是镜像。就我个人而言，我发现将集合的第一部分视为洗牌部分更容易任何一点，但这是我的失败，而不是固有的差异。）

另请记住，如果您使用 a List<Card>，则可以使用Collections.shuffle并完全避免为此编写代码。

于 2013-05-01T06:21:58.313 回答
7

您可以将您的实现与 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;
    }
于 2013-05-01T06:21:57.053 回答
5

有时，洗牌的最好方法是不洗牌。由于您已经知道如何使用随机数，您可以使用对 Fisher-Yates 洗牌的修改以随机顺序提取卡片，没有重复，所有这些都没有初始排序。

用这些物理术语来考虑它（使用真正的一副纸牌时）。与其将牌堆放在前面，然后不断地抽出最上面的牌，不如让牌堆按排序顺序排列，每次从随机位置抽出一张牌。

有关其工作原理的完整说明，请参见此处，但我将在下面介绍从 1 到 9 提取三个数字。

从（未洗牌的）列表{1,2,3,4,5,6,7,8,9}（显然是长度为 9）开始，并根据该长度生成一个随机数（从 0 到 8 包括在内，假设我们使用从零开始的索引，Java 就是这样做的）。假设第一个随机数是 4。

然后将项目保存在位置编号 4（即5）并将列表中的 _last 项目 ( 9) 移动到该位置，将长度减一。这为您{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 后返回它。

您应该能够看到这是如何发展的。无需担心预先对整个列表进行排序，您可以实现无重复的随机序列（当然，只要您的随机数生成器允许的随机）。

于 2013-05-01T06:27:49.220 回答