Random sem repetir numero

int numero = new Random().nextInt(20);
Exemplo. Se já saiu o número 0
Na outra
Como eu faço para sair outro número que não seja o que saiu…
Tem como fazer isso?

Você pode colocar todos os resultados em uma estrutura de dados, depois faça a interação nela antes de apresentar o resultado

O mais fácil é colocar todos os valores em um List aí fazer um shuffle.

4 curtidas

Você vai sortear dentro de uma faixa (ex: de 0 a 20), ou pode ser qualquer número entre o Integer.MIN_VALUE (-2147483648) e o Integer.MAX_VALUE?

Se for dentro de uma faixa, uma solução similar ao proposto pelo Eduardo é inserir os números num List e emabaralhá-los com Collections.shuffle. Quando precisar de um número aleatório, você remove um número dessa lista.

Abraço.

2 curtidas

@staroski
@TerraSkilll
@Eduardo_Maranata10
Vocês poderiam demonstrar … eu não sei como fazer isso.

Você pode fazer como abaixo:

    Set<Integer> set = new LinkedHashSet<>();
	
	final int QTD = 20;
	Random numero = new Random();
	
	while (set.size() < 20) {
		set.add(numero.nextInt(QTD));
	}
	
	System.out.println(set);

Você adiciona em um LinkedHashSet. Não aceita duplicidade e mantém a ordem de inserção.
Com isso você faz um loop até preencher a quantidade de números que você desesja, ou seja, até o conjunto ter tamanho 20 por exemplo.

Essa forma pode demorar pois estará tentando gerar aleatoriamente os números de 0 à 19 e quando um número for gerado repetido, ele tentará gerar novamente até que não se repita.

Eu criaria uma classe assim:

import java.util.Collections;
import java.util.LinkedList;
import java.util.List;

public final class NumerosAleatorios {

    private final List<Integer> numeros;

    public NumerosAleatorios(int quantidade) {
        if (quantidade < 1) {
            throw new IllegalArgumentException("Não faz sentido sortear " + quantidade + " números");
        }
        numeros = new LinkedList<>();
        for (int numero = 0; numero < quantidade; numero++) {
            numeros.add(numero);
        }
        Collections.shuffle(numeros);
    }

    public int proximo() {
        if (numeros.isEmpty()) {
            throw new IllegalStateException("Todos os números já foram sorteados");
        }
        return numeros.remove(0);
    }
}

E utilizaria mais ou menos assim:

int quantidade = 20;
NumerosAleatorios sorteio = new NumerosAleatorios(quantidade);
for (int i = 0; i < quantidade; i++) {
    int numero = sorteio.proximo();
    System.out.println(numero);
}
2 curtidas

Faça um teste e diz se acontece isso:

    long inicio, fim;
	
	inicio = System.currentTimeMillis();
	
	int quantidade = 9999;
	NumerosAleatorios sorteio = new NumerosAleatorios(quantidade);
	for (int i = 0; i < quantidade; i++) {
	    int numero = sorteio.proximo();
	    System.out.println(numero);
	}
	
	fim = System.currentTimeMillis();
	
	long teste1 = fim - inicio;
	
	//===============================================
	
	inicio = System.currentTimeMillis();
	
	Set<Integer> set = new LinkedHashSet<>();

	final int QTD = 9999;
	Random rnd = new Random();

	while (set.size() < QTD) {
		set.add(rnd.nextInt(QTD));
	}

	fim = System.currentTimeMillis();
	
	long teste2 = fim - inicio;
	
	set.forEach(System.out::println);
	
	System.out.println("Teste 1: " + teste1);
	System.out.println("Teste 2: " + teste2);

Isso gera um conjunto 9999 números entre zero e 9998. Mas ele não vai fazer 9999 gerações de números, vai fazer mais, muito mais, por causa das repetições. É ineficiente.

