在交换两个值后,洗牌一副卡,冗余

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

}

但是上面的shuffle方法存在一个逻辑错误,如下所示:假设我将卡号4替换为卡号42,然后我交换了两次.我想知道有没有办法不这样做？

我在这里查了一篇帖子:洗牌一副牌

但这对我来说没有意义.

Answer 1

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

绝对.而不是将一张卡与任何其他卡交换,只需将一张卡与后一张卡交换即可.

所以在任何一点上,你真的会选择哪张卡片i将从"尚未挑选的所有剩余卡片"中插入.它在概念上等同于从一个卡片列表开始,并随机移除卡片以放置在新的洗牌集合中.实际上,当您正在进行交换时,实际上是在交换位置这一事实无关紧要,因为在任何时候您都会从剩余的插槽中随机选择.

有关更多信息,请阅读有关Fisher-Yates shuffle的维基百科文章.

(有些实现从末尾交换,所以元素x与范围内的随机元素交换[0, x].这相当于我所描述的,只是镜像.我个人觉得更容易将集合的第一部分视为洗牌部分任何一点,但这是我的失败而不是固有的差异.)

另外请记住,如果您使用a 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 shuffle的修改以随机顺序提取卡片,无需重复,无需初始排序.

从这些物理术语中考虑它(当使用真正的牌组时).而不是将前面的牌组洗牌,然后连续提取顶牌,只需按照分类顺序离开牌组,每次从随机位置提取牌.

请参阅此处以获取有关其工作原理的完整说明,但我将介绍从下面的1到9中提取三个数字.

从(未检查的)列表{1,2,3,4,5,6,7,8,9}(显然是长度为9)开始,并根据该长度生成一个随机数(从0到8,包括0到8,假设我们使用基于零的索引,Java会这样做).假设第一个随机数是4.

然后,将项目保存在位置编号4(即5),并将列表(9)中的_last项目移动到该位置,将长度减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 之后返回.

你应该能够看到这是如何发展的.无需担心预先对整个列表进行排序,您可以实现随机序列(即,随机数生成器允许的随机序列),无需重复.