Construir um algoritmo que selecione aleatoriamente números mas de forma que não haja repetição dos numeros selecionados.
Existem dois processos básicos de seleção de números: 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 é imprevisível dada a sequencia de números já escolhidos antes. A sequencia aleatória é o processo implementado comumente em API de apoio em linguagens de programação e em Java é representado pela classe java.util.Random . Esta classe é o que se chama um Gerador de Números Aleatórios mas ele é de fato um gerador de sequências aleatórias.
A geração de sequencias aleatórias com Random não é tão aleatória assim. A geração baseia-se num algoritmo que parte de um numero e gera outro, e a partir desse outro, assim sucessivamente. Esse primeiro numero é chamado de semente (seed, em inglês). Diz-se que este tipo de sequência é pseudo-aleatória porque tentar prever essa geração por "força bruta" é demasiado complexo para ser feito na prática mas não é impossível em teoria. 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 difíceis de prever.
Uma utilidade muito importante das sequências pseudo-aleatórias é a capacidade de repetir a mesma sequência caso seja necessário. Random suporta o conceito de semente. Portanto, criando o objeto com a mesma semente será produzida a mesma sequência. Isto é de extrema importância em algoritmos como os Método de Monte Carlo onde queremos produzir números aleatoriamente, mas queremos produzir sempre os mesmos a cada execução do teste para obter repetibilidade.
Objetos da classe Random geram sequências de quase todos os tipos primitivos em java nomeadamente: boolean , int , long , float e double . O contra-dominio ( ou seja, o conjunto de números possíveis de serem gerados) das sequências 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 possíveis 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 possíveis 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 possível 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 já que as bolas não voltam para a tombola.
A diferença de um processo de sequência aleatória para um de sorteio é que em um sorteio nós escolhemos o conjunto de números possiveis ao invés de utilizar todo o intervalo de um certo tipo de valor.
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 números 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 previsível. 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 números 1, 10 , 100 e 1000.
public int sorteia (){
List lista = new ArrayList () ;
lista.add ( new Integer ( 1 )) ;
lista.add ( new Integer ( 10 )) ;
lista.add ( new Integer ( 100 )) ;
lista.add ( new Integer ( 1000 )) ;
Collections.suffle ( lista ) ;
// pega qualquer indice. pegamos o primeiro por conveniência.
return lista.get (0);
}Repare que a grande diferença aqui é que escolhemos os números que podem ser sorteados, um a um. Utilizando este processo podemos simular uma loteria com quaisquer números. Se os números forem muitos utilizaremos um laço para iniciar a lista de opções, mas o processo de sorteio, em si, é o mesmo.
public int sorteia (){
List lista = new ArrayList () ;
for ( int i = 1 ; i <= 60 ; i++ ){ // de 1 a 60
lista.add ( new Integer ( i )) ;
}
Collections.suffle ( lista ) ;
// pega qualquer indice. pegamos o primeiro para conveniencia.
return lista.get ( 0 );
}É comum sortear números dentro de um determinado intervalo. No exemplo acima, sorteamos entre 1 e 60. Se quisermos simular um dado, sortearemos entre 1 e 6. Para poucos elementos, o processo de utilizar uma coleção funciona, mas para intervalos grandes não é um processo prático.
Se, por outro lado, o sorteio for feito num contra-dominio continuo ( por exemplo os números 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 sequência aleatória limitada. As únicas sequências aleatórias limitadas que temos disponíveis são as de tipos double ou float que produzem números 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:
public int sorteia (){
Random r = new Random () ;
final int H = 60 ; // sorteia entre 1 e 60
final int L = 1 ;
return (int)( r.nextDouble () * ( H-L )) + L;
}Onde H representa o numero mais alto, e L o numero mais baixo do intervalo.
A classe Random tem um método especial que ajuda nesta geração em intervalos. O codigo ficaria assim:
public int sorteia (){
Random r = new Random () ;
final int H = 60 ; / sorteia entre 1 e 60
final int L = 1 ;
return r.nextInt (H+1) + L
}O método nextInt de Random gera um inteiro no intervalo [0, H+1[ , ou seja, entre , ou seja, entre 0 inclusive e H+1 exclusive. Somando L a geração é entre L e H inclusive.
Vimos como faríamos 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.
List<Integer> lista = new ArrayList<>() ;
public void iniciaConjunto {
lista.add ( new Integer ( 1 )) ;
lista.add ( new Integer ( 10 )) ;
lista.add ( new Integer ( 100 )) ;
lista.add ( new Integer ( 1000 )) ;
}
public int sorteia (List<Integer> lista){
Collections.shuffle ( lista ) ;
// pega qualquer indice. pegamos o primeiro para conveniência.
return ((Integer)lista.remove(0)).intValue();
}Como vemos a 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.
Set<Integer> sorteados = new TreeSet<> () ;
public int sorteia (){
Random r = new Random () ;
final int H = 60 ; / sorteia entre 1 e 60
final int L = 1 ;
int result;
do (){
result = r.nextInt ( H+ 1 ) + L
while ( !sorteados.add( Integer.valueOf(result))) ;
return result;
}O numero é gerado e adicionado a coleção de números 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 útil no caso geral. Normalmente estamos interessados em sortear números inteiros de um conjunto e nesse caso é melhor utilizar o mecanismo baseado em coleções que vimos antes.
Sortear números é um processo comum, mas muitas vezes precisamos sortear outro tipo de objeto. Podemos querer sortear String ou qualquer outro objeto. Por exemplo, podemos querer sortear produtos para mostrar na página principal do site.
Nestes casos podemos 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 números. Eis um exemplo de sorteio de String :
public String sorteia (){
List<Integer> lista = new ArrayList<Integer> () ;
lista.add ( "Alice" ) ;
lista.add ( "Bruno" ) ;
lista.add ( "Carlos" ) ;
lista.add ( "Daniel" ) ;
Collections.shuffle ( lista ) ;
// pega qualquer indice. pegamos o primeiro para conveniencia.
return lista.get (0);
}Quando falamos em sorteio estamos normalmente interessados em sorter um subconjunto de elementos. Por exemplo, sortear 6 numeros entre 1 e 60. O código a seguir mostra como fazer este sorteio
public List<Integer> sorteia ( int quantidadeDeElementosASortear, int limiteInferior, int limiteSuperior){
// cria a lista de elementos
List<Integer> elementos = new ArrayList<Integer>(limiteSuperior - limiteInferior + 1);
for (int i = limiteInferior; i <= limiteSuperior; i++){
elementos.add(Integer.valueOf(i));
}
// altera a ordem aleatoriamente
Collections.shuffle (elementos) ;
// sorteia o numero de elementos necessários
List<Integer> resultado = elementos.subList(0,quantidadeDeElementosASortear);
return new ArrayList<Integer>(resultado);
}Primeiro montamos a lista completa de elementos possiveis. Reordenamos a lista de forma aleatória com Collections.shuffle() . Por fim pegamos os primeiros elementos dessa lista reordenada utilizando subList(). A lista que resulta deste método está vinculada à lista original, para a desvincularmos copiamos para um ArrayList.