Algorithm for betting creation on Lotofácil

Question

One of the ways to bet on Easy Bet is to choose 15 numbers from number 1 to 25. I would like an algorithm in c# that generates bets. Remembering that in each combination the numbers cannot repeat each other and the bets should not be repeated.

I’ve done something but it’s not good. My strategy was to create an arraylist of 15 numbers, for each position to generate a ramnamic number from 1 to 25 and check if that number was in some other position, at the end I would sort the numbers and check if there was any other bet with the same numbers, If it did not exist I would like to know new ways of thinking.

Answer 1

I’d do it this way.

Solution 1

• Create a list of 25 numbered positions from 1 to 25
• I’d do a lot of shuffling on the list
• I’d take the first 15 elements
• I would check if I already have these 15 numbers
• I would repeat the process for the number of times needed

Solution 2

• Generate all 3,268,760
• I would randomly choose how many I need

The choice between each solution depends on the space/time choice.

If you need the algorithm here has the theoretical basis and various implementations including C#.

Answer 2

Given an algorithm capable of catching the n-th combination, you just need to use random integer numbers to get the games.

Class to obtain the nth combination

I made a class able to get the nth combination. Just instantiate it, passing the number of elements to be returned (in case 15), and an array with all possible elements (array of numbers from 1 to 25). After created call the method PegarCombinacao passing the combination index, with 0 being the first possible and 3268759 the last possible.

Speed guarantees

The advantage in speed is exactly in the fact that we represent any of the possible games, simply as being a int... where selecting whole numbers at random is very fast.

Also, the class of catching the nth combination, is made without iterating over all combinations. I use a summation-based algorithm to find the exact combination without having to iterate. For 15 elements to be returned, the maximum iteration of this algorithm is 15 * 15 in the worst case, and 1 * 1 in the best case.

Class code

public class Combinador<T>
{
    private readonly int _cnt;
    private readonly T[] _items;
    private readonly List<int[]> _somatorios;

    public Combinador(int cnt, T[] items)
    {
        _cnt = cnt;
        _items = items;
        var line0 = new[] { 1 }.Concat(Enumerable.Repeat(0, cnt)).ToArray();
        var lines = new List<int[]>(cnt) { line0 };
        for (int itLine = 1; itLine <= cnt; itLine++)
        {
            var prevLine = lines[itLine - 1];
            var newLine = new int[line0.Length];
            for (int itCol = 0; itCol < newLine.Length; itCol++)
                newLine[itCol] = (itCol > 0 ? newLine[itCol - 1] : 0) + prevLine[itCol];
            lines.Add(newLine);
        }
        _somatorios = lines;
    }

    public T[] PegarCombinacao(int seed)
    {
        return GerarIndices(_somatorios, _items.Length - _cnt, _cnt, seed)
            .Select(i => _items[i])
            .ToArray();
    }

    private static IEnumerable<int> GerarIndices(List<int[]> lines, int fs, int ts, int num)
    {
        if (ts <= 0) yield break;
        var line = lines[ts];
        var min = 0;
        for (int itFs = 0; itFs <= fs; itFs++)
        {
            var max = min + line[itFs];
            if (num < max)
            {
                var num2 = num - min;
                yield return fs - itFs;
                foreach (var idx in GerarIndices(lines, itFs, ts - 1, num2))
                    yield return fs - itFs + idx + 1;
                yield break;
            }
            min = max;
        }

        throw new Exception("O parâmetro deve ser menor que " + min);
    }
}

Example of use

Read the comments, they are very important.

var comb = new Combinador<int>(15, Enumerable.Range(1, 25).ToArray());
var rnd = new Random();

// Criando os jogos de 1 a 1 e colocando num HashSet até ter N elementos
// esse método é rápido para poucas combinações, e vai ficando mais lento
// tendendo a infinito quando o número se aproxima da quantidade máxima.
// Mesmo assim, essa técnica é a recomendável para até 3 milhões de jogos.
// Use para 0% até 95% de todas as alternativas.
var numeros = new HashSet<int>();
int tentativas = 0;
while (numeros.Count < 200000)
{
    numeros.Add(rnd.Next(3268760));
    tentativas++;
}
var jogosAleatorios2 = numeros
    .Select(comb.PegarCombinacao)
    .ToArray();

// Criando todos os jogos e pegando N aleatórios
// esse método é lento, e não recomendo se não for
// gerar todos os jogos ou algo muito próximo de todos.
// Use somente para 95% até 100% de todas as alternativas.
var jogosAleatorios1 = Enumerable.Range(0, 3268760)
    .OrderBy(a => rnd.Next())
    .Select(comb.PegarCombinacao)
    .Take(100000)
    .ToArray();

The recommendations I made in the comments are based on tests performed on my machine, it may be that in your results are a little different.

Answer 3

Since I am quiet, I have developed a routine that generates these "games" randomly.

Take a look at:

  public List<int>[] GeraJogos(int numeroDeJogos)
    {
        List<int>[] jogos = new List<int>[numeroDeJogos];
        int i = 0;


        while (i < numeroDeJogos)
        {
            var lotoFacil = new List<int>();
            lotoFacil = LotoFacil();

            if (jogos.Contains(lotoFacil))
            {
                continue;
            }

            jogos[i] = lotoFacil;
            i++;
        }

        return jogos;
    }

    public List<int> LotoFacil()
    {
        var resultado = new List<int>();

        var randow = new Random();
        int randowNumber;
        int i = 0;

        while (i < 15)
        {
            randowNumber = randow.Next(1, 25);

            if (resultado.Contains(randowNumber))
            {
                continue;
            }

            resultado.Add(randowNumber);
            i++;
        }

        return resultado;
    }