Programming Problem

[Neil Croft]

I've been trying to "solve" a problem and I've run into a pretty solid wall and need some ideas. Here's the problem put as simply as I can. Note this is a problem in combinatrics, not a lottery problem.

Imagine a 6 from 49 lottery where 6 balls are drawn at random from a set of 49 without replacement. Order is unimportant. How many tickets/lines of numbers would I need to buy to guarantee at least 2 matches on one line?

The current best is 19 lines. http://lottery.merseyworld.com/Wheel/

So, how far have I got?

Each line is 0<n1<n2<n3<n4<n5<n6<50 which gives 13983816 possible lines from 1,2,3,4,5,6 to 44,45,46,47,48,49.

Option 1 - Brute Force
Working on proving if there's an 18 line option for 2 matches, this gives 6.5300550628388e+112 possible variations to test. Assuming 0.1 seconds per test on each combination, a brute force attempt would take 2.07e+104 years. Even spread across all 10 CPUs here and allowing a bit for Moore's Law would maybe cut it down to 2e+100 years. Patently not an option in my lifetime.

Option 2 - Monte Carlo
Monte Carlo is a means of solving a problem whereby a random starting point is continually modified. Modifications that result in an improved outcome are retained. Modifications that result in a worsened outcome are rejected. By changing one or more numbers at a time, I have managed to achieve 99.9549% coverage by using the first 18 lines of the 19 lines as a start point. Monte Carlo methods haven't actually improved on that start point however one limitation of Monte Carlo methods is they're prone to get stuck in local minima solutions. Running with a random start point generally gets to 99.2% and seemingly gets stuck.

Option 3 - Ask for help and suggestions
That'll be where I am now. Can anyone suggest ways of working out what the minimum number of lines is and/or working out what those lines are?

BTW, I asked this on a maths forum and they didn't seem to think it could be done in 19 lines which was a little worrying.

[Cliff Nichols]

Neil,
Stop trying to beat the Mega-Millions Jackpot lotto

(sorry, just had to say it )

What I do, know is statistically, you can drill down the odds, but then again I barely passed "Statistics 101", and my answer to the the professors last question on the final exam was like the following

Name 1 thing you learned in this class

My answer: "Given any set of numbers, I can prove the sun rises in the west....but that does NOT make it true"

Sorry I do not have an answer for you, but someone more mathematically inclined might, but I thought you would like the story as well

[Neil Croft]

Neil,
Stop trying to beat the Mega-Millions Jackpot lotto

(sorry, just had to say it )

I stopped trying that a long time ago. I buy one line a week 'cos the day I can't afford to waste £1 is the day after I die.

Sorry I do not have an answer for you, but someone more mathematically inclined might, but I thought you would like the story as well

If I've kicked one brain cell into action, even a non-maths one, then it's not a waste of time.

[Donald Darden]

This is one of the most popular themes on the Internet. The odds and the algorythms for projecting those odds are posted many places. I suggest you look for lottery calculator, lottery odds, or lottery odds calculator in your search.

I actually have working programs in Excel and in PowerBasic for making my own determinations, and I found it an interesting subject at one time. But megalottos have put the odds of winning to such a remote extreme that I gave up an active interest in playing many years ago. Calculating the odds is just a waste of time after that.

Note, that I also found that the lotteries themselves post the odds of winning, And there are books written about playing strategies, such as the art of Wheeling. Wheeling is taking a group of numbers, say your 9 favorite numbers, then playing them in arrangements of six numbers each. How many lines would you have to play to maximize your potential of winning on any combination of those 9 numbers? The idea is that if you can narrow the probabilities to the best 8 or 9 numbers, and say five of six numbers that are drawn actually are among those numbers you pick, then one of those lines may have 4 or 5 of those numbers on it.

It's still a risk, of course, but it only depends on whether you are able to pick numbers that have a better chance of coming up. That's where people hope to get lucky or use a process of elemination.

There are different strategies for Wheeling, which depend on the number of preferred numbers you want to play, how many numbers you want combined minimum per line, and how many lines you want to play. You might want to try your hand at programming a Wheeling program that works this out for you. And of course you can find lottery wheels and lottery wheeling systems on the Internet as well.

Everybody believes that they can play and eventually beat the odds. If you take comfort in this, then I suggest you ignore the odds altogether. They are not encouraging, and for megagames, they are the absolute pits.

[Neil Croft]

Donald, you've missed the line that says

Note this is a problem in combinatrics, not a lottery problem.

