Explanation of card shuffling algorithm (java)



I was trying to better understand in a common Java shuffle deck of cards algorithm, this piece of code:

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

Why is it necessary to “pad” or add i index to the resultant random number? It looks like as you iterate and add i, by subtracting i, you keep the max possible range of random numbers consistent from 0 to 51, but why not just do:

int r = rand.nextInt(52);

Full code:

      
    // 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

The Fisher–Yates shuffle works as follows:

  • Take a random element from the array, and swap it into first place
  • Take a random element from remaining values, and swap it into second place
  • Take a random element from remaining values, and swap it into third place
  • and so on

It is the “remaining values” part you’re asking about.

E.g. after 10 iterations, you have swapped 10 random values into the first 10 positions of the array, so for the next iteration you need a random position in range 10-end, hence the offset of 10 from a random range of 10 less than full range, aka i + rand.nextInt(52 - i).



Source: stackoverflow