java - 洗牌，交换两个值后的冗余

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号卡，那么我在交换两次。我想知道有什么办法可以不这样做吗？

我在这里查看了一个帖子:Shuffling a deck of cards

但这对我来说没有意义。

Answer 1

I'm wondering is there any way of not doing this?

当然。不要将一张卡片与其他任何交换，只需将一张卡片与以后的交换。

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

阅读Wikipedia article on the Fisher-Yates shuffle获取更多信息。

(一些实现从 end 开始交换，所以元素 x 与范围内的随机元素交换 [0, x] 。这等同于我所描述的，只是镜像。我个人发现它更容易将集合的第一部分视为任何时候的洗牌部分，但这是我的失败，而不是内在差异。)

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