洗牌算法讲解（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

在费雪耶茨洗牌的工作原理如下：

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

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

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