11
\$\begingroup\$

This is a rather complex but very interesting maths subject (known as "covering problem"),

And I'd like your help for implementing it.

Imagine a lottery game, where each ticket must choose 5 random numbers in a set of 50 numbers (from 1 to 50).

It's quite easy to know the probability of a winning ticket, or the probability to have 1, 2, 3 or 4 good numbers.

It's also quite easy to "generate" all the tickets that have 1, 2, 3, 4 good numbers.

My question (and code challenge) is related to this, but slightly different:

I want to buy some lottery tickets (the fewest possible), such as at least one of my tickets has 3 good numbers.

Challenge

Your goal is to implement a generic solution (as a program or just a function), like this, in any language:

// Input: 3 prameters
min_lottery_tickets(total_numbers_to_choose_from, how_many_numbers_to_choose, how_many_good_numbers_i_want)

For the above example, one would just have to call:

min_lottery_tickets(50, 5, 3)

and the program will generate the smallest set of tickets to play to achieve this goal.


Example:

 min_lottery_tickets(10, 5, 2)

would output 7 tickets, like those:

1   2   3   4   5
5   6   7   8   9
10  1   2   6   7
10  3   4   8   9
3   4   6   7   8
1   2   3   8   9
1   4   9   5   10

because such tickets are enough to cover any pair of numbers from 1 to 10.


Output

Text, one line per ticket, tabulations or spaces between numbers


who wins

The most efficient program wins (i.e. the program generating the fewest tickets for the above parameters):

min_lottery_tickets(50, 5, 3)


Thanks!

\$\endgroup\$
10
  • \$\begingroup\$ Related. \$\endgroup\$ Dec 11, 2013 at 10:57
  • 4
    \$\begingroup\$ This question needs various clarifications. Are you after a program, a function, or either? Does the output format matter? Do the numbers have to be indexed from 1, or could they be indexed from 0? And what's the objective winning condition? \$\endgroup\$ Dec 11, 2013 at 10:58
  • 3
    \$\begingroup\$ @xem this almost belongs on Math SE then. Where they will probably prove to you that the numbers aren't in your favour(though there does exist some jackpot number s.t it's worth buying tickets) \$\endgroup\$
    – Cruncher
    Dec 11, 2013 at 16:02
  • 2
    \$\begingroup\$ What is a good number? \$\endgroup\$
    – DavidC
    Dec 11, 2013 at 22:34
  • 2
    \$\begingroup\$ I'm pretty sure that it's provable that you will lose a lot of money if you actually go buy the tickets output by such a program. \$\endgroup\$ Dec 15, 2013 at 21:15

1 Answer 1

1
\$\begingroup\$

I know it's not optimal, but here is the code in node.js:

function min_lottery_tickets(total_numbers_to_choose_from, how_many_numbers_to_choose, how_many_good_numbers_i_want) {
    c(function(result) {
        var other = result[result.length - 1];
        while (result.length < how_many_numbers_to_choose) {
            other++;
            var already = false;
            for (var i = 0; i < result.length; i++) {
                if (other === result[i]) {
                    already = true;
                    break;
                }
            }
            if (!already) {
                result.push(other);            
            }
        }
        if (other <= total_numbers_to_choose_from) {
            // Print results
            console.log(result);
        }
    }, total_numbers_to_choose_from, how_many_good_numbers_i_want);
}

function c(next, total_numbers, length, start, results) {
    if (!start) start = 1;
    if (!results) results = [];

    for (var i = start; i <= total_numbers + 1 - length; i++) {
        var resultsNew = results.slice(0);
        resultsNew.push(i);
        if (length > 1) {
            c(next, total_numbers, length - 1, i + 1, resultsNew);
        } else {
            next(resultsNew);
        }
    }
}

Some example results:

> min_lottery_tickets(5, 3, 2)
[ 1, 2, 3 ]
[ 1, 3, 4 ]
[ 1, 4, 5 ]
[ 2, 3, 4 ]
[ 2, 4, 5 ]
[ 3, 4, 5 ]

other:

> min_lottery_tickets(10, 5, 2)
[ 1, 2, 3, 4, 5 ]
[ 1, 3, 4, 5, 6 ]
[ 1, 4, 5, 6, 7 ]
[ 1, 5, 6, 7, 8 ]
[ 1, 6, 7, 8, 9 ]
[ 1, 7, 8, 9, 10 ]
[ 2, 3, 4, 5, 6 ]
[ 2, 4, 5, 6, 7 ]
[ 2, 5, 6, 7, 8 ]
[ 2, 6, 7, 8, 9 ]
[ 2, 7, 8, 9, 10 ]
[ 3, 4, 5, 6, 7 ]
[ 3, 5, 6, 7, 8 ]
[ 3, 6, 7, 8, 9 ]
[ 3, 7, 8, 9, 10 ]
[ 4, 5, 6, 7, 8 ]
[ 4, 6, 7, 8, 9 ]
[ 4, 7, 8, 9, 10 ]
[ 5, 6, 7, 8, 9 ]
[ 5, 7, 8, 9, 10 ]
[ 6, 7, 8, 9, 10 ]

