Générez le moins de billets de loterie à jouer afin d'avoir au moins N bons numéros

C'est un sujet mathématique assez complexe mais très intéressant (dit "problème de couverture" ),

Et j'aimerais votre aide pour sa mise en œuvre.

Imaginez un jeu de loterie, où chaque billet doit choisir 5 numéros aléatoires dans un ensemble de 50 numéros (de 1 à 50).

Il est assez facile de connaître la probabilité d'un ticket gagnant, ou la probabilité d'avoir 1, 2, 3 ou 4 bons numéros.

Il est également assez facile de "générer" tous les tickets qui ont 1, 2, 3, 4 bons numéros.

Ma question (et défi de code) est liée à cela, mais légèrement différente:

Je veux acheter des billets de loterie (le moins possible), comme au moins un de mes billets a 3 bons numéros.

Défi

Votre objectif est d'implémenter une solution générique (en tant que programme ou simplement fonction), comme celle-ci, dans n'importe quelle langue:

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

Pour l'exemple ci-dessus, il suffit d'appeler:

min_lottery_tickets(50, 5, 3)

et le programme générera le plus petit ensemble de billets à jouer pour atteindre cet objectif.

Exemple:

 min_lottery_tickets(10, 5, 2)

produirait 7 tickets, comme ceux-ci:

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

car de tels billets sont suffisants pour couvrir n'importe quelle paire de numéros de 1 à 10.

Production

Texte, une ligne par ticket, tabulations ou espaces entre les chiffres

qui gagne

Le programme le plus efficace gagne (c'est-à-dire le programme générant le moins de tickets pour les paramètres ci-dessus):

min_lottery_tickets(50, 5, 3)

Merci!

Je sais que ce n'est pas optimal , mais voici le code dans 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);
        }
    }
}

Quelques exemples de résultats:

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

autre:

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

autre:

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