Sorteio aleatório sem Repetição

Este texto foi atualizado e doado ao projeto Java Building.
Leia a
versão mais atualizada.

Problema

Construir um algoritmo que selecione aleatoriamente numeros mas de forma que não haja repetição dos numeros selecionados.

Existem dois processos básicos de seleção de numeros: sorteio e sequencia aleatória. Estes processo são semelhantes mas são dois processos diferentes. A seguir exploraremos cada um deles e exemplicaremos implementações em Java.

O conceito da sequencia aleatória limita-se a obter um numero após o outro, tal que o numero seguinte é imprevisivel dada a sequencia de numeros já escolhidos antes. A sequencia aleatória é o processo implementado comummente em API de apoio em linguagens de programação e em Java é representado pela classe java.util.Random. Esta classe é o que se chama de um Gerador de Numeros Aleatórios mas é de fato um gerador de sequências aleatórias.

A geração de sequencias aleatórias com Random não é tão aleatoria assim.A geração baseia-se num algoritmo que parte de um numero e gera outro. Esse primeiro numero é chamado de semente (seed, em inglês). Diz-se que este tipo de sequencia é pseudo-aleatória porque tentar prever essa geração “no braço” é demasiado complexo para ser feito na prática mas não é impossivel. Portanto, a geração não é verdadeiramente aleatória. Para quase todos os fins práticos este tipo de geração é suficiente, mas para aplicações em segurança não é. Por isso existe a classe SecureRandom que implementa algoritmos mais dificeis de prever.

Uma utilidade muito importante das sequências pseudo-aleatórias é a capacidade de repetir a mesma sequencia caso seja necessário. Random suporta o conceito de semente. Portanto, criando o objeto com a mesma semente será produzida a mesma sequencia. Isto é de extrema importancia em algoritmos como o Teste de Montecarlo onde queremos produzir numeros aleatóriamente, mas queremos produzir sempre os mesmos a cada execução do teste para obter repetibilidade.

Objetos da classe Random geram sequencias de quase todos os tipos primitivos em java nomeadamente: boolean, int, long, float e double. O contra-dominio ( ou seja, o conjunto de numeros possiveis de serem gerados) das sequencias aleatórias é limitado entre 0.0 (zero) e 1.0 (um) para double e float. Para os outros tipos o contra-dominio são todos os valores possiveis para esse tipo de variável em Java. A geração é feita tal que todos os valores possiveis têm igual probabilidade.

O conceito de sorteio é o de um processo em que um dos possiveis valores é escolhido de entre todos os outros. O sorteio pode ser com repetição ou sem repetição.

Imagine que tem um sacola de pano preto de forma que o seu interior não pode ser visto de fora. São colocadas bolas dentro dessa sacola, uma para cada numero possivel de ser sorteado. O sorteio é o processo em que uma pessoa coloca a mão na sacola e retira um bola. Após o numero na bola ser visto a bola pode, ou não, voltar para dentro do saco. Se voltar estamos perante um sorteio com repetição. Se não voltar estamos perante um sorteio sem repetição. A loteria, por exemplo, é um processo de sorteio sem repetição.

A diferença de um processo de sequencia aleatória para um de sorteio é que em um sorteio nós escolhemos o conjunto de numeros possiveis ao invés de utilizar todo o intervalo de um certo tipo de variável.

Simular um sorteio com o auxilio de um computador não utiliza uma sacola de pano preto, mas pode utilizar outra implementação de um conjunto: uma coleção.

Para começar podemos pensar numa coleção dos numeros que queremos sortear. O sorteio é simulado pela escolha de um desses elementos da coleção. Esse é o numero sorteado.Em um sorteio com repetição o elemento é devolvido à coleção. em um processo sem repetição o elemento é descartado e não é devolvido à coleção.
Contudo, se simplesmente adicionarmos os elementos na coleção e depois os retirarmos vamos ter um sorteio completamente previsivel. Precisamos de um elemento que misture os elementos. Em Java conseguimos isso usando o método suffle() em java.util.Collections. Este método aceita um List que é um tipo especial de coleção onde os elementos podem ser referidos por um indice. Eis um exemplo simples. Queremos sortear entre os numeros 1, 10 , 100 e 1000.

