Hacker News Reader

Comment by crazygringo | Hacker News Reader

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.

View on HN

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.

> 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.

Reply on news.ycombinator.com