The newest article in my series on the Lottery Problem describes the design decisions I made when making my first attempt at an implementation of an efficient wheel generator based on the simple greedy algorithm for set cover. The design decisions described were influenced by three key insights I had when considering how one might attempt to generate a close-to-optimal wheel for a 6-from-49 lottery in a reasonable amount of time.
- Once the relationships between tickets have been completely expressed, the actual numbers that constitute the tickets are of no significance and can be discarded.
- It is only necessary to keep track of how many uncovered tickets an unselected ticket could potentially cover if selected. It is unnecessary to know exactly which tickets those are.
- Every ticket initially covers the same number of other tickets, and this number can be computed through combinatorics alone.
You can read the full article here. It primarily addresses the challenges involved in expressing the problem within a reasonable amount of memory, and gives an overview of how the computation will be approached. The computation itself will be described in detail in the next article.
Share this content on:
