Randomness of shuffled cards

Question

I have an Array List of cards containing 52 cards. I want to shuffle the deck.

This is what I have done.

1. Created a new Array List.
2. Generated random index between 0 to deck size.
3. Get card at random index and add to new list.
4. Remove card from deck
5. Repeat until deck is empty.

Here is my code:

String[] Number = {"A","2","3","4","5","6","7","8","9","10","J","Q","K"};
String[] Suits = {"Club","Diamonds","Hearts","Spades"};
ArrayList<Card> deck = new ArrayList<Card>();

// create a deck    

for(int i=0;i<13;i++){
        for(int j=0;j<4;j++){
            Card card = new Card(Suits[j],Number[i]);
            deck.add(card);
        }    
    }

// shuffle of deck

ArrayList<Card> new_deck = new ArrayList<Card>();
    while(deck.size()!=0){   

        Random rand = new Random();
        int  n = rand.nextInt(deck.size());

        new_deck.add(deck.get(n));
        deck.remove(n);
    }

// Display

for(int i=0;i<52;i++){
        System.out.println(new_deck.get(i).getSuit()+" : "+new_deck.get(i).getValue());
    }

Finally, I get the shuffled deck from new ArrayList.

Is its randomness good enough or not?

What should I do to increase randomness?

Answer 1

Does it's randomness is enough or not ?

Define good enough (!!)

Your current approach is going to give a good shuffle, with no obvious biases ... except for biases that may be introduced by the random number generator.

And in this case, there is real cause for concern. Random is specified to be a linear congruential generator, and LC generations have distinct patterns in the numbers that they generate. (In statistical terms, they show strong auto-correlation.) This is quite clear if you graph the n'th random number against n.

To improve randomness, you should use a better random number generator. The SecureRandom generator should be good enough: javadoc.

---

The same concern about the randomness applies if you use Collections.shuffle method. For a good (or consistent) shuffle you should use the method overload where you supply a Random implementation ... and choose a good one.

Answer 2

I suggest you can simply use Collections.shuffle() as shown below rather than reinventing the shuffling logic which is already provided by Collections API:

Collections.shuffle(deck);//Pass your ArrayList<Card> object i.e., deck

So, by reusing this existing Collections API clears all your doubts on the randomness of your deck object.

Answer 3

You should define your notion of "randomness" in a precise way. "Increasing randomness" is a rather vague term.

I will assume by "random", what you want is a uniform distribution of permutation on your deck. Which is to say, you want your deck to be reordered in such a way that the chance that the next card is a particular card is equal.

There are two different factors at play here:

• How you shuffle
• How good a random generator Random is

---

How you shuffle

As far as how you shuffle goes, it is uniform. It can be proven by conditional probability that any card being in any position is exactly 1/52.

How good util.Random is

First, to be clear, util.Random is not actually random. It is a pseudorandom number generator(PRNG). That means what they do is not to produce truly random numbers. Instead they try to, and depending on application requirements, it will be enough.

util.Random is a linear congruential generator, and as far as PRNGs go, its pretty weak. If you don't care about really randomizing your deck, it will work fine. However if you need something more robust, here is a starting point.

Answer 4

There is one issue not mentioned here about java.util.Random: whether it can generate all permutations of a 52-item list. This is based on its period. In general, a pseudorandom number generator (PRNG) can't generate more permutations of random number sequences than its period (see "Shuffling" in my article on randomness for further discussion).

The period of java.util.Random is no higher than 2⁴⁸, since it uses a 48-bit seed length. However, there are 52-factorial permutations of a 52-item list, and that's higher than 2²²⁵ -- which exceeds java.util.Random's period by many orders of magnitude. Because of this, there are many, many permutations of a 52-item list that java.util.Random can't generate (using the same shuffling technique). (And this applies to any PRNG with period less than 52-factorial, not just linear congruential generators, like java.util.Random, in particular.) Therefore, an application that needs to shuffle a 52-item list would be well advised to use a generator designed to produce random numbers that are cost-prohibitive to predict (such as Java's SecureRandom) or use a PRNG with period 52-factorial or higher (although a period that high, by itself, may not be enough to ensure the PRNG can generate all permutations of that list).

---

EDIT: Two recent questions discussed how to generate enough randomness to shuffle a digital "deck" of 52 cards:

Is java.util.Random really that random? How can I generate 52! (factorial) possible sequences?

Where can I get a reliable source of entropy (real randomness byte[])?

The gist of the solution is that you will need to find a way to generate 226 bits or more of entropy (randomness) and use it to help generate a random permutation. See the linked questions for details, and see also my section on nondeterministic sources and seed generation.