CODEWITHSUNDEEP
java
user3350968
user3350968

Reputation: 21

How can Java prevent duplicated number creation with Random class?

I'm learning Java by reading the book "JAVA, How To Program", and I have reached chapter 7 which talks about array and arrays manipulations. In section 7.5 (case study: card shuffling and dealing simulation), it presents a program that creates a deck of cards, shuffles it and displays the shuffled cards without any duplicates.

In the program it uses the method shuffle to shuffle the cards after creating them. The method uses random object to create a random number between 0 and 51 to select a card from the deck and assign it to an array. The code:

 public void shuffle() {
     // after shuffling, dealing should start at deck[ 0 ] again
     currentCard = 0; // reinitialize currentCard

     // for each Card, pick another random Card (0-51) and swap them
     for (int first = 0; first < deck.length; first++) {
         // select a random number between 0 and 51
         int second = randomNumbers.nextInt( NUMBER_OF_CARDS ); 

         // swap current Card with randomly selected Card
         Card temp = deck[ first ];
         deck[ first ] = deck[ second ];
         deck[ second ] = temp;
    }
}

What if int second = randomNumbers.nextInt( Number_OF_CARDS ); generates a random number that is already selected? Wouldn't be there any duplicates in the deck? If this not the case, why duplicated numbers are not given by this line? What am I missing?

I have learnt that random numbers are generated "almost" equally between the range given, but there is still a chance for generating a number that is already generated before.

Upvotes: 2

Views: 197

Answers (3)

WJS
WJS

Reputation: 40034

Here is an algorithm that I learned many years ago. The key is to continually decrement the limit for the random number so you you won't replace what has already been replaced.


public class ShuffleDemo {
   int max = 10;

   public static void main(String[] args) {
      new ShuffleDemo().shuffle();
   }

   public void shuffle() {
      // start off with an array of 1 to max
      int[] vals = IntStream.rangeClosed(0, max).toArray();
      while (max > 0) {
         int selection = ThreadLocalRandom.current().nextInt(max);
         int temp = vals[max - 1];
         vals[max - 1] = vals[selection];
         vals[selection] = temp;
         max--;
      }

      System.out.println(Arrays.toString(vals));
   } // end method
}

It is still possible for a card to end up in its original position. But then, that can also happen with a real deck

Upvotes: 0

yshavit
yshavit

Reputation: 43391

It won't duplicate, because you're always swapping cards, and swapping can never duplicate. For instance, let's say my list starts out [a, b, c, d]. If I pick 1 as my first random number, then I swap elements 0 and 2, and end up with [c, b, a, d]. If I pick 2 again for my second number, I swap 1 and 2, and end up with [c, a, b, d].

But you are right that the algorithm is wrong! You can swap an already-swapped card, meaning that cards that get swapped early have a higher chance of getting swapped again, which introduces a bias. This CodingHorror blog post talks about it some, and there are many other discussions online if you search for "wrong shuffling algorithm" or such.

Instead, if you're trying to swap a card into position i, you should randomly pick a card from location x such that i <= x < deck.length. I forget offhand what the name of the book's (incorrect) algorithm is, but the variant I mentioned is called Fisher–Yates shuffle.

Upvotes: 2

Progman
Progman

Reputation: 19546

This code doesn't pick cards from a deck and insert in a new list. Instead it swaps two random cards multiple times. The cards inside the deck are still "unique" to each other. That one of the index is selected more than one time is not a problem, it just gets swapped with another card. So in one case it might swap the cards at index 5 and 14 and in another for loop iteration, it might swap the cards at index 11 and 14. But in the end the deck contains the same cards, they are just not in the original order anymore.

Upvotes: 0

Related Questions