posted 2 weeks ago

There has been several threads that have discussed the fact that Java's built in random algorithm doesn't have enough bits to generate all possible permutations of 52 cards. For the most part this is not a problem, but what if you really wanted/needed to guarantee that all permutations were possible?

I have tripped over a web site random.org that uses physical noise detectors to generate as many random bits as you need. They have an API with a JSON interface where you can request a random ordering of the numbers from 0 to 51 inclusive which you could use as indexes into an array or list of cards. It appears that you have to sign up for a key which allocates so many random bits a day for you to request; should be good for quite a number of card shuffles.

Has anyone tried to implement a card shuffle via their API?

I have tripped over a web site random.org that uses physical noise detectors to generate as many random bits as you need. They have an API with a JSON interface where you can request a random ordering of the numbers from 0 to 51 inclusive which you could use as indexes into an array or list of cards. It appears that you have to sign up for a key which allocates so many random bits a day for you to request; should be good for quite a number of card shuffles.

Has anyone tried to implement a card shuffle via their API?

Some people, when confronted with a problem, think "I know, I'll use regular expressions." Now they have two problems.

posted 2 weeks ago

Is something wrong with Collections.shuffle?

SCJP 1.4 - SCJP 6 - SCWCD 5 - OCEEJBD 6 - OCEJPAD 6

How To Ask Questions How To Answer Questions

posted 2 weeks ago

Yes. All possible permutations of a deck of cards is 52! and the possible outcomes of shuffle() (based on a long) is a fraction of that.
Some people, when confronted with a problem, think "I know, I'll use regular expressions." Now they have two problems.

Rob Spoor wrote:Is something wrong with Collections.shuffle?

Yes. All possible permutations of a deck of cards is 52! and the possible outcomes of shuffle() (based on a long) is a fraction of that.

posted 2 weeks ago

But for one shuffle operation you don't need all permutations, just a specific one. And that's what shuffle does - it randomly shuffles the elements. The current implementation iterates from the back, and swaps elements with an element located before it in the list:

Unless this shuffle mechanism is broken, this will eventually generate all possible permutations - one at a time.

Unless this shuffle mechanism is broken, this will eventually generate all possible permutations - one at a time.

SCJP 1.4 - SCJP 6 - SCWCD 5 - OCEEJBD 6 - OCEJPAD 6

How To Ask Questions How To Answer Questions

Campbell Ritchie

Marshal

Posts: 54909

155

posted 2 weeks ago

The problem is discussed in more detail by Bloch and Gafter; more info in this thread. The number of permutations is 52! and that is more than the possibilities from a Random object. But even so, Collections#shuffle is probably the best available implementation of that problem.

posted 2 weeks ago

I have the book right here, and their solution is to use

Conclusion: you're right, you need more precision, and that would require a third party RNG library that can handle the 52! size. Other than that, the best you can do is use SecureRandom instead of Random.

`Collections.shuffle`. They mention the problem in the limitation of the size of long as well. They say that using SecureRandom gives you 160 bits instead of 64 bits.Conclusion: you're right, you need more precision, and that would require a third party RNG library that can handle the 52! size. Other than that, the best you can do is use SecureRandom instead of Random.

SCJP 1.4 - SCJP 6 - SCWCD 5 - OCEEJBD 6 - OCEJPAD 6

How To Ask Questions How To Answer Questions

posted 2 weeks ago

When I take a deck of cards in my hands and shuffle the deck, the possible outcomes of that shuffle is a very small fraction of 52! because I'm not going to live long enough to shuffle the deck that many times. But nobody seems to mind that when I shuffle the deck.

Carey Brown wrote:Rob Spoor wrote:Is something wrong with Collections.shuffle?

Yes. All possible permutations of a deck of cards is 52! and the possible outcomes of shuffle() (based on a long) is a fraction of that.

When I take a deck of cards in my hands and shuffle the deck, the possible outcomes of that shuffle is a very small fraction of 52! because I'm not going to live long enough to shuffle the deck that many times. But nobody seems to mind that when I shuffle the deck.