Hacker News Reader

Comment by codeulike | Hacker News Reader

Looks great. It probably doesn't matter for something like this, but what algorithm are you using for card shuffling? Note that if you use a 32-bit random seed, you only reach about 4 x 10^9 of the 8 x 10^67 different ways a pack of cards can be shuffled - a tiny tiny tiny fraction.

http://www.lauradhamilton.com/random-lessons-online-poker-ex...

The other interesting aspect about card shuffling is how more shuffling than necessary might make the end result worse

https://blog.codinghorror.com/the-danger-of-naivete/

edit: changed to 'seed' as mentioned below, reframed blog post

View on HN

> if you use a 32-bit random number generator, you only reach about 4 x 10^9 of the 8 x 10^67 different ways

I suggest you reread your linked article. The fault is in using a 32-bit SEED.

Random shuffling algorithms are trivial and well known [0]. It really doesn't need some click-bait blog posts.

[0] https://en.wikipedia.org/wiki/Fisher–Yates_shuffle

Well they're not well known to me. But yes I can see in the FAQ https://playingcards.io/docs/faq that this site uses Fisher-Yates.

Yes, you got it, Fischer-Yates shuffle via lodash. Here's their implementation: https://github.com/lodash/lodash/blob/master/shuffle.js

Trying to work out how many bits the seed has, but it depends on the browsers implementation of Math.random() - in theory could be anything but apparently its usually Xorshift128+, which as far as I can tell has a 128 bit seed. So all good? Although I'm not sure where the 128 bits for the seed come from.

https://hackernoon.com/how-does-javascripts-math-random-gene...

I'm intrigued by why all these example shuffling algorithms are based on swapping cards in-place.

The first algorithm that would occur to me would be take a pile of 52 cards, and repeatedly pick cards randomly to place into a new pile that eventually has 52 cards.

Though I suppose that's the kind of thing that's trivial to program in scripting languages with arrays that are easy to remove a middle item from, and less so in a classic algorithmic language like C.

> and less so in a classic algorithmic language like C.

Shuffling into a new pile is not that it is hard to do in C, just move items from one linked list to another.

But if it can be done with a simple array saving memory then why not.

It's surprisingly easy to write an incorrect shuffling algorithm, and end up with a subset of permutations or a very skewed distribution.

(in fact, there's both obvious and interesting information preserved by a single riffle shuffle... which is why you need to shuffle multiple times in real life. It would be cool if the site emulated a riffle shuffle, so you'd need to shuffle seven-ish times to get close to a uniformly random permutation.)

But that's what I mean -- swapping seems indeed suprisingly easy to write incorrectly, just as you say.

But just randomly picking from a pile seems pretty easy to write correctly. No? And if you have an off-by-one error, your deck of 52 cards gets turned into 51, so it's not like you won't catch it...

Maintaining a "pile" of not-yet-selected items, and randomly removing elements from it, turns your shuffle from an O(n) algorithm into an O(n^2) one (unless you go out of your way to use a more sophisticated data structure than either an array or a linked list).

It's not likely to matter much if you're only shuffling 52 cards, but if you're writing a general-purpose shuffle algorithm, there's no reason to needlessly make it inefficient.

You don't actually need two arrays to implement your idea. Since the combined size will be constant, just one array with an index indicating the split is enough.

When moving cards from one side to the other a lot of elements will have to be moved around. But for small n it should be much faster than using linked lists. And also relatively easy to implement in C.

The shifting of elements when inserting can be avoided by only swapping two positions. (ABXDEFC instead of ABXCDEF, when inserting X into ABCDEF). But by then you have just reinvented Fisher-Yates.

So the swapping in some of these algoritms is basically an implementation of your idea.

> The first algorithm that would occur to me would be take a pile of 52 cards, and repeatedly pick cards randomly to place into a new pile that eventually has 52 cards.

This is a perfect description of the Fisher–Yates shuffle – the standard you should reach for when shuffling, and what the latter article suggested, too.

Of course, as a technical implementation detail, instead of having two actual arrays, you can use one array and swap within it to get the effect of two arrays, except in one for performance.

Reply on news.ycombinator.com