Generieren Sie die wenigsten Lottoscheine, um mindestens N gute Zahlen zu haben

Dies ist ein ziemlich komplexes, aber sehr interessantes Mathematikfach (bekannt als "Deckungsproblem" ).

Und ich hätte gerne Ihre Hilfe bei der Implementierung.

Stellen Sie sich ein Lotteriespiel vor, bei dem jedes Ticket 5 Zufallszahlen in einem Satz von 50 Zahlen (von 1 bis 50) auswählen muss.

Es ist ziemlich einfach, die Wahrscheinlichkeit eines Gewinnscheins oder die Wahrscheinlichkeit von 1, 2, 3 oder 4 guten Zahlen zu kennen.

Es ist auch ziemlich einfach, alle Tickets mit 1, 2, 3, 4 guten Zahlen zu "generieren".

Meine Frage (und Code-Herausforderung) hängt damit zusammen, ist aber etwas anders:

Ich möchte einige Lottoscheine kaufen (die wenigsten), zum Beispiel, dass mindestens einer meiner Tickets 3 gute Nummern hat.

Herausforderung

Ihr Ziel ist es, eine generische Lösung (als Programm oder nur als Funktion) wie diese in einer beliebigen Sprache zu implementieren:

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

Für das obige Beispiel müsste man nur anrufen:

min_lottery_tickets(50, 5, 3)

und das Programm generiert den kleinsten Satz von Tickets, um dieses Ziel zu erreichen.

Beispiel:

 min_lottery_tickets(10, 5, 2)

würde 7 Tickets ausgeben, wie diese:

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

weil solche Tickets ausreichen, um jedes Zahlenpaar von 1 bis 10 abzudecken.

Ausgabe

Text, eine Zeile pro Ticket, Tabellen oder Leerzeichen zwischen Zahlen

Wer gewinnt

Das effizienteste Programm gewinnt (dh das Programm, das die wenigsten Tickets für die oben genannten Parameter generiert):

min_lottery_tickets(50, 5, 3)

Vielen Dank!

Ich weiß, dass es nicht optimal ist , aber hier ist der 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);
        }
    }
}

Einige Beispielergebnisse:

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

andere:

> 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 ]

andere:

> 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 ]