by ·2 Comments

In the final installment of the portion of The Lottery Problem article series that has to do with the simple greedy wheel generator, I give a brief complexity analysis of my generation algorithm, and I report on the successes and the failures of the implemented generator:

On a 2.66 GHz Intel Core 2 Duo (though only using a single core), the generator consumed a peak of 1.87 GB of RAM and ran for approximately 36 hours before returning its wheel for 3-matches in a 6-from-49 lottery. […] The wheel that it generated for my target 6-from-49 3-match lottery was 325 tickets long. While this is in my opinion a pretty good wheel, it is not optimal.

You can read the whole article here. The long and the short of it is that the generator is indeed as efficient as I hoped it would be, but that it is not an optimal generator, as I suspected it would not be. The above-linked article includes a link to download the code for my implementation of this generator, if you wish to download it to play around with it or try to improve upon it.

My hunch is still that this problem is NP-Hard, and so I do not expect that any such simple generator will consistently produce optimal wheels. However, this is not the end of my series of articles on this problem. I do have hope that I can improve the generated wheels substantially by including a heuristic function that avoids the pitfalls of my current generator. Ultimately I would like to produce a generator that produces wheels that are guaranteed to be within a small approximation factor of optimal, or a randomized generator that is optimal with a reasonably high probability.

One small confession is that while I have posted the six articles in the current Lottery Problem series over the course of about six weeks, I had in fact written the entire greedy generator and knew its results before I even began writing the articles. For the heuristic and/or randomized generator that I am considering, I have so far done little more than pondering, so it may well be more than a week or two until the next article is posted.

by ·0 Comments

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.

  1. Once the relationships between tickets have been completely expressed, the actual numbers that constitute the tickets are of no significance and can be discarded.
  2. 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.
  3. 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.

by ·0 Comments

I can’t remember exactly how I got there (I suspect that Wikipedia was involved), but some weeks ago I ended up reading the UK National Lottery Wheeling Challenge website. The “challenge” involved is to generate a lottery wheel as small as possible for winning at least £10 in the United Kingdom’s national lottery. What exactly is a wheel, and why should it be small? To quote my own introduction:

A lottery wheel is a set of tickets for a lottery drawing which, if purchased in its entirety, guarantees a certain type of win, according to the rules of the lottery, no matter which ticket is actually drawn. […] The goal is straightforward. Each ticket we purchase costs money, so we want to generate a lottery wheel that is as small as possible while still guaranteeing a win of some minimum desired prize.

Now, obviously, such a thing no matter how good is not going to let you turn playing the lottery into a reliable money-maker, but in fact the reason that this is interesting has nothing to do with actually playing the lottery. I’ve only bought one lottery ticket in my entire life, and needless to say I lost.

The reason that this was initially interesting to me was that the site showcased a wheel of 163 tickets, which seems quite good for a 6-from-49 lottery, but went on to solicit for better wheels (indicating that the 163-ticket wheel was not known to be optimal) and to note that no wheel generation algorithm was known. The more I thought about how to create a generation algorithm, the more intriguing the problem became. The problem turns out to be a very special, highly symmetric form of minimum set covering. From what I was able to find, this problem has been studied academically, but with minimal results, and rarely on realistically-sized problems.

So, inspired by this, I set out to do two things: write a program that runs in a reasonable amount of time on a modern personal computer that can generate good lottery wheels for realistically-sized lotteries, and if possible prove whether this problem is NP-Hard or not.

I am documenting this project in a series of articles on the lottery problem. To start with, I have posted the first three articles which describe the problem, its relationship to set covering, and the challenges involved in implementing a generator algorithm for realistically-sized lotteries. Further articles will be posted later documenting my progress on the problem.