Shuffling

Today's 241 class was quite interesting. It talks about different ways of shuffling a list, like you could shuffle a deck of cards in real life. I'll describe all the ways I learned about in this post, so if this topic doesn't interest you, feel free to stop reading.

This requires us to be able to pick a single random element from the list. This is super easy, just choose a random number from 0-n, then pick the element at that position.

Now that we can do that, shuffling the whole list isn't too hard. Start at position 0, pick from positions 0-n to swap with it. Then move to position 1 and pick from positions 1-n to swap with it. And so on.

A harder problem is picking several random things from the list, without repeating. For example, drawing 5 balls from a bag of 20 balls, without putting them back in.

We can't just generate 5 random numbers, because they might repeat, and we don't want to select the same item twice.

The simplest method is of course to remove the selected element from the data structure and then pick from the remainder, but this requires the data structure to be modifiable like a linked list, rather than a Java array where elements cannot be removed, only nulled/zeroed.

A simple idea is to simply check if that number has already been generated, and roll again if it has. This is very simple to do, but there's always the chance that it could repeat forever if the same random number happened to keep being generated.

A similar idea is to first choose from 0-n. For the second item, choose from 0-(n-1), incrementing the index if that index was already chosen. For the third item, choose from 0-(n-2), ... This has the advantage of not getting stuck in potential random loops, but it's O(n²), because for every item we're picking, we have to iterate through the list checking if each element was already used.

An elegant idea is to add each element to the hand with a probability of a/r, where a is the number of cards still needed, and r is the number of cards in the deck that we can pick from. This is O(n), and we don't need to shuffle the deck first, but we do need to shuffle the hand of cards that were selected or they'll be in the same order as they were in the original deck — perfect for a raffle, not great for a poker tournament.

Finally there is the silly method where we can't change the order of items in the deck, so no shuffling allowed. We can actually use the naughty children trick here — while no one's looking, we shuffle the deck, but record our shuffles, and put everything back in the right place afterwards so it's all good for the next method. This is O(n), but probably slower than other methods, since we have to undo everything at the end.

The Pokémon of the day is, oh, there isn't one. We've passed 1000 cases, and there aren't 1000 Pokémon. Blame Nintendo.

The YouTube channel of the day is The Stupendium. This guy got me back into video game fan songs with the incredible sounds, background video, and production value. If you like music, give him a watch! My favourite song is the one from Untitled Goose Game.

— Cadence

← Previous: BreadNext: Tableau II →