0

I'm creating a simple method to simulate shuffling a deck. My idea is to store the size of the original deck, and repeat the loop as long as the size is not negative.

During the loop I copy an Object (card) from the list, and place it in another list. Remove from the original list, and resume the loop.

while(size >= 0){
        int random = (int) ((Math.random() * size) + 0);    
        shuffledDeck.add(this.orderedDeck.get(random));
        orderedDeck.remove(random);
        size--;
    }

The size of this particular deck is

int size = this.getDeckSize()-1; //51 (52 cards, from 0 to 51)

My issue is that on several different attempts, the last card in the shuffled deck is consistently the same card as the last in the unshuffled deck. This suggests that random is never equal to size-1.

How can I make it so the last card is actually able to be shuffled?

(In other words, why is random ever equal to size-1 ?)

Oak
  • 693
  • 7
  • 13

3 Answers3

3

Math.random() never returns 1.0, as the docs explain:

Returns a double value with a positive sign, greater than or equal to 0.0 and less than 1.0.

Even if it did return 1.0, it would do so with minuscule probability, and your code would round any other value down, so you still wouldn't uniformly be getting the results you want.

As others have noted you have some further arithmetic errors in your code, but even correcting them won't yield properly distributed random values.

You should not use Math.random() for this task - instead use Random.nextInt(n), which is designed to properly return a uniform value in the desired range.

Dealing with random sources of data properly is tricky. As a rule of thumb, if you find yourself doing arithmetic on random values it's likely you're doing something wrong (such as generating non-uniform results) and you should look for an existing function that provides the type of randomness you're looking for instead.

dimo414
  • 47,227
  • 18
  • 148
  • 244
  • Returning `1.0` from the RNG is not the problem as this would give an index which is too large anyway. – Code-Apprentice Jul 02 '17 at 17:57
  • Explicitly mentioning that casting `double` to `int` rounds it down might also be useful for this answer. `Math.random` should work fine if you increase `size` by 1, but `nextInt` indeed seems more appropriate and less prone to error. – Bernhard Barker Jul 02 '17 at 18:36
  • @Code-Apprentice even correcting for the arithmetic errors `Math.random()` is not a robust way to generate a random value from a discrete range. The results will still be non-uniform, and using the proper methods of the `Random` class is the way to avoid these issues. – dimo414 Jul 02 '17 at 19:58
  • @dimo414 I want to understand more about this. I decided to post a new question rather than continue in comments. Please take a look when you have some time: https://stackoverflow.com/questions/44874801/does-math-random-generate-pseudorandom-numbers-uniformly – Code-Apprentice Jul 02 '17 at 20:11
2

It looks like size is initialized to orderedDeck.size() - 1. Since (int) (Math.random() * size) returns a value in the range [0, size), that is, size itself never included, the last element will never get selected.

You can fix by using size + 1 as the upper bound instead of size:

while (size >= 0) {
  int random = (int) (Math.random() * (size + 1));
  shuffledDeck.add(orderedDeck.get(random));
  orderedDeck.remove(random);
  size--;
}

But please, don't use this technique to create a shuffled list.

The current approach is very inefficient, because removing elements from the middle of a list is inefficient. It will be better and very easy to implement efficient sorting using Fisher-Yates shuffle. For example:

Random random = new Random();
for (int i = list.size() - 1; i > 0; i--) {
  int j = random.nextInt(i);
  int tmp = list.get(i);
  list.set(i, list.get(j));
  list.set(j, tmp);
}
janos
  • 120,954
  • 29
  • 226
  • 236
0
int size = this.getDeckSize()-1; //51 (52 cards, from 0 to 51)

The problem is that you subtract 1 from the returned value. getDeckSize() shows that your deck has exactly the correct number of elements (52 cards). You should not subtract 1.

Code-Apprentice
  • 81,660
  • 23
  • 145
  • 268
  • It has to be `size = 51`, because if I had `size=52` it would prompt Math.random() to be able to return `52` (I have tested this). This results in a `java.lang.IndexOutOfBoundsException:` because there the list only has 52 elements, and pointing to element 52 is impossible (as the list starts on element 0) – Oak Jul 02 '17 at 17:58
  • @Oak Please edit the question to show the code that gives the IndexOutOfBoundsException. – Code-Apprentice Jul 02 '17 at 17:59
  • 1
    @Oak "there the list only has 52 elements, and pointing to element 52 is impossible (as the list starts on element 0)" Note that indexes between 0 and 51 give 52 possible choices. Therefore, `size` should be 52. Unless you have misnamed your variable and it should be `maxIndex` instead of `size`. – Code-Apprentice Jul 02 '17 at 18:00