Não é uma questão de dar certo ou não (usar Set ou Collections.shuffle obtém o mesmo resultado: uma coleção com números aleatórios numa faixa), só há uma diferença de desempenho, ainda mais se a quantidade de números a ser gerada aumenta. Por isso acho a solução de usar Collections.shuffle melhor.

Abraço.

Porque não faz o teste pra ter certeza do que está falando sobre o desempenho?

Claro, estou com alguns minutos livres :grin:

Note que dá timeout quanto se tenta usar set com 20000000 elementos, por que demora. Mas já com 20000 elementos, o shuffle é mais rápido.

Repetindo: ambas soluções funcionam, mas uma se mostra mais rápida conforme se aumenta a quantidade de números a ser gerada. É uma diferença que não deve impactar muito o que o RafaelV.B quer (20 números), mas existe sim.

Abraço.

Que coleguinha teimoso, vamos lá…

Primeiramente, veja os comentários que pus no código que você postou:

public static void main(String[] args) {
    long inicio, fim;
    inicio = System.currentTimeMillis();

    int quantidade = 9999;
    NumerosAleatorios sorteio = new NumerosAleatorios(quantidade);
    for (int i = 0; i < quantidade; i++) {
        int numero = sorteio.proximo();
        System.out.println(numero); // aqui estamos gerando E imprimindo o numero a cada iteração
    }

    // aqui está calculando o tempo do teste 1
    // após ter iterado a lista e impresso os resultados
    fim = System.currentTimeMillis();
    long teste1 = fim - inicio;

    // ===============================================

    inicio = System.currentTimeMillis();

    Set<Integer> set = new LinkedHashSet<>();

    final int QTD = 9999;
    Random rnd = new Random();

    while (set.size() < QTD) {
        set.add(rnd.nextInt(QTD)); // aqui estamos gerando o numero e adicionando numa coleção, sem imprimir nada
    }

    // aqui está calculando o tempo do teste 2, antes de imprimir algo
    fim = System.currentTimeMillis();
    long teste2 = fim - inicio;

    set.forEach(System.out::println); // e só agora está iterando a coleção e imprimindo os resultados do teste 2

    System.out.println("Teste 1: " + teste1);
    System.out.println("Teste 2: " + teste2);
}

A saída é esta:

Teste 1: 427
Teste 2: 103

Agora, vamos ser honestos e fazer dois cálculos de forma similar e ainda validando a questão de geração repetida de números:

public static void main(String[] args) {
    long inicio, fim;

    inicio = System.currentTimeMillis();
    int quantidade = 9999;
    NumerosAleatorios sorteio = new NumerosAleatorios(quantidade);
    Set<Integer> setTeste1 = new LinkedHashSet<>();
    int repetidos1 = 0;
    int iteracoes1 = 0;
    for (int i = 0; i < quantidade; i++) {
        if (!setTeste1.add(sorteio.proximo())) {
            repetidos1++;
        }
        iteracoes1++;
    }
    fim = System.currentTimeMillis();
    long teste1 = fim - inicio; // calcular o tempo antes de imprimir, igual ao teste 2

    setTeste1.forEach(System.out::println);

    // ===============================================

    inicio = System.currentTimeMillis();
    Set<Integer> setTeste2 = new LinkedHashSet<>();
    final int QTD = 9999;
    Random rnd = new Random();
    int repetidos2 = 0;
    int iteracoes2 = 0;
    while (setTeste2.size() < QTD) {
        if (!setTeste2.add(rnd.nextInt(QTD))) {
            repetidos2++;
        }
        iteracoes2++;
    }
    fim = System.currentTimeMillis();
    long teste2 = fim - inicio;

    setTeste2.forEach(System.out::println);

    System.out.println("Teste 1  tempo:       " + teste1);
    System.out.println("   iteracoes:         " + iteracoes1);
    System.out.println("   numeros repetidos: " + repetidos1);
    System.out.println("Teste 2  tempo:       " + teste2);
    System.out.println("   iteracoes:         " + iteracoes2);
    System.out.println("   numeros repetidos: " + repetidos2);
}

E a saída é:

Teste 1  tempo:       18
   iteracoes:         9999
   numeros repetidos: 0
Teste 2  tempo:       50
   iteracoes:         95249
   numeros repetidos: 85250

Vocês são donos da razão.
Usei o seu primeiro código comparando com o meu. Agora você alterou meu código e o seu.
Ignora minha resposta. Ajuda o dono do post. Eu não tenho dúvidas para serem resolvidas.

Não, ninguém é.
Apenas comentamos que seu laço era ineficiente pois fica repetidamente tentando gerar um número que ainda não existe.

Sim, mas sua comparação foi falha, pois no seu código você comparou os tempos antes de realizar as operações de I/O e no meu comparou após as operações de I/O.

Só incluí um contador de números repetidos no seu código, para ilustrar o que o outro colega já havia explicado e você não havia entendido. E também por você ter respondido minha resposta pedindo para eu testar e ver se isso realmente acontecia, pois bem, agora ficou claro que as repetições de número aconteciam.

Nós 3 ajudamos, você, o outro colega e eu.

:expressionless:

1 curtida

Eu entendi muito bem o que disseram e sabia o que meu código estava fazendo, porém pedi pra fazer um teste de desempenho. Mesmo que teoricamente vocês estivessem certos.
Falhei no teste? Concordo mas não alterei seu código para os testes serem justos. Esse foi o erro. Mantive a sua solução. Que por sinal não estava em sua melhor forma.

Sim, mas isso acontece, qual o problema?
E eu só modifiquei seu laço pois quando comentei que havia geração repetida de código você pediu para eu testar seu código pra ver se realmente acontecia. Pois bem, eu alterei pra poder ver.

De fato não está, se naquela classe remover o shuffle e usar o Random para remover de posições aleatórias da lista, será mais rápido. :slight_smile:

Eu tinha dito pra testar se estava mais lento e não se tinha geração repetida. Também não expliquei o que quis dizer.
Mas agora está resolvido.

1 curtida

Essa é definitivamente a solução mais eficiente, pois é O(N). Não tem nem como calcular a complexidade computacional de criar um Set e ficar checando se o número já foi gerado antes. Existe a possibilidade do algoritmo nem acabar de rodar, e portanto não é nem um algoritmo.

1 curtida

Esse é o modo que usei num programinha que uso bastante. Um Sorteador de duplas de baralho (minha vó acha que tem trapaça na jogada :smile:). Eu ia sugerir sets, mas shuffle é mais simples.

Caso você precise de um vetor, sem usar coleções

public static void main(String[] args) {
	// Digite a quantidade de numeros

	NumeroSoteado numeroSoteado = new NumeroSoteado(20);
	
	for (int i = 0; i < 21; i++) {
		int numero = new Random().nextInt(20);
		numeroSoteado.adiciona(numero);
	}   
	
	numeroSoteado.mostrar();
	
}

}

Classe NumeroSoteado

class NumeroSoteado {
int[] vetor;
int cont = 0;

public NumeroSoteado(int quantidadeDeNumeros) {
	if(quantidadeDeNumeros > 0) {
		vetor = new int[quantidadeDeNumeros];		
	}else {
		System.out.println("Numero menor ou igual a zero");
	}
	
}

private boolean isPresente(int numero) {
	for (int i = 0; i <= cont; i++) {
		if (numero == vetor[i]) {
			return true;
		}
	}
	return false;
}

public void adiciona(int numero) {

	if (cont > vetor.length) {
		System.out.println("Vetor cheio");
	} else {
		if (!isPresente(numero)) {
			vetor[cont] = numero;
			cont++;
		}else {
			System.out.println("Numero soteado");
		}
	}
}

public void mostrar() {
	System.out.println("Sequencia");
	for (int i = 0; i < cont; i++) {
		System.out.print(vetor[i]+ ", ");
	}
}