01
02
03 public int sorteia (){
04 List lista = new ArrayList () ;
05 lista.add ( new Integer ( 1 )) ;
06 lista.add ( new Integer ( 10 )) ;
07 lista.add ( new Integer ( 100 )) ;
08 lista.add ( new Integer ( 1000 )) ;
09
10 Collections.suffle ( lista ) ;
11
12 // pega qualquer indice. pegamos o primeiro para conveniencia.
13
14 return (( Integer ) lista.get ( 0 )) .intValue () ;
15 }

Código 1:

Repare que a grande diferença aqui é que escolhemos os numeros que podem ser sorteados, um a um. Utilizando este processo podemos simular uma loteria com quaisquer numeros. Se os numeros forem muitos utilizaremos um laço para iniciar a lista de opções, mas o processo de sorteio, em si, é o mesmo.

01
02
03 public int sorteia (){
04 List lista = new ArrayList () ;
05
06 for ( int i = 1 ; i <= 60 ; i++ ){ // de 1 a 60
07 lista.add ( new Integer ( i )) ;
08 }
09
10 Collections.suffle ( lista ) ;
11
12 // pega qualquer indice. pegamos o primeiro para conveniencia.
13
14 return (( Integer ) lista.get ( 0 )) .intValue () ;
15 }

Código 2:

É comum sortear numeros dentro de um determinado intervalo. No exemplo acima, sorteamos entre 1 e 60. Se quisermos simular um dado, sortamos entre 1 e 6. Para poucos elementos, o processo de utilizar um coleção funciona, mas para intervalos grandes não é um processo prático. Por outro lado se o sorteio for feito num contra-dominio continuo ( por exemplo os numeros não-inteiros entre 1 e 2) o uso de uma coleção também não é eficaz. Nestas circunstancias é utilizada um processo que simula o sorteio por meio da geração de uma sequencia aleatória limitada. As únicas sequencias aleatórias limitadas que temos disponiveis são as de tipos double ou float que produzem numeros entre 0.0 e 1.0. Como fazer para que esse intervalo possa ser qualquer que queiramos? Na realidade é bem simples. Basta utlizarmos uma formula

1
2 public int sorteia (){
3
4 Random r = new Random () ;
5 final int H = 60 ; / sorteia entre 1 e 60
6 final int L = 1 ;
7 return ( int )( r.nextDouble () * ( H-L )) + L
8 }

Código 3:

Onde H representa o numero mais alto, e L o numero mais baixo do intervalo. Desta forma reduzimos o intervalo à escala que queremos.

A classe Random tem um método especial que ajuda nesta geração em intervalo. O codigo ficaria assim

1
2 public int sorteia (){
3
4 Random r = new Random () ;
5 final int H = 60 ; / sorteia entre 1 e 60
6 final int L = 1 ;
7 return r.nextInt ( H+ 1 ) + L
8 }

Código 4:

