10

Uma das formas de apostar na lotofácil é escolher 15 números do número 1 à 25. Gostaria de um algoritmo em c# que gerasse apostas. Lembrando que em cada combinação os números não podem se repetir entre si e as apostas não devem se repetir.

Já fiz alguma coisa mas não ficou bom. A minha estratégia foi de criar um arraylist de 15 números, para cada posição gerar um número ramdômico de 1 a 25 e verificar se esse número estava em alguma outra posição, no final eu ordenava os números e verificava se existia alguma outra aposta com os mesmos números, caso não existisse eu armazenava.Gostaria de conhecer novas formas de pensar.

4
  • 3
    Qual é a dúvida? Você quer escrever um programa que escolha conjuntos de 15 números aleatórios sem repetir? Já tentou algo? O que deu errado na sua implementação? 27/03/2014 às 14:45
  • 2
    Nesta comunidade, nós ajudamos a resolver problemas com código e não trabalhamos de graça. Por favor, mostre-nos o que você tentou e está com dificuldade. Se não sabe por onde começar, mostre o que pesquisou e o que tem até agora. Não se ofenda, não é nada pessoal. É apenas como esta comunidade é. Se tiver dúvidas, por favor, leia a faq. 27/03/2014 às 14:50
  • 2
    Se for pensar nesse sentido, "trabalhar de graça", a comunidade passa a não fazer sentido. Todo a dúvida que é solucionada (via código ou não) no fim das contas alguém trabalhou para solucioná-la (usou sua experiência ou conhecimento). 27/03/2014 às 14:55
  • 2
    Douglas, ao invés de criar um comentário, quando você quiser adicionar detalhes ou informações à sua pergunta edite-a. Assim ninguém vai perder o contexto extra por não ter lido o comentário. Dessa vez eu fiz pra você, mas tente sempre lembrar disso.
    – Gabe
    8/04/2014 às 14:11

3 Respostas 3

10

Eu faria da seguinte maneira.

Solução 1

  • Criaria uma lista de 25 posições numerados de 1 a 25
  • Faria varios embaralhamentos na lista
  • Pegaria os 15 primeiros elementos
  • Verificaria se já n tenho estes 15 números
  • Repetiria o processo para o numero de vezes necessário

Solução 2

  • Geraria todas as 3.268.760
  • Escolheria randomicamente quantas eu preciso

A escolha entre cada uma das soluções depende da escolha espaço/tempo.

Caso precise do algoritmo aqui tem a base teórica e varias implementações inclusive C#.

4
  • Eu pensei nas 3.268.760, sei que tem uma solução matemática (binomial não sei do que), o problema é que não achei o algoritmo para gerar as combinações. 27/03/2014 às 14:58
  • Foi na mosca! Muito obrigado! 27/03/2014 às 15:07
  • Recomendo que na Solução numero 2, use uma estrutura de dados adequada, por exemplo uma arvore, para o acesso aos dados ser rapido.
    – urb
    27/03/2014 às 17:42
  • @Urbester: gerar todas e randomizar demora um pouco, como demonstro na minha resposta. Aqui leva uns 5 segundos, para randomizar 3.268.760 de valores inteiros. 27/03/2014 às 22:15
9

Dado um algoritmo capaz de pegar a n-ésima combinação, basta você usar números inteiros aleatórios para obter os jogos.

Classe para obter a n-ésima combinação

Fiz uma classe capaz de obter a n-ésima combinação. Basta instanciar ela, passando o número de elementos a serem retornados (no caso 15), e um array com todos os elementos possíveis (arra de números de 1 até 25). Depois de criada chame o método PegarCombinacao passando o índice da combinação, sendo 0 a primeira possível e 3268759 a última possível.

Garantias de velocidade

A vantagem na velocidade está exatamente no fato de representarmos qualquer um dos jogos possíveis, simplesmente como sendo um int... sendo que selecionar números inteiros aleatoriamente é muito rápido.

Além disso, a classe de pegar a n-ésima combinação, é feita sem iterar sobre todas as combinações. Eu uso um algoritmo baseado em somatórios para achar a exata combinação, sem ter de iterar. Para 15 elementos a serem retornados, o máximo de iterações deste algoritmo é 15 * 15 no pior caso, e 1 * 1 no melhor caso.

Código da classe

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);
    }
}

Exemplo de uso

Leia os comentários, eles são muito importantes.

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();

As recomendações que fiz nos comentários são baseadas em testes executados na minha máquina, pode ser que na sua os resultados sejam um pouco diferentes.

5

Já que eu estou tranquilo, eu desenvolvi uma rotina que gera esses "jogos" aleatoriamente.

Deem uma olhada:

  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;
    }
1
  • 1
    Muito bom Matheus! Sua ideia é muito boa! 27/03/2014 às 15:59

Esta não é a resposta que você está procurando? Pesquise outras perguntas com a tag .