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

Today brings us, at long last, the latest installment in my article series on exploration of the Lottery Problem.

In the previous article, I discussed the design decisions that were made in the greedy lottery wheel generator in order to get around the computational problems inherent in even a simple greedy generator for realistically-sized lotteries. In this article, I will walk through the mechanics of generating all tickets and matches, selecting a ticket for the wheel, and updating ticket meta-data in order to allow the next selection.

You can read the whole article here. In essence, this is a walkthrough, using text, diagrams, and pseudocode, of how exactly I went about implementing a greedy algorithm based lottery wheel generator. This article addresses my solutions to problems of time complexity, much as the previous article largely addressed the solutions to problems of space complexity.

The actual generator was implemented in, of course, C++. However this article contains no actual code, only pseudocode, so as to put emphasis on the algorithms and not the details. Besides, full details of any program can only really be understood by reading code itself, not descriptions of it with snippets. I have still not yet made available the source code to this generator, although that will be forthcoming. Hopefully I will have it cleaned up enough to be suitable for public consumption before the next article in the series is posted.