. Like the Travelling Salesman problem doesn't actually require us to hop in the car and drive around loads of strange town and note the mileage. The exercise is to find a better algorithm. Every Lottery site I've seen concentrates on "beating the odds" and I'm a man of logic and will quite happily use a pin to pick numbers to beat the lottery with equal success to any software.

Regardless of any logic people who buy that stuff should conside this. If I did write a program that could pick winning lottery numbers, 1) why would I want to share it? 2) Why would I need to share it?

Forget the lottery. Imagine 49 germs of which 6 are present in any person and you can only give them 18 antibiotics of which there are 13983816 different varieties and you want to kill at least 2 germs in every person and each antibiotic can kill 6 different germs. Whatever gets your programming juices flowing.

The exercise is to find an algorithm that proves or disproves the solution can be calculated in less than a planet's lifetime, not win the lottery.

[Chris Holbrook]

Every Lottery site... beat the lottery...pick winning lottery ...Forget the lottery... not win the lottery.

Neil, in these forums such nuances of meaning are best avoided unless they can be expressed in code.

I liked the one about the germs though.

[Neil Croft]

Chris,

With hindsight re-expressing the problem before posting may have avoided the "L word" associations. It's quite scary the number of people who exert extreme amounts of effort to try and predict the unpredictable although it's also interesting to see how people approach solving that "problem".

It's interesting (and slightly related) to hear relatives at family gatherings asking why computers can't do X yet, where X is curing cancer (BOINC, they do), Answer the meaning of life (SETI?), make a cup of tea (I'm sure I could modify a water CPU cooler ), etc. As a home computer owner since 1982 (Sinclair Spectrum Yay!) I've always been more interested in programming and the algorithms rather than the end use albeit the end use indirectly pays my mortgage (I'm an IT security consultant).

This particular conundrum should be eminently calculable though. It's simple pattern matching for goodness sake. Even good suggestions of ways to parallelize the code to share it around the heap of tin around the house would be welcome. I looked at BOINC but my C skills are poor to say the least. Just tracking the problem space is vast and so just trying to track what 10 or so CPUs had checked made my brain pop.

[Eddy Van Esch]

Neil,

If you would like to experiment with some kind of brute-forcing method, I can possibly get you in touch with a guy who has developed a client-server application for distributed calculations (a SETI-like setup).
Last time I talked to him he was looking for an experiment to put his system to the test.

Drop me a private mail if you think this could be of use to you.

Kind regards

[John Gleason]

Neil, would it be of benefit to increase the number of tests per second you can run? Ten per second is not too many. A 2Ghz processor translates to 200 million ticks per test. Oof. I have to believe I can improve on that. I count 1176 combos on 18 or 19 lines of 15 combos each or say 285 combos. Thats 335,000 tests on a 1 to 1 basis or 600 ticks per test. Maybe I can get it down to like 60, or yow, 6. hehheh

[Neil Croft]

10/second was a conservative estimate but given the truly vast number of tests required you'd have to go some. Still, along those lines....

Just to loop through the 6 options per line for 18 lines would require 108 nested loops which blows the stack and, as I've seen elsewhere in answers on here, if you're blowing the stack on nested loops it's time to reconsider the algorithm. Still, 18 loops is doable so the logic of my brute force program is basically the following. There's a small piece of code that saves progress every 10k iterations and loads up the data first time around so as not to completely start from scratch each run but I've taken that out for clarity. I suspect using the P&() array directly instead of transposing into W&() would save me a bunch of cycles and that's my current task.

Note, using the big P&() array saves the stack but uses 330k of RAM when running. Not for the faint hearted or those with smaller machines.

#INCLUDE "win32api.inc"
FUNCTION PBMAIN () AS LONG
    ' Use spare cyles so we don't kill the machine
    ff&=SetPriorityClass(GetCurrentProcess, %IDLE_PRIORITY_CLASS)
    ' Name the console so we know what's running
    CONSOLE NAME "18 lines - 2 from 49"
    ' save some time
    REGISTER f&
    REGISTER g&
    '
    ta&=13983816
    '
    ' store all possibilities
    DIM p&(1 TO ta&,1 TO 6)
    '
    ta&=0
    '
    ' set the possibilities array
    FOR a&=1 TO 44
        FOR b&=a&+1 TO 45
            FOR c&=b&+1 TO 46
                FOR d&=c&+1 TO 47
                    FOR e&=d&+1 TO 48
                        FOR f&=e&+1 TO 49
                            INCR ta&
                            p&(ta&,1)=a&
                            p&(ta&,2)=b&
                            p&(ta&,3)=c&
                            p&(ta&,4)=d&
                            p&(ta&,5)=e&
                            p&(ta&,6)=f&
                        NEXT
                    NEXT
                NEXT
            NEXT
        NEXT
    NEXT
    '
    'current set array
    DIM w&(1 TO 18,1 TO 49)
    '
    ' if a solution exists it will have 1,2,3,4,5,6 as first line
    l1&=1
    w&(1,1)=1
    w&(1,2)=1
    w&(1,3)=1
    w&(1,4)=1
    w&(1,5)=1
    w&(1,6)=1
    FOR l2&=2 TO 13983799
        w&(2,p&(l2&,1))=1
        w&(2,p&(l2&,2))=1
        w&(2,p&(l2&,3))=1
        w&(2,p&(l2&,4))=1
        w&(2,p&(l2&,5))=1
        w&(2,p&(l2&,6))=1
    FOR l3&=l2&+1 TO 13983800
        w&(3,p&(l3&,1))=1
        w&(3,p&(l3&,2))=1
        w&(3,p&(l3&,3))=1
        w&(3,p&(l3&,4))=1
        w&(3,p&(l3&,5))=1
        w&(3,p&(l3&,6))=1
    FOR l4&=l3&+1 TO 13983801
        w&(4,p&(l4&,1))=1
        w&(4,p&(l4&,2))=1
        w&(4,p&(l4&,3))=1
        w&(4,p&(l4&,4))=1
        w&(4,p&(l4&,5))=1
        w&(4,p&(l4&,6))=1
    FOR l5&=l4&+1 TO 13983802
        w&(5,p&(l5&,1))=1
        w&(5,p&(l5&,2))=1
        w&(5,p&(l5&,3))=1
        w&(5,p&(l5&,4))=1
        w&(5,p&(l5&,5))=1
        w&(5,p&(l5&,6))=1
    FOR l6&=l5&+1 TO 13983803
        w&(6,p&(l6&,1))=1
        w&(6,p&(l6&,2))=1
        w&(6,p&(l6&,3))=1
        w&(6,p&(l6&,4))=1
        w&(6,p&(l6&,5))=1
        w&(6,p&(l6&,6))=1
    FOR l7&=l6&+1 TO 13983804
        w&(7,p&(l7&,1))=1
        w&(7,p&(l7&,2))=1
        w&(7,p&(l7&,3))=1
        w&(7,p&(l7&,4))=1
        w&(7,p&(l7&,5))=1
        w&(7,p&(l7&,6))=1
    FOR l8&=l7&+1 TO 13983805
        w&(8,p&(l8&,1))=1
        w&(8,p&(l8&,2))=1
        w&(8,p&(l8&,3))=1
        w&(8,p&(l8&,4))=1
        w&(8,p&(l8&,5))=1
        w&(8,p&(l8&,6))=1
    FOR l9&=l8&+1 TO 13983806
        w&(9,p&(l9&,1))=1
        w&(9,p&(l9&,2))=1
        w&(9,p&(l9&,3))=1
        w&(9,p&(l9&,4))=1
        w&(9,p&(l9&,5))=1
        w&(9,p&(l9&,6))=1
    FOR l10&=l9&+1 TO 13983807
        w&(10,p&(l10&,1))=1
        w&(10,p&(l10&,2))=1
        w&(10,p&(l10&,3))=1
        w&(10,p&(l10&,4))=1
        w&(10,p&(l10&,5))=1
        w&(10,p&(l10&,6))=1
    FOR l11&=l10&+1 TO 13983809
        w&(11,p&(l11&,1))=1
        w&(11,p&(l11&,2))=1
        w&(11,p&(l11&,3))=1
        w&(11,p&(l11&,4))=1
        w&(11,p&(l11&,5))=1
        w&(11,p&(l11&,6))=1
    FOR l12&=l11&+1 TO 13983810
        w&(12,p&(l12&,1))=1
        w&(12,p&(l12&,2))=1
        w&(12,p&(l12&,3))=1
        w&(12,p&(l12&,4))=1
        w&(12,p&(l12&,5))=1
        w&(12,p&(l12&,6))=1
    FOR l13&=l12&+1 TO 13983811
        w&(13,p&(l13&,1))=1
        w&(13,p&(l13&,2))=1
        w&(13,p&(l13&,3))=1
        w&(13,p&(l13&,4))=1
        w&(13,p&(l13&,5))=1
        w&(13,p&(l13&,6))=1
    FOR l14&=l13&+1 TO 13983812
        w&(14,p&(l14&,1))=1
        w&(14,p&(l14&,2))=1
        w&(14,p&(l14&,3))=1
        w&(14,p&(l14&,4))=1
        w&(14,p&(l14&,5))=1
        w&(14,p&(l14&,6))=1
    FOR l15&=l14&+1 TO 13983813
        w&(15,p&(l15&,1))=1
        w&(15,p&(l15&,2))=1
        w&(15,p&(l15&,3))=1
        w&(15,p&(l15&,4))=1
        w&(15,p&(l15&,5))=1
        w&(15,p&(l15&,6))=1
    FOR l16&=l15&+1 TO 13983814
        w&(16,p&(l16&,1))=1
        w&(16,p&(l16&,2))=1
        w&(16,p&(l16&,3))=1
        w&(16,p&(l16&,4))=1
        w&(16,p&(l16&,5))=1
        w&(16,p&(l16&,6))=1
    FOR l17&=l16&+1 TO 13983815
        w&(17,p&(l17&,1))=1
        w&(17,p&(l17&,2))=1
        w&(17,p&(l17&,3))=1
        w&(17,p&(l17&,4))=1
        w&(17,p&(l17&,5))=1
        w&(17,p&(l17&,6))=1
    FOR l18&=l17&+1 TO 13983816
        w&(18,p&(l18&,1))=1
        w&(18,p&(l18&,2))=1
        w&(18,p&(l18&,3))=1
        w&(18,p&(l18&,4))=1
        w&(18,p&(l18&,5))=1
        w&(18,p&(l18&,6))=1
        '
        'so that's 18 (17 really) loops picking out each line from the possibilities
        co&=0
        FOR a&=1 TO 44
            FOR b&=a&+1 TO 45
                FOR c&=b&+1 TO 46
                    FOR d&=c&+1 TO 47
                        FOR e&=d&+1 TO 48
                            FOR f&=e&+1 TO 49
                                ok&=0
                                FOR g&=1 TO 18
                                    s&=w&(g&,a&)+w&(g&,b&)+w&(g&,c&)+w&(g&,d&)+w&(g&,e&)+w&(g&,f&)
                                    'if it got a 2 match thn we can proceed
                                    IF s&>1 THEN ok&=1:EXIT
                                NEXT
                                ' if we didn't get a match then that set of 18 is no good. Move on.
                                IF ok&=0 THEN EXIT,EXIT,EXIT,EXIT,EXIT,EXIT
                                INCR co&
                                '
                            NEXT
                        NEXT
                    NEXT
                NEXT
            NEXT
        NEXT
        '
        ' show some progress
        IF co&>bco& THEN
            bco&=co&
            PRINT DATE$;" ";TIME$;bco&;ta&-bco&;FORMAT$(bco&/ta&,"##.00000%")
            FOR e&=1 TO 18
                FOR f&=1 TO 49
                    IF w&(e&,f&)=1 THEN PRINT f&;
                NEXT
                IF e&=1 THEN PRINT "",1
                IF e&=2 THEN PRINT "",l2&
                IF e&=3 THEN PRINT "",l3&
                IF e&=4 THEN PRINT "",l4&
                IF e&=5 THEN PRINT "",l5&
                IF e&=6 THEN PRINT "",l6&
                IF e&=7 THEN PRINT "",l7&
                IF e&=8 THEN PRINT "",l8&
                IF e&=9 THEN PRINT "",l9&
                IF e&=10 THEN PRINT "",l10&
                IF e&=11 THEN PRINT "",l11&
                IF e&=12 THEN PRINT "",l12&
                IF e&=13 THEN PRINT "",l13&
                IF e&=14 THEN PRINT "",l14&
                IF e&=15 THEN PRINT "",l15&
                IF e&=16 THEN PRINT "",l16&
                IF e&=17 THEN PRINT "",l17&
                IF e&=18 THEN PRINT "",l18&
            NEXT
            PRINT
            '
        END IF
        '
        ' if we get a solution then save it to disk.
        IF co&=ta& THEN
            ff&=FREEFILE
            OPEN "result.txt" FOR OUTPUT AS ff&
            FOR a&=1 TO 18
                FOR b&=1 TO 49
                    IF w&(a&,b&)=1 THEN PRINT# ff&,b&;
                NEXT
                PRINT# ff&,""
            NEXT
            CLOSE
        END IF
        '
        w&(18,p&(l18&,1))=0
        w&(18,p&(l18&,2))=0
        w&(18,p&(l18&,3))=0
        w&(18,p&(l18&,4))=0
        w&(18,p&(l18&,5))=0
        w&(18,p&(l18&,6))=0
    NEXT
        w&(17,p&(l17&,1))=0
        w&(17,p&(l17&,2))=0
        w&(17,p&(l17&,3))=0
        w&(17,p&(l17&,4))=0
        w&(17,p&(l17&,5))=0
        w&(17,p&(l17&,6))=0
    NEXT
        w&(16,p&(l16&,1))=0
        w&(16,p&(l16&,2))=0
        w&(16,p&(l16&,3))=0
        w&(16,p&(l16&,4))=0
        w&(16,p&(l16&,5))=0
        w&(16,p&(l16&,6))=0
    NEXT
        w&(15,p&(l15&,1))=0
        w&(15,p&(l15&,2))=0
        w&(15,p&(l15&,3))=0
        w&(15,p&(l15&,4))=0
        w&(15,p&(l15&,5))=0
        w&(15,p&(l15&,6))=0
    NEXT
        w&(14,p&(l14&,1))=0
        w&(14,p&(l14&,2))=0
        w&(14,p&(l14&,3))=0
        w&(14,p&(l14&,4))=0
        w&(14,p&(l14&,5))=0
        w&(14,p&(l14&,6))=0
    NEXT
        w&(13,p&(l13&,1))=0
        w&(13,p&(l13&,2))=0
        w&(13,p&(l13&,3))=0
        w&(13,p&(l13&,4))=0
        w&(13,p&(l13&,5))=0
        w&(13,p&(l13&,6))=0
    NEXT
        w&(12,p&(l12&,1))=0
        w&(12,p&(l12&,2))=0
        w&(12,p&(l12&,3))=0
        w&(12,p&(l12&,4))=0
        w&(12,p&(l12&,5))=0
        w&(12,p&(l12&,6))=0
    NEXT
        w&(11,p&(l11&,1))=0
        w&(11,p&(l11&,2))=0
        w&(11,p&(l11&,3))=0
        w&(11,p&(l11&,4))=0
        w&(11,p&(l11&,5))=0
        w&(11,p&(l11&,6))=0
    NEXT
        w&(10,p&(l10&,1))=0
        w&(10,p&(l10&,2))=0
        w&(10,p&(l10&,3))=0
        w&(10,p&(l10&,4))=0
        w&(10,p&(l10&,5))=0
        w&(10,p&(l10&,6))=0
    NEXT
        w&(9,p&(l9&,1))=0
        w&(9,p&(l9&,2))=0
        w&(9,p&(l9&,3))=0
        w&(9,p&(l9&,4))=0
        w&(9,p&(l9&,5))=0
        w&(9,p&(l9&,6))=0
    NEXT
        w&(8,p&(l8&,1))=0
        w&(8,p&(l8&,2))=0
        w&(8,p&(l8&,3))=0
        w&(8,p&(l8&,4))=0
        w&(8,p&(l8&,5))=0
        w&(8,p&(l8&,6))=0
    NEXT
        w&(7,p&(l7&,1))=0
        w&(7,p&(l7&,2))=0
        w&(7,p&(l7&,3))=0
        w&(7,p&(l7&,4))=0
        w&(7,p&(l7&,5))=0
        w&(7,p&(l7&,6))=0
    NEXT
        w&(6,p&(l6&,1))=0
        w&(6,p&(l6&,2))=0
        w&(6,p&(l6&,3))=0
        w&(6,p&(l6&,4))=0
        w&(6,p&(l6&,5))=0
        w&(6,p&(l6&,6))=0
    NEXT
        w&(5,p&(l5&,1))=0
        w&(5,p&(l5&,2))=0
        w&(5,p&(l5&,3))=0
        w&(5,p&(l5&,4))=0
        w&(5,p&(l5&,5))=0
        w&(5,p&(l5&,6))=0
    NEXT
        w&(4,p&(l4&,1))=0
        w&(4,p&(l4&,2))=0
        w&(4,p&(l4&,3))=0
        w&(4,p&(l4&,4))=0
        w&(4,p&(l4&,5))=0
        w&(4,p&(l4&,6))=0
    NEXT
        w&(3,p&(l3&,1))=0
        w&(3,p&(l3&,2))=0
        w&(3,p&(l3&,3))=0
        w&(3,p&(l3&,4))=0
        w&(3,p&(l3&,5))=0
        w&(3,p&(l3&,6))=0
    NEXT
        w&(2,p&(l2&,1))=0
        w&(2,p&(l2&,2))=0
        w&(2,p&(l2&,3))=0
        w&(2,p&(l2&,4))=0
        w&(2,p&(l2&,5))=0
        w&(2,p&(l2&,6))=0
    NEXT
    '
    PRINT "Done"
    WAITKEY$
    '
END FUNCTION

A better way of storing the P&() array (maybe 13983816x49 bytes and some clever memory reading using pointers) would be a better way forward but is a bit beyond my programming skills. Just doing a test on the 18 loops with nothing more than an incrementing counter displaying the time every 500,000,000 passes puts the time out just about every 6 seconds on my 3.6GHz xeon :goodboy: That suggests there's huge scope for improvement on my brute force method. Maybe time to go back to the drawing board there.

[John Gleason]

Just a start, but there is a kind of pattern. I haven't figured out the verify proof logic yet tho.

#COMPILE EXE
#DIM ALL

FUNCTION PBMAIN () AS LONG
    LOCAL ii, ii2, x, x2 AS LONG, tots AS STRING
    DIM comb(1 TO 1176) AS LONG, ticket(1 TO 19) AS QUAD
    DIM ticket2comb(285) AS LONG

'*********************************************************************************************************************
                    'enter ticket numbers left-zero-padded (this is the current record holder)
ticket(1) = &h010203040506
ticket(2) = &h010207080910
ticket(3) = &h010211121314
ticket(4) = &h030407081314
ticket(5) = &h030409101112
ticket(6) = &h050607081112
ticket(7) = &h050609101314
ticket(8) = &h151617181920
ticket(9) = &h151621222324
ticket(10) = &h151625262728
ticket(11) = &h171821222728
ticket(12) = &h171823242526
ticket(13) = &h192021222526
ticket(14) = &h192023242728
ticket(15) = &h293031323334
ticket(16) = &h353637383940
ticket(17) = &h414243444546
ticket(18) = &h414243474849
ticket(19) = &h444546474849

'*********************************************************************************************************************
FOR ii = 1 TO 19    'this loop converts the 6-number tickets above into all their possible 2 number combos.
   ii2 = (ii - 1) * 15 + 1
   ticket2comb(ii2+00) = (ticket(ii) AND &hff0000000000) \ &h000100000000 + (ticket(ii) AND &h00ff00000000) \ &h000100000000
   ticket2comb(ii2+01) = (ticket(ii) AND &hff0000000000) \ &h000100000000 + (ticket(ii) AND &h0000ff000000) \ &h000001000000
   ticket2comb(ii2+02) = (ticket(ii) AND &hff0000000000) \ &h000100000000 + (ticket(ii) AND &h000000ff0000) \ &h000000010000
   ticket2comb(ii2+03) = (ticket(ii) AND &hff0000000000) \ &h000100000000 + (ticket(ii) AND &h00000000ff00) \ &h000000000100
   ticket2comb(ii2+04) = (ticket(ii) AND &hff0000000000) \ &h000100000000 + (ticket(ii) AND &h0000000000ff)

   ticket2comb(ii2+05) = (ticket(ii) AND &h00ff00000000) \ &h000001000000 + (ticket(ii) AND &h0000ff000000) \ &h000001000000
   ticket2comb(ii2+06) = (ticket(ii) AND &h00ff00000000) \ &h000001000000 + (ticket(ii) AND &h000000ff0000) \ &h000000010000
   ticket2comb(ii2+07) = (ticket(ii) AND &h00ff00000000) \ &h000001000000 + (ticket(ii) AND &h00000000ff00) \ &h000000000100
   ticket2comb(ii2+08) = (ticket(ii) AND &h00ff00000000) \ &h000001000000 + (ticket(ii) AND &h0000000000ff)

   ticket2comb(ii2+09) = (ticket(ii) AND &h0000ff000000) \ &h000000010000 + (ticket(ii) AND &h000000ff0000) \ &h000000010000
   ticket2comb(ii2+10) = (ticket(ii) AND &h0000ff000000) \ &h000000010000 + (ticket(ii) AND &h00000000ff00) \ &h000000000100
   ticket2comb(ii2+11) = (ticket(ii) AND &h0000ff000000) \ &h000000010000 + (ticket(ii) AND &h0000000000ff)

   ticket2comb(ii2+12) = (ticket(ii) AND &h000000ff0000) \ &h000000000100 + (ticket(ii) AND &h00000000ff00) \ &h000000000100
   ticket2comb(ii2+13) = (ticket(ii) AND &h000000ff0000) \ &h000000000100 + (ticket(ii) AND &h0000000000ff)

   ticket2comb(ii2+14) = (ticket(ii) AND &h00000000ff00)                  + (ticket(ii) AND &h0000000000ff)

NEXT
'*********************************************************************************************************************
                    'this section sorts the ticket 2-digit combos, then removes dupes
ARRAY SORT ticket2comb()
x = 0
FOR ii = 1 TO 285
   IF ticket2comb(x) <> ticket2comb(ii) THEN
      INCR x
      ticket2comb(x) = ticket2comb(ii)
   END IF
   
NEXT
'*********************************************************************************************************************
                    'finally this part compares the ticket array to all 1176 possible combos, and prints the
                    'result to a file. The file should be viewed with word-wrap OFF to see the pattern. You can
                    'use WordPad for example to do this.
    x = 0
    x2 = 1
    FOR ii = 1 TO 49
       FOR ii2 = ii + 1 TO 49
          INCR x
          comb(x)  = VAL("&h" & FORMAT$(ii * 100 + ii2, "0000"))

          IF comb(x) = ticket2comb(x2) THEN
             comb(x) = &h08888
             INCR x2
          END IF
          tots = tots & HEX$(comb(x), 4) & ","

       NEXT
          tots = tots & $CRLF
    NEXT
                      
    REPLACE "8888" WITH "####" IN tots
    OPEN "c:\totsCombinatrixFile2.txt" FOR BINARY AS #1
    PUT #1, ,tots
    CLOSE
   ? "Data saved in: c:\totsCombinatrixFile2.txt"

END FUNCTION

[Michael Mattias]

For better performance, use zero-based arrays instead of one-based arrays - "as documented in the help file."

But yes you are correct, by using pointer variables you could moot the perfomance benefits of zero-based arrays.

[Neil Croft]

John,

I can see where you're heading with that and it's an interesting visualisation concept. I need to get my head around how I can go further with that.

Michael,

Well noted. Force of habit is to declare the lower bound 'cos usually I don't need the speed and have been burned before when doing array sorts.

Now I need to go and look at some pointer examples.

[Rodney Hicks]

You might choose the Brute Force method because:

Most of the work has been done for you

19 combinations give you 19*15=285
18 combinations give you 18*15=270

There are 19*6=114 numbers in the 19 combinations.
Therefore some numbers appear twice, others thrice. Perhaps others once.

Derive all combinations from each set of numbers, store in an array
sets(19,15,2) or sets$(19,15)
Once array sets() is full, parse the array to find all duplicate twosomes.

Count the number of duplicated twosomes. If less that 15 you will not be able to find an 18 piece subset to satisfy your needs or curiosity.

However a quick look at the set of 19 tells me that there should be in excess of 15 twosomes that are duplicated.

So if you count the different numbers in the duplicates and see if there is a preponderance of any certain numbers, ie, that the numbers are not evenly distributed, which I've already shown you that they aren't, you can then try to fashion your 18 piece subset by removing instances of the numbers with a higher count.

Any 18 piece subset is going to include the numbers of the 19 piece subset, therefore making millions of calculation on all possible combinations seems redundant. You have fewer than 300 comparisons to make.

Rod

[Tom Ulrich]

Another approach:

Think of it as a tree... Try to reduce the branches.

1 to 49 pick 6 results in 49!/(6! 43!)=13,983,816 possible.

In the 19 tickets there are tickets 1,8,15 and 19 with consecutive numbers.
ticket 1:1,2,3,4,5,6
ticket 8:15,16,17,18,19,20
ticket 15:29,30,31,32,33,34
ticket 19:44,45,46,47,48,49

Take ticket 1: 1,2,3,4,5,6
If I did my math correctly...(used hypergeometric formula)
matches of 2 or more =2,111,733

This now reduces the 13,983,816 possible to:
13,983,816-2,111,733=11,872,043

The next ticket will have some overlap and give less than 2,111,733 matches.

If an array held all the possible then trim out the matches for the 1st ticket. With this now trimmed array take out the next matches.

See if a different ticket reduced it more or not. Once a 2nd ticket is chosen, repeat for the next tickets.

[Tom Ulrich]

http://www.cs.umanitoba.ca/~vanrees/Lotto.pdf

Lemma 4.19 L(49,6,6,2)=19

"Lotto Designs" by J.A. Bate & G.H.J. van Rees, J. Comb. Math. & Comb. Computing, V28 (1998) 15-39.

Unless the professors at University of Manitoba and the reviewers blundered, 19 is the best one can get.

[StanHelton]

....
Forget the lottery. Imagine 49 germs of which 6 are present in any person and you can only give them 18 antibiotics of which there are 13983816 different varieties and you want to kill at least 2 germs in every person and each antibiotic can kill 6 different germs. Whatever gets your programming juices flowing.

The exercise is to find an algorithm that proves or disproves the solution can be calculated in less than a planet's lifetime, not win the lottery.

Okay.


My first attempt:

Total # of infected persons = unlimited
Total # of antibx that kill 6 germs = 13 million plus
Total # of germs = 49
Total # of germs in each infected person = 6
Max # of vacinations = 18

Goal: kill at least 2 germs in every infected person without exceeding the max # of vacinations

49 Cr 6 = >13.98E+6
49 Cr 2 = 1,176 unique pairs of germs

18 sets of 6 -> maximum number of unique sets of six
OR
18 sets x 3 unique pairs per set = 54 unique pairs

Conclusion: solution is not possible as it will miss 1,122 unique pairs of germs.


My second attempt:

given 49 germs
given 13 million plus antibx that kill 6 germs

solution:
select 8 antibx with completely unique sets of 6 (48 germs killed)
AND
a 9th antibx that includes at least one instance of germ #49

DEFLNG a-z
%False = 0
%True = NOT %False
 

FUNCTION KillThoseNastyGerms() AS LONG

'initialize the germs
DIM GermSet(48) AS LONG
FOR x = 0 TO 48
   GermSet(x) = x
NEXT x

'randomize the antibx
DIM AntibxSet(13983815, 5) AS LONG
FOR x = 0 TO 13983815
   FOR y = 0 TO 5
      AntibxSet(x, y) = RND(0, 48)
   NEXT y
NEXT x

'solution set
DIM VacinationSet(1 TO 9) AS GLOBAL LONG

VacAntibx = 0
GermsKilled = 0
Success = %False

FOR x = 0 TO 13983815   'checking each antibx in turn
   FOR y = 0 TO 5           'find unique antibx
      IF GermSet(AntibxSet(x, y)) >= 0 THEN INCR UniqueFlag
   NEXT y

   IF UniqueFlag = 6 _
   AND GermsKilled < 48 THEN              'add unique antibx to vacination list
      VacinationSet(AntibxIndexNo) = x
      INCR AntibxIndexNo
      FOR y = 0 TO 5
         GermSet(AntibxSet(x, y)) = -1
      NEXT y
      GermsKilled = GermsKilled + 6
   ELSEIF UniqueFlag > 0 _
   AND GermsKilled = 48 THEN               'select 9th antibx
      VacinationSet(AntibxIndexNo) = x
      GermsKilled = GermsKilled + 1
   END IF
   UniqueFlag = 0

   IF GermsKilled = 49 THEN
      'double check the solution
      FOR y = 0 TO 48
         IF GermSet(y) < 0 THEN
            GermsKilled = GermsKilled + GermSet(y)
         END IF
      NEXT y
      IF GermsKilled <> 0 THEN
         Success = %False
      ELSE
         Success = %True
         EXIT FOR
      END IF
   END IF
NEXT x

IF ISTRUE Success THEN
   'do whatever with the VacinationSet()
ELSEIF ISFALSE Success THEN
   'research more antibx!
END IF

FUNCTION = Success
END FUNCTION

It won't win the lottery, but it might save the poor patient 9 injections... AND it kills all 6 germs in every patient.

Stan

[Rodney Hicks]

18 sets of 6 -> maximum number of unique sets of six
OR
18 sets x 3 unique pairs per set = 54 unique pairs

In each set of 6 there are 15 unique pairs so the last line above should read:
18 sets x15 unique pairs=270 unique pairs

In the original group of 19 sets of 6 there were 285 number pairs, with some duplication, however there are in that 19 sets of 6 248 discreet pairs which means that there are 37 duplicates. Those 37 duplicates are the key to reducing 19 to 18( or time willing 17) sets of 6.

Rod

[StanHelton]

In each set of 6 there are 15 unique pairs so the last line above should read:
18 sets x15 unique pairs=270 unique pairs

In the original group of 19 sets of 6 there were 285 number pairs, with some duplication, however there are in that 19 sets of 6 248 discreet pairs which means that there are 37 duplicates. Those 37 duplicates are the key to reducing 19 to 18( or time willing 17) sets of 6.

Rod

I stand corrected.

My math is not as strong as yours. How do you arrive at 285 number pairs in the 19 sets of 6?

Stan

[Rodney Hicks]

A set of 6 --1,2,3,4,5,6

There are 6 choices for the first digit* 5 choices for the second digit=30 digits.
Since we are using 2 at a time, we divide by 2 to get 15
Each number will appear 5 times in the 15 sets of 2

1,2  1,3  1,4  1,5  1,6
     2,3  2,4  2,5  2,6
          3,4  3,5  3,6
               4,5  4,6
                    5,6

Therefore in 19 sets, there ar 19 *15= 285.
If you look at the 19 sets from that first link in this thread you'll find there are duplicates.
The 248 discreet pairs could be divided by 15 to show the absolute minimum number of 6 number sets required. (17)
Those 17 sets of 6 would still leave you with 7 duplicates.

Rod