O método nextInt de Random gera um inteiro no intervalo [0, H+1[ , ou seja, entre 0 e H+1 exclusive. Somando L a geração é entre L e H inclusive.

Vimos como fariamos sorteios com repetição em conjunto e intervalos. Vejamos agora como fariamos sorteios sem repetição em cada modalidade.

Para fazer sorteios sem repetição em conjunto, basta, como vimos antes, remover o numero da coleção. Voltando ao exemplo inicial

01
02
03 List lista = new ArrayList () ;
04
05 public iniciaLista (){
06 lista.add ( new Integer ( 1 )) ;
07 lista.add ( new Integer ( 10 )) ;
08 lista.add ( new Integer ( 100 )) ;
09 lista.add ( new Integer ( 1000 )) ;
10 }
11
12 public int sorteia (){
13
14
15 Collections.suffle ( lista ) ;
16
17 // pega qualquer indice. pegamos o primeiro para conveniencia.
18
19 return (( Integer ) lista.remove ( 0 )) .intValue () ;
20 }

Código 5:

Como vemos é diferença é minima. Basta utilizar o método remove em vez do get. Contudo a lista de valores possiveis é guardada e iniciada fora do metodo. Para intervalos o processo é mais complexo já que temos que memorizar o elemento sorteado.

01
02
03 Set sorteados = new TreeMap () ;
04
05 public int sorteia (){
06
07 Random r = new Random () ;
08 final int H = 60 ; / sorteia entre 1 e 60
09 final int L = 1 ;
10 int result;
11 do (){
12 result = r.nextInt ( H+ 1 ) + L
13 while ( !sorteados.add ( new Integer ( result ))) ;
14
15 return result;
16 }

Código 6:

O numero é gerado e adicionado a coleção de numeros já sorteados. Se o numero já existia no conjunto o método add retorna false e o laço recomeça gerando outro numero.O laço só termina quando um numero novo for gerado. Este processo é extreamente ineficiente pois à medida que o numero de elementos no conjunto dos já sorteados cresce é cada vez mais dicifil gerar um numero diferente.

Na prática o sorteio sem repetição dentro de um intervalo não é muito util e quase sempre é possivel utilizar um mecanismo utilizando coleções.

Sortear numeros é um processo comum, mas muitas vezes precisamos sortear outro tipo de objeto. Podemos querer sortear String ou qualquer outro objeto. Nestes casos podemo utilizar o sorteio utilizando listas para sortear os objetos. Na realidade, com este método, sempre estivemos sorteando objetos desde um inicio. Acontecia apenas que esses objetos representavam numeros.Eis um exemplo de sorteio se Strings

01
02
03 public int sorteia (){
04 List lista = new ArrayList () ;
05 lista.add ( “Alice” ) ;
06 lista.add ( “Bruno” ) ;
07 lista.add ( “Carlos” ) ;
08 lista.add ( “Daniel” ) ;
09
10 Collections.suffle ( lista ) ;
11
12 // pega qualquer indice. pegamos o primeiro para conveniencia.
13
14 return (( Integer ) lista.get ( 0 )) .intValue () ;
15 }

Código 7:

As Strings podem ser quaisquer. Utilizamos aqui nomes para ser mais claro.

Creative Commons License Sérgio Taborda
Este trabalho é licenciado sob a
Licença Creative Commons Atribuição-Uso Não-Comercial-Não a obras derivadas 3.0 Genérica .
  1. 2008/06/23 às 12:40 | #1

    Olá, parabéns pelo blog!

    Mas estou com uma dúvida… o código

    return ( int )( r.nextDouble () * ( H-L+ 1 )) + L

    não está errado? Acho que não deve ter esse +1, e no lugar de apenas descartar a parte fracionária, acho que seria mais correto arredondar. Aí ficaria +- assim:

    (Math.round(r.nextDouble() * (H - L)) + L

    Valeu :)

  2. sergiotaborda
    2008/06/24 às 10:08 | #2

    Sim, tem razão, não tem o +1. Vou corrigir. Em relação ao round(): não deve usar o round porque está introduzindo um desvio ( sempre para cima) em todos os numeros sorteados, isso faz com que a probabilidade de cada numero não seja equivalente viciando os resultados do sorteio.

  3. Claudimir
    2008/06/24 às 11:37 | #3

    Estou migrando do VB6 para o Java. Estou começando a estudar a nova plataforma (JAVA), por isso, me perdoe a ignorância na utilização da linguagem.
    Tentei compilar e executar o Código 1 e não consegui sucesso, quer no modo console, quer utilizando o NetBeans 6.0.1(pt-br). Dá um erro (Java:23 – no netbeans), já na primeira linha “public int sorteia(){” o que pode ser? o que estou fazendo de errado?
    Se puder me socorrer, agradeço.
    t+

  4. sergiotaborda
    2008/06/24 às 13:44 | #4

    Os codigo apresentados neste blog não são completos. São excertos para ilustrar o que se está dizendo no texto. O blog parte do pressumposto que o leitor saiba programar minimamente em java. ( sim, é uma limitação, mas não ha como agradar a todos). Para usar aquele método vc tem que criar uma classe , escrever o método nessa classe e depois colocar um método main para executar o codigo. Aquele código, tal como está, não é executável.

  5. Claudimir
    2008/06/25 às 8:27 | #5

    Obrigado pelos esclarecimentos. Ah! sim. Antes que me esqueça de novo, parabéns pelos artigos. Já li vários e são muito esclarecedores e escritos com uma linguagem bem simples de entender (exceto as linhas de código kkkk), até para mim, novatíssimo em Java, que busco me inteirar com a plataforma.

  6. dener
    2008/08/08 às 13:07 | #6

    como fazer esse sorteio

  7. sergiotaborda
    2008/08/11 às 9:36 | #7

    Qual sorteio ?

  8. Pedro
    2008/11/02 às 8:06 | #8

    Randomizar numeros Unicos de 1 á 10 utilizando o

    public void randomiza() {
    rnd = new Random();
    for (int l = 0; l < 9; l++) {
    numeros[l] = Math.abs(rnd.nextInt()) % 9 +1;
    for (int x = 0; x < l; x++) {
    if (numeros[x] == numeros[l]) {
    numeros[l] = Math.abs(rnd.nextInt()) % 9 +1;
    x = -1; // x = -1 para ver se possui mais um numero igual ao novo adicionado
    }
    }

    }
    }

  9. sergiotaborda
    2008/11/02 às 8:53 | #9

    Humm.. não testei esse codigo mas parece-me que não está certo.
    O segundo for deveria ser um while. Por outro lado esse for não encontra os repetidos em todo o array.
    Não vejo vantagem em usar esse algoritmo (que não me parece sequer funcionar) em deterimento de algo bem mais simples como fazer shuffle de um list de numeros de 1 a 10.

  10. Pedro
    2008/11/02 às 9:22 | #10

    funciona corretamente…
    acabei de faze-lo
    estava buscando um sem utilizar List… mas não achei e tive que fazer
    pode testar

  11. Pedro
    2008/11/02 às 10:05 | #11

    Peguei um exemplo seu e modifiquei para sortear 9 numeros diferentes (1 á 9) e armazená-los numa lista

    List lista;
    lista = new ArrayList(9);
    Random r = new Random () ;
    int result;
    for(int x=0;x<9;x++){
    do {
    result = Math.abs(r.nextInt()) % 9 + 1;
    }while (lista.contains(result)==true);
    lista.add(result);
    }

  12. sergiotaborda
    2008/11/03 às 8:15 | #12

    Sortear 9 numeros de um a nove não é um sorteio é um embaralhamento. Os numeros sempre serão 1,2,3,4,5,6,7,8,9 apenas a ordem muda. Assim , não é eficiente ter um loop que procura repetidos quanto já sabemos que não haverão repetidos. Dai o loop inicial que simplesmente preenche a lista no meu exemplo.

    Depois da lista preenchida, o método suffle faz o resto. E o faz de forma eficiente. O detalhe é que sempre queremos sortear de um conjunto de elementos conhecido. Se requiséssemos construir um conjunto de elementos aletatoriamente isso são outros 500, mas o mesmo codigo pode ser adaptado.
    Basta usar um set em vez de lista e preenche-lo com N elementos gerados aletóriamente. O set vai garantir que não ha repetidos (substitui o seu do-while) . Ai vc copia o set para o list e usa shuffle. (Em opção pode criar set em cima de um list para poupar uma copia)

  13. ALESSANDRO
    2009/05/23 às 11:54 | #13

    olá Sergio teria como eu conseguir fazer um embaralhamento dos numeros de 01 – 20 sem repeti-los aguardo respostas parabéns pelo blog!

    • sergiotaborda
      2009/05/23 às 18:33 | #14

      Você pode usar a tenica que está descrita no artigo.
      Você utiliza uma lista e coloca os numeros de 1 a 20 nela usando um for.
      Depois utiliza Collections.shuffle para embaralhar a lista.
      Pronto, ai tem uma lista embaralhada.

      Podem existir algoritmos mais rápidos, mas este eu acho que é o mais evidente e simples de implementar

  14. Theo
    2009/05/25 às 22:07 | #15

    primeiramente, meus parabéns.. o blog é show!!

    já me desculpando da minha ignorância.. é que sou iniciante em Java :)
    estou querendo fazer um programinha que o usuário entra com 10 nomes, o programa lê, armazena em um array do tipo string e depois sortea um dos nomes..
    mas não estou tendo sucesso..
    se alguém puder me ajudar eu ficaria muitíssimo grato.

    • sergiotaborda
      2009/05/26 às 8:29 | #16

      Tem mesmo que ser um array ? Se puder usar um objeto do tipo List, use-o e aplique a mesma tenica descrita no artigo. Utilize Collections.shuffle para embaralhar e pegue o primeiro com list.get(0).

      Se tiver mesmo que utilizar um array, então faça o sorteio do indice do array. Aqui pode usar Random.nextInt() como mostrado no codigo 4.

      • Theo
        2009/05/26 às 15:13 | #17

        é.. tem que ser um array mesmo..
        vou ver se tenho sucesso agora com as suas dicas..
        muito obrigado!

  15. 2009/08/21 às 10:25 | #18

    Com base na sugestao apresentada, vou tentar seguir as instruçoes fornecidas e depois darei lhe algum comentario sobre o trabalho, na perspectiva de no futuro possam tornar muito importante nos meus trabalhos da faculdade.

  16. Alan
    2009/10/21 às 10:14 | #19

    Bom dia!

    Não consegui sortear String…

    Como que eu faço??

    ArrayList nomes = new ArrayList();

    nomes.add (“Alice”);
    nomes.add (“Bruno”);
    nomes.add (“Carlos”);
    nomes.add (“Daniel”);

    Collections.shuffle(nomes) ;

    • sergiotaborda
      2009/10/23 às 8:33 | #20

      O codigo está certo. Porque vc não consegue sortear ? É só fazer

      String sorteado = (String)nomes.get(0);

      Se quiser sortear mais do que um, é um pouco diferente. Veja no texto.

  17. 2009/11/09 às 10:40 | #21

    Ola, encontrei um codigo que serve direitinho para uma brincadeira de bingo onde ele chama uma página com um numero de cada vez mas tem um problema. ele repete diversar vezes o mesmo numero .por mais que eu tente colocar varios dispositivos de sorteio. Haveria um codigo que eu pudesse usar que não repetisse? to estudando essas opções todas escritas ai mas não sei onde poderia encaixar no codigo que utilizei. o sisteminha para brincar de bingo dá certinho em alguns messengers de voz Mas todo mundo reclama depois de alguns sorteios, do excesso de repetição, mesmo que embora isso não cause problema nenhum. Se pudesse dar uma olhada e alguma sugestão eu agradeceria muito. http://www.salainterativa.xpg.com.br/_sorteio.html
    abçs

    • sergiotaborda
      2009/11/09 às 12:09 | #22

      Quando se faz um sorteio no bingo real a bola sai de circulação até ao final do sorteio. É por isso que ela nunca mais vai se repetir. O que vc precisa é retirar o numero sorteado de entre os numeros possiveis. Assim a lista de numeros possiveis vai diminuindo e não ha repetição. Quando todos os numeros forem sorteados a lista é carregada de novo para um proximo sorteio.

      • 2009/11/09 às 18:12 | #23

        É eu só nao sei como fazer. mas achei uma solução pratica e rapida. deixei só a roleta e criei várias paginas com tabelas. a unica diferença é que nesse caso o sorteio é manual. mas pelo menos nao repete. Aida procuro codigos pra fazer um que sorteie automaticamente mas sem repetir. Valeu

  18. carlos
    2010/04/30 às 15:00 | #24

    Como gerar,em linguagem C ,um sorteio aleatorio para preecher 8 grupos com nomes de seleções sem repetições tipo um soteio para preecher os grupos da copa do mundo.

    • sergiotaborda
      2010/05/03 às 6:38 | #25

      è uma boa pergunta, mas porque não usa Java. Não me parece uma tarefa que precisa ser escrita em C.

  19. Libni
    2010/08/04 às 12:04 | #26

    Olá, achei muitíssimo interessante esse artigo, Mas da mesma forma que o Claudimir não estou conseguindo compilar os códigos. Iniciei em Java faz uns 6 meses, e uso a ferramenta BlueJ.
    Preciso fazer um Bingo, onde ocorre um sorteio de 75 numeros, e esses numeros não podem se repetir. O metodo indicado pelo professor é o Math.random.
    Gostaria de uma ajuda sua, se você puder, desde ja agradeçoo

    • sergiotaborda
      2010/08/05 às 9:23 | #27

      Como respondi então ao Claudemir respondo a si. Os código do blog não são feitos para serem executados como estão, são exemplos. Espera-se que a pessoa tenha minimo entendimento de java para saber como executar esses codigos. No seu caso, se vc tem um professor, então fale com ele. Se ele estipulou o uso de random, e vc não entende como usar isso, fale com ele. É para falar com eles, que os professores servem.

  20. Mauro Pires
    2012/03/02 às 6:40 | #28

    Bom dia,

    alguem sabe como fazer gerar os numero num bingo???

  21. RONY FERNANDES
    2012/03/31 às 1:42 | #29

    OLA QUERO SORTEAR INSCRIÇOES DE DUPLAS,EM PROVAS DE LAÇO.EXEMP.RONY X MARCOS FAZ 15 INSCRIÇOES CORRE 1º PULA 5 CORRE 2º PULA MAIS 5 E ASSIM POR DIANTE.ALGUEM PODE ME AJUDAR

  1. No trackbacks yet.
Tem de ter a sessão iniciada para publicar um comentário.
Seguir

Get every new post delivered to your Inbox.

%d bloggers like this: