洗牌算法讲解(java)

Question

我试图在一个常见的Java洗牌算法中更好地理解，这段代码：

// Random for remaining positions. 
int r = i + rand.nextInt(52 - i);

为什么要对生成的随机数“填充”或添加 i 索引？看起来当您迭代并添加 i 时，通过减去 i，您可以使随机数的最大可能范围保持在 0 到 51 之间，但为什么不这样做：

int r = rand.nextInt(52);

完整代码：

      
    // Function which shuffle and print the array 
    public static void shuffle(int card[], int n) 
    { 
          
        Random rand = new Random(); 
          
        for (int i = 0; i < n; i++) 
        { 
            // Random for remaining positions. 
            int r = i + rand.nextInt(52 - i); 
              
             //swapping the elements 
             int temp = card[r]; 
             card[r] = card[i]; 
             card[i] = temp; 
               
        } 
    }

Answer 1

您的代码所做的是创建一副牌的洗牌。在每次迭代中，它随机取一张牌并将其放回牌组的前面，从 i=0 到 i=n。

如果您会使用 int r = rand.nextInt(52);，这意味着在每次迭代中您都可以取回任何卡牌，即使是那些在牌组开头已经属于牌组新顺序的牌。

通过减去i你只选择剩下的52-i张牌中的一张牌，然后你需要添加+i才能得到它的实际位置，因为你已经在开头设置了第一张i张牌套牌作为新的洗牌。

例如，假设您已经将前 10 张牌放到了新位置。现在你需要拿到第 11 张牌，所以你从剩下的 52-10=42 张牌中随机拿一张牌。假设我们找回了数字 5，它不是 card[4] 处的卡片，而是 card[10+4]

处的卡片

Answer 2

Fisher–Yates shuffle的工作原理如下：

从数组中随机取一个元素，并将其交换到第一位
从剩余个值中随机取一个元素，并将其交换到第二位
从剩余个值中随机取一个元素，将其交换到第三位
等等

您问的是“剩余值”部分。

例如在 10 次迭代之后，您已将 10 个随机值交换到数组的前 10 个位置，因此对于下一次迭代，您需要一个范围为 10-end 的随机位置，因此 10 从随机范围 10 的偏移量小于完整范围, 又名 i + rand.nextInt(52 - i).

Answer 3

其他答案没有解决您的问题“为什么不这样做： int r = rand.nextInt(52);”。这有时被称为 naive shuffle，答案是因为这会导致有偏见的 shuffle。

理想情况下，您希望结果的数量能够反映出相同可能性结果所涉及的概率计算。这意味着洗好的牌组中的第一张牌可以是 52 张牌中的任意一张，第二张可以是剩余 51 张牌中的任意一张，第三张可以是剩余 50 张牌中的任意一张，......换句话说，有A = 52*51*50*...*3*2*1（即 52 阶乘）可能的纸牌排列。这就是 Fisher-Yates 洗牌及其变体所做的。但是，如果您按照您的建议选择任何一张卡片在第 i^th 次迭代中移动，则会生成 C = 52⁵² 个案例。结果是有偏见的洗牌。

为了说明在简单洗牌中如何以及为什么会出现偏差，请考虑一副只有 3 张牌的小得多的牌组。在这种情况下，A = 3*2*1 = 6 种排列，而 C = 3³ = 27 是到达最终排列的路径数。为什么这是个问题？因为鸽巢原理。 C 不是 A 的整数倍，所以如果我们把 C 看成鸽子，把 A 看成鸽子洞，那么某些洞肯定比其他洞得到更多的鸽子。用洗牌的术语来说，有些安排比其他安排有更多的途径。因此，并非所有安排都会同样频繁地发生，因此结果不是“公平”的洗牌。

如果您通过分析计算并从一个初始化为 ['a','b','c'] 的数组开始，您会发现在使用朴素洗牌时出现以下概率：

outcome         probability
-------         -----------
['a','b','c']       4/27
['a','c','b']       5/27
['b','a','c']       5/27
['b','c','a']       5/27
['c','a','b']       4/27
['c','b','a']       4/27

而对于无偏随机排列，6 种可能排列中每一种排列的概率都是 1/6。这就是创建 Fisher-Yates 算法的原因。

洗牌算法讲解(java)

Explanation of card shuffling algorithm (java)

java

algorithm

random

shuffle