Sorteio aleatório sem Repetição

Este texto foi atualizado e doado ao projeto Code Design World.

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.

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 .