Java 洗牌一副牌，交换两个值后的冗余
声明：本页面是StackOverFlow热门问题的中英对照翻译，遵循CC BY-SA 4.0协议，如果您需要使用它，必须同样遵循CC BY-SA许可，注明原文地址和作者信息，同时你必须将它归于原作者（不是我）：StackOverFlow
原文地址: http://stackoverflow.com/questions/16313567/
Warning: these are provided under cc-by-sa 4.0 license. You are free to use/share it, But you must attribute it to the original authors (not me):
StackOverFlow
Shuffling a Deck of Cards , Redundancy after swapping two values
提问by Tan
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?
但是上面的shuffle方法有一个逻辑错误，如下所示：假设我用卡号42替换卡号4，然后我交换了两次。我想知道有没有办法不这样做？
I checked one post here :Shuffling a deck of cards
我在这里查看了一个帖子：洗牌
But it didn't make sense to me.
但这对我来说没有意义。
采纳答案by Jon Skeet
I'm wondering is there any way of not doing this?
我想知道有没有办法不这样做？
Absolutely. Instead of swapping one card with anyother, simply swap one card with a laterone.
绝对地。相反，与一个交换卡的任何其他，只需换一张卡用后一个。
So at any point, you're really picking which card is going to be in slot ifrom "all the remaining cards" which haven't been picked. It's conceptuallyequivalent to starting with one list of cards, and removingcards at random to place in the new shuffled collection. The fact that you're actually swapping locations while you're doing that is irrelevant, as at any point you'll be picking uniformly randomly from the remaining slots.
因此，在任何时候，您实际上都是i从尚未选择的“所有剩余卡”中选择哪张卡将放入插槽中。这在概念上等同于从一张卡片列表开始，然后随机移除卡片以放置在新的洗牌集合中。在您这样做时实际上交换位置这一事实无关紧要，因为在任何时候您都会从剩余的位置中随机均匀地选择。
Read the Wikipedia article on the Fisher-Yates shufflefor more information.
阅读有关 Fisher-Yates shuffle的Wikipedia 文章了解更多信息。
(Some implementations swap from the end, so element xis swapped with a random element in the range [0, x]. That's equivalent to what I described, just mirrored. Personally I find it easier to think of the firstpart of the collection as being the shuffled part at any point, but that's a failing on my part rather than an inherent difference.)
（一些实现从末尾交换，因此元素x与范围内的随机元素交换[0, x]。这相当于我所描述的，只是镜像。就我个人而言，我发现更容易将集合的第一部分视为在任何一点，但这是我的失败而不是内在的差异。）
Also bear in mind that if you use a List<Card>, you can use Collections.shuffleand avoid having to write the code for this at all.
还要记住，如果您使用 a List<Card>，则可以使用Collections.shuffle并完全避免为此编写代码。
回答by Evgeniy Dorofeev
You can compare your implementation with Collections.shuffle, that one definitely works right, this is a snippet from src
您可以将您的实现与 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;
}
回答by paxdiablo
Sometimes, the best way to shuffle a deck is to notshuffle it. Since you already know how to use random numbers, you can use a modification to the Fisher-Yates shuffle to extract cards in random order, without duplicates, all without an initial sort.
有时，洗牌的最好方法是不洗牌。由于您已经知道如何使用随机数，您可以对 Fisher-Yates shuffle 进行修改，以随机顺序提取卡片，没有重复，所有都没有初始排序。
Think of it in these physical terms (when using a real deck of cards). Rather than shuffling the deck up front then continuously extracting the top card, just leave the deck in sorted order and extract a card from a random location each time.
用这些物理术语来考虑（当使用一副真正的纸牌时）。与其先洗牌然后连续提取最上面的牌，不如按顺序离开牌组，每次从随机位置提取一张牌。
See herefor an complete explanation of how this works but I'll cover extracting three numbers from 1 through 9 inclusive below.
有关其工作原理的完整说明，请参见此处，但我将在下面介绍从 1 到 9 中提取三个数字。
Start with the (unshuffled) list {1,2,3,4,5,6,7,8,9}(of length 9, obviously) and generate a random number based on that length (from 0 to 8 inclusive, assuming we use zero-based indexes, which Java does). Let's say the first random number is 4.
从（未打乱的）列表{1,2,3,4,5,6,7,8,9}（显然长度为 9）开始，并根据该长度（从 0 到 8，包括 0 到 8，假设我们使用从零开始的索引，Java 所做的）生成一个随机数。假设第一个随机数是 4。
You then save the item at position number 4 (which is 5) and move the _last item in the list (9) to that position, decreasing the length by one. That gives you {1,2,3,4,9,6,7,8}with a length of 8.
然后将项目保存在位置编号 4（即5），并将列表中的 _last 项目 ( 9) 移动到该位置，将长度减一。这为您{1,2,3,4,9,6,7,8}提供了 8 的长度。
Then go back for a second number again using a random number based on the length (0 through 7 inclusive). In this case, we'll get the random number 1.
然后使用基于长度的随机数（0 到 7 包括在内）再次返回第二个数字。在这种情况下，我们将得到随机数 1。
The item at offset 1 is 2and we then adjust the list same as the first step, giving {1,8,3,4,9,6,7}with a length of 7.
偏移量 1 处的项目是2，然后我们调整与第一步相同的列表，{1,8,3,4,9,6,7}长度为 7。
Now let's say we get a third random number based on the current length of 7 and it happens to be 4 again. That item is now 9so we return that, after modifying the list to become {1,8,3,4,7,6}with length 6.
现在假设我们根据当前的长度 7 得到第三个随机数，它恰好又是 4。该项目现在是，9所以我们在修改列表使其{1,8,3,4,7,6}长度为 6后返回该项目。
You should be able to see how this is developing. Without any worry about sorting the entire list up front, you can achieve a random sequence (well, as random as your random number generator permits) without repeats.
您应该能够看到这是如何发展的。无需担心预先对整个列表进行排序，您可以实现一个随机序列（好吧，只要您的随机数生成器允许随机）而无需重复。