other:

> min_lottery_tickets(10, 5, 3)
[ 1, 2, 3, 4, 5 ]
[ 1, 2, 4, 5, 6 ]
[ 1, 2, 5, 6, 7 ]
[ 1, 2, 6, 7, 8 ]
[ 1, 2, 7, 8, 9 ]
[ 1, 2, 8, 9, 10 ]
[ 1, 3, 4, 5, 6 ]
[ 1, 3, 5, 6, 7 ]
[ 1, 3, 6, 7, 8 ]
[ 1, 3, 7, 8, 9 ]
[ 1, 3, 8, 9, 10 ]
[ 1, 4, 5, 6, 7 ]
[ 1, 4, 6, 7, 8 ]
[ 1, 4, 7, 8, 9 ]
[ 1, 4, 8, 9, 10 ]
[ 1, 5, 6, 7, 8 ]
[ 1, 5, 7, 8, 9 ]
[ 1, 5, 8, 9, 10 ]
[ 1, 6, 7, 8, 9 ]
[ 1, 6, 8, 9, 10 ]
[ 1, 7, 8, 9, 10 ]
[ 2, 3, 4, 5, 6 ]
[ 2, 3, 5, 6, 7 ]
[ 2, 3, 6, 7, 8 ]
[ 2, 3, 7, 8, 9 ]
[ 2, 3, 8, 9, 10 ]
[ 2, 4, 5, 6, 7 ]
[ 2, 4, 6, 7, 8 ]
[ 2, 4, 7, 8, 9 ]
[ 2, 4, 8, 9, 10 ]
[ 2, 5, 6, 7, 8 ]
[ 2, 5, 7, 8, 9 ]
[ 2, 5, 8, 9, 10 ]
[ 2, 6, 7, 8, 9 ]
[ 2, 6, 8, 9, 10 ]
[ 2, 7, 8, 9, 10 ]
[ 3, 4, 5, 6, 7 ]
[ 3, 4, 6, 7, 8 ]
[ 3, 4, 7, 8, 9 ]
[ 3, 4, 8, 9, 10 ]
[ 3, 5, 6, 7, 8 ]
[ 3, 5, 7, 8, 9 ]
[ 3, 5, 8, 9, 10 ]
[ 3, 6, 7, 8, 9 ]
[ 3, 6, 8, 9, 10 ]
[ 3, 7, 8, 9, 10 ]
[ 4, 5, 6, 7, 8 ]
[ 4, 5, 7, 8, 9 ]
[ 4, 5, 8, 9, 10 ]
[ 4, 6, 7, 8, 9 ]
[ 4, 6, 8, 9, 10 ]
[ 4, 7, 8, 9, 10 ]
[ 5, 6, 7, 8, 9 ]
[ 5, 6, 8, 9, 10 ]
[ 5, 7, 8, 9, 10 ]
[ 6, 7, 8, 9, 10 ]
\$\endgroup\$
6
  • 1
    \$\begingroup\$ Your min_lottery_tickets(10, 5, 2) generates much more solutions than OP's. \$\endgroup\$
    – vgru
    Jan 14, 2014 at 15:25
  • \$\begingroup\$ I know @Groo, I said I knew it was not optimal, but this was the first working version I had ;) Any suggestion on how to remove "redundant" results? \$\endgroup\$
    – greuze
    Jan 14, 2014 at 16:58
  • \$\begingroup\$ Hi Groo, Hi greuze, thanks a lot for this first attempt. You have a score of 21 (because you generated 21 tickets for (10,5,2)). I don't know how to remove the redundant results however, that's why I created this topic. I'm still wondering what the best algorithm to do this job looks like. \$\endgroup\$
    – xem
    Jan 15, 2014 at 12:30
  • \$\begingroup\$ Here are some good readings on the subject: (1) dip.sun.ac.za/~vuuren/papers/lotery_artikel1oud.pdf, (2) goo.gl/Ex7Woa, (3) google.fr/… \$\endgroup\$
    – xem
    Jan 15, 2014 at 12:32
  • 1
    \$\begingroup\$ It's a NP-complete problem, so I'm afraid there's no magic solution. We have to "brute force" the computation of all possible tickets and the elimination of those who are redundant by comparing each of its group of numbers to all the other tickets. That would take an exponential time. \$\endgroup\$
    – xem
    Jan 16, 2014 at 16:21

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.