Sometimes we like to do things in a more complicated way just because we follow what we can easily visualise.

Problem definition

Implement code for a shuffled deck of cards:

• allow to retrieve cards one-by-one
• allow to return cards to the deck but these are not used until original deck is fully used up
• before returned cards are used, they are shuffled.

Straightforward implementation

A straightforward approach would be to maintain some form of list that holds a shuffled deck in the order of retrieval.

There are two inherent inefficiencies with this:

• Needing to figure out in advance, for each card in a deck, the order will it be retrieved from the deck; requiring upfront computation of this order of retrieval for each card
• Storing the deck in such shuffled order; requiring storage for such shuffled deck.

Neither is strictly necessary as we only care about the next card needed and making sure that that next card was not served before.

Optimised!

The only thing really needed to be stored is which cards got used so far, so a simple bitmap suffices.

Initially, this bitmap will contain all 0s denoting that no card was used up yet.

Each time a card is retrieved, a random number is generated and used to seed the search for the next unset bit of the bitmap which will be the card to be returned. Conversely, this bit in the bitmap will be set to denote the card is used and return the matching card.

Returning cards to deck

Similarly, returned cards are kept as a bitmap in which cards that are returned are denoted by an unset bit i.e. initially, bitmap is fully set. Once the last card in the original bitmap of used cards is used up, bitmaps of used cards and returned cards are swapped, and the same code used to fetch the next card to be returned is used. This also sets the bitset for returned cards to be empty. This in effect results in shuffling returned cards to the deck.

Implementation quirks

See code for Java implementation of what was described above: https://github.com/dkambur/Ramblings

Java BitSet implementation allocates sufficient amount of words to store all bits required but it does not store the number of actual bits used, and all operations work off bits allocated as opposed to bits actually used.