• Post Reply Bookmark Topic Watch Topic
  • New Topic

Shuffling cards and Random.org  RSS feed

 
Carey Brown
Saloon Keeper
Posts: 3329
46
Eclipse IDE Firefox Browser Java MySQL Database VI Editor Windows
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
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?
 
Carey Brown
Saloon Keeper
Posts: 3329
46
Eclipse IDE Firefox Browser Java MySQL Database VI Editor Windows
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Moved to forum: Java in General
 
Rob Spoor
Sheriff
Posts: 21135
87
Chrome Eclipse IDE Java Windows
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Is something wrong with Collections.shuffle?
 
Carey Brown
Saloon Keeper
Posts: 3329
46
Eclipse IDE Firefox Browser Java MySQL Database VI Editor Windows
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
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.
 
Rob Spoor
Sheriff
Posts: 21135
87
Chrome Eclipse IDE Java Windows
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
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.
 
Campbell Ritchie
Marshal
Posts: 56599
172
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
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.
 
Rob Spoor
Sheriff
Posts: 21135
87
Chrome Eclipse IDE Java Windows
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
I have the book right here, and their solution is to use 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.
 
Paul Clapham
Sheriff
Posts: 22844
43
Eclipse IDE Firefox Browser MySQL Database
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
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.
 
  • Post Reply Bookmark Topic Watch Topic
  • New Topic
Boost this thread!