CODEWITHSUNDEEP
c#.netconsolecombinations
Trinnexx
Trinnexx

Reputation: 57

Generating Combinations

Recently I have been reading about lotto wheeling and combination generating. I thought I'd give it a whirl and looked about for example code. I managed to cobble together a number wheel based on some VB but I've introduced an interesting bug while porting it. http://www.xtremevbtalk.com/showthread.php?t=168296

It allows you to basically ID any combination. You feed it N numbers, K picks and an index and it returns that combination in lexicographical order. It works well at low values but as the number of balls (N) rises I get additional numbers occurring for example. 40 balls, 2 picks. Combination No. 780 Returns 40 and 41! The more picks and numbers I added the higher this goes, It seem to happen at the end of a run when the number preceding is due to cycle.

I found the method for generating number of possible combination on the VB forum to not make a lot of sense, so I found a simpler one: http://www.dreamincode.net/code/snippet2334.htm Then I discovered that using doubles seems to cause a lack of resolution. Using long works, but now I can't use higher values of N because the multiplying goes out of range for a long! I then tried ulong and decimal neither could go much past 26-28 numbers (N). So I reverted to the version on the VB site. http://www.xtremevbtalk.com/showthread.php?s=6548354125cb4f312fc555dd0864853e&t=129902

The code is a method to avoid hitting the 96bit ceiling and claims to be able to calculate as high as N 98, K 49. For some reason I cannot get this to behave, it spits out some very strange numbers.

After giving up for a while I decided to re-read the wiki suggested. While most of it was over my head, I was able to discover that certain ways of calculating a binomial coefficient have inaccuracy. This wouldn't be appropriate for a system where you are essentially dialing up (wheeling) to a game. After a bit of searching and reading I came across this: http://dmitrybrant.com/2008/04/29/binomial-coefficients-stirling-numbers-csharp

Turns out this is exactly the information I was looking for! The first method is accurate and plenty fast for anything I'm doing. Much thanks for psYchotic going to the trouble of joining just to post here!

Upvotes: 0

Views: 1396

Answers (1)

psYchotic
psYchotic

Reputation: 366

There are exactly 780 combinations of 2 numbers to generate out of a set of 40. If your combination generator uses a zero-based index, any index >= the maximum amount of combinations would be invalid. You can use the binomial coefficient to determine the number of combinations that can be formed.

Upvotes: 1

Related Questions