Announcement

Collapse
No announcement yet.

Programming Problem

Collapse
X
 
  • Filter
  • Time
  • Show
Clear All
new posts

  • Programming Problem

    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.
    Neil Croft (cissp)

  • #2
    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
    Engineer's Motto: If it aint broke take it apart and fix it

    "If at 1st you don't succeed... call it version 1.0"

    "Half of Programming is coding"....."The other 90% is DEBUGGING"

    "Document my code????" .... "WHYYY??? do you think they call it CODE? "

    Comment


    • #3
      Originally posted by Cliff Nichols View Post
      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.

      Originally posted by Cliff Nichols View Post
      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.
      Neil Croft (cissp)

      Comment


      • #4
        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.

        Comment


        • #5
          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.
          Neil Croft (cissp)

          Comment


          • #6
            Originally posted by Neil Croft View Post
            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.

            Comment


            • #7
              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.
              Neil Croft (cissp)

              Comment


              • #8
                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
                Eddy

                Comment


                • #9
                  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

                  Comment


                  • #10
                    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.

                    Code:
                    #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.
                    Neil Croft (cissp)

                    Comment


                    • #11
                      Just a start, but there is a kind of pattern. I haven't figured out the verify proof logic yet tho.
                      Code:
                      #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

                      Comment


                      • #12
                        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.
                        Michael Mattias
                        Tal Systems (retired)
                        Port Washington WI USA
                        [email protected]om
                        http://www.talsystems.com

                        Comment


                        • #13
                          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.
                          Neil Croft (cissp)

                          Comment


                          • #14
                            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
                            Rod
                            In some future era, dark matter and dark energy will only be found in Astronomy's Dark Ages.

                            Comment


                            • #15
                              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.
                              Last edited by Tom Ulrich; 30 May 2008, 09:12 AM. Reason: 2,073,848 should have been 2,111,733

                              Comment


                              • #16
                                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.

                                Comment


                                • #17
                                  Originally posted by Neil Croft View Post
                                  ....
                                  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


                                  Code:
                                  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
                                  Last edited by StanHelton; 31 May 2008, 08:51 PM. Reason: Clarify solution - add DEFLNG to make compilable
                                  Do not go quiet into that good night,
                                  ... Rage, rage against the dark.

                                  Comment


                                  • #18
                                    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
                                    Rod
                                    In some future era, dark matter and dark energy will only be found in Astronomy's Dark Ages.

                                    Comment


                                    • #19
                                      Originally posted by Rodney Hicks View Post
                                      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
                                      Do not go quiet into that good night,
                                      ... Rage, rage against the dark.

                                      Comment


                                      • #20
                                        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
                                        Code:
                                        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
                                        Last edited by Rodney Hicks; 1 Jun 2008, 02:29 AM. Reason: bad grammar, she was supposed to be in the kitchen.
                                        Rod
                                        In some future era, dark matter and dark energy will only be found in Astronomy's Dark Ages.

                                        Comment

                                        Working...
                                        X