洗牌的随机性

Question

我有一个包含 52 张卡片的卡片数组列表。我想洗牌。

这就是我所做的。

创建了一个新的数组列表。
生成了 0 到牌组大小之间的随机索引。
在随机索引中获取卡片并添加到新列表。
从牌组中移除卡片
重复直到牌组变空。

这是我的代码：

String[] Number = {"A","2","3","4","5","6","7","8","9","10","J","Q","K"};
String[] Suits = {"Club","Diamonds","Hearts","Spades"};
ArrayList<Card> deck = new ArrayList<Card>();

// create a deck    

for(int i=0;i<13;i++){
        for(int j=0;j<4;j++){
            Card card = new Card(Suits[j],Number[i]);
            deck.add(card);
        }    
    }

// shuffle of deck

ArrayList<Card> new_deck = new ArrayList<Card>();
    while(deck.size()!=0){   

        Random rand = new Random();
        int  n = rand.nextInt(deck.size());

        new_deck.add(deck.get(n));
        deck.remove(n);
    }

// Display

for(int i=0;i<52;i++){
        System.out.println(new_deck.get(i).getSuit()+" : "+new_deck.get(i).getValue());
    }

最后，我从新的 ArrayList 中得到了洗牌后的牌组。

它的随机性够不够好？

我应该怎么做才能增加随机性？

Answer 1

您应该以精确的方式定义您对 "randomness" 的概念。 "Increasing randomness" 是一个相当模糊的术语。

我会根据 "random" 假设，你想要的是你套牌上的 uniform distribution of permutation。也就是说，您希望您的牌组以这样一种方式重新排序，即下一张牌是特定牌的机会是相等的。

这里有两个不同的因素在起作用：

你如何洗牌
随机生成器Random有多好

你如何洗牌

就洗牌方式而言，它是统一的。可以证明conditional probability任意一张牌在任意位置正好是1/52。

`util.Random`有多好

首先，要明确的是，util.Random 不是实际上是随机的。这是一个 pseudorandom number generator(PRNG)。这意味着他们所做的不是产生真正的随机数。相反，他们尝试，并且根据应用要求，这就足够了。

util.Random是一个linear congruential generator, and as far as PRNGs go, its pretty weak. If you don't care about really randomizing your deck, it will work fine. However if you need something more robust, here是一个起点。

Answer 2

我建议您可以简单地使用 Collections.shuffle()，如下所示，而不是重新发明 Collections API:

已经提供的洗牌逻辑

Collections.shuffle(deck);//Pass your ArrayList<Card> object i.e., deck

因此，通过重用这个现有的 Collections API 消除了您对 deck 对象的随机性的所有疑虑。

Answer 3

Does it's randomness is enough or not ?

定义足够好 (!!)

您当前的方法将提供良好的洗牌，没有明显的偏差...除了随机数生成器可能引入的偏差。

在这种情况下，确实值得关注。 Random 被指定为线性同余生成器，并且 LC 生成器在生成的数字中具有不同的模式。（在统计术语中，它们显示出很强的自相关性。）如果您绘制第 n 个随机数与 n 的关系图，这就很清楚了。

要提高随机性，您应该使用更好的随机数生成器。 SecureRandom 生成器应该足够好：javadoc.

如果您使用 Collections.shuffle 方法，同样会担心随机性。对于 good（或一致的）shuffle，您应该在提供 Random 实现的地方使用方法重载...并选择一个好的实现。

Answer 4

这里有一个问题java.util.Random没有提到：是否可以生成52项列表的所有排列。这是基于它的周期。一般来说，伪随机数生成器 (PRNG) 不能生成比其周期更多的随机数序列排列（有关进一步讨论，请参阅我的 article on randomness 中的 "Shuffling"）。

java.util.Random的周期不高于2⁴⁸，因为它使用48位种子长度。但是，52 项列表有 52 个阶乘排列，这比 2²²⁵ 高——比 java.util.Random 的周期高出许多数量级。因此，java.util.Random 无法生成 52 项列表的许多排列（使用相同的改组技术）。（这适用于周期小于 52 阶乘的 any PRNG，而不仅仅是线性同余生成器，特别是 java.util.Random。）因此，需要洗牌的应用程序一个 52 项列表最好使用设计用于生成预测成本过高的随机数的生成器（例如 Java 的 SecureRandom）或使用周期为 52 阶乘的 PRNG或更高（尽管如此高的周期本身可能不足以确保 PRNG 可以生成该列表的所有排列）。

编辑：最近的两个问题讨论了如何产生足够的随机性来洗牌 52 张数字 "deck"：

解决方案的要点是您需要找到一种方法来生成 226 位或更多的 entropy（随机性）并使用它来帮助生成随机排列。有关详细信息，请参阅链接的问题，另请参阅我关于 nondeterministic sources and seed generation.

的部分

洗牌的随机性

Randomness of shuffled cards

java

random

arraylist

playing-cards

你如何洗牌

`util.Random`有多好

洗牌的随机性

Randomness of shuffled cards

java

random

arraylist

playing-cards

你如何洗牌

util.Random有多好

`util.Random`有多好