Création de nombres aléatoires sans doublons

Question

Dans ce cas, le MAX n'est que de 5, donc je pourrais vérifier les doublons un par un, mais comment pourrais-je le faire de manière plus simple ? Par exemple, que se passe-t-il si le MAX a une valeur de 20 ? Merci.

int MAX = 5;

for (i = 1 , i <= MAX; i++)
{
        drawNum[1] = (int)(Math.random()*MAX)+1;

        while (drawNum[2] == drawNum[1])
        {
             drawNum[2] = (int)(Math.random()*MAX)+1;
        }
        while ((drawNum[3] == drawNum[1]) || (drawNum[3] == drawNum[2]) )
        {
             drawNum[3] = (int)(Math.random()*MAX)+1;
        }
        while ((drawNum[4] == drawNum[1]) || (drawNum[4] == drawNum[2]) || (drawNum[4] == drawNum[3]) )
        {
             drawNum[4] = (int)(Math.random()*MAX)+1;
        }
        while ((drawNum[5] == drawNum[1]) ||
               (drawNum[5] == drawNum[2]) ||
               (drawNum[5] == drawNum[3]) ||
               (drawNum[5] == drawNum[4]) )
        {
             drawNum[5] = (int)(Math.random()*MAX)+1;
        }

}

Answer 1

Le moyen le plus simple serait de créer une liste des nombres possibles (1..20 ou autre) et de les mélanger ensuite avec Collections.shuffle . Il suffit ensuite de prendre le nombre d'éléments que vous voulez. C'est une excellente solution si votre portée est égale au nombre d'éléments dont vous avez besoin à la fin (par exemple, pour mélanger un jeu de cartes).

Cela ne fonctionne pas très bien si vous voulez (disons) 10 éléments aléatoires dans l'intervalle 1..10.000 - vous finirez par faire beaucoup de travail inutilement. À ce stade, il est probablement préférable de conserver un ensemble de valeurs que vous avez générées jusqu'à présent et de continuer à générer des nombres en boucle jusqu'à ce que le prochain ne soit pas déjà présent :

if (max < numbersNeeded)
{
    throw new IllegalArgumentException("Can't ask for more numbers than are available");
}
Random rng = new Random(); // Ideally just create one instance globally
// Note: use LinkedHashSet to maintain insertion order
Set<Integer> generated = new LinkedHashSet<Integer>();
while (generated.size() < numbersNeeded)
{
    Integer next = rng.nextInt(max) + 1;
    // As we're adding to a set, this will automatically do a containment check
    generated.add(next);
}

Faites attention au choix de l'ensemble cependant - j'ai très délibérément utilisé LinkedHashSet car il maintient l'ordre d'insertion, ce qui nous intéresse ici.

Une autre option consiste à toujours progresser, en réduisant à chaque fois la portée et en compensant les valeurs existantes. Par exemple, supposons que vous vouliez 3 valeurs dans l'intervalle 0 9. À la première itération, vous générez n'importe quel nombre dans la plage 0 9 - disons que vous générez un 4.

À la deuxième itération, vous générez un nombre compris entre 0 et 8. Si le nombre généré est inférieur à 4, on le garde tel quel... sinon on lui ajoute un. Vous obtenez ainsi un résultat compris entre 0 et 9 sans 4. Supposons que nous obtenions 7 de cette façon.

À la troisième itération, vous générez un nombre compris entre 0 et 7. Si le nombre généré est inférieur à 4, on le garde tel quel. S'il est égal à 4 ou 5, on ajoute un chiffre. S'il est égal à 6 ou 7, vous ajoutez deux. Ainsi, la plage de résultats est de 0 à 9, sans 4 ni 6.

Answer 2

Voici comment je m'y prendrais

import java.util.ArrayList;
import java.util.Random;

public class Test {
    public static void main(String[] args) {
        int size = 20;

        ArrayList<Integer> list = new ArrayList<Integer>(size);
        for(int i = 1; i <= size; i++) {
            list.add(i);
        }

        Random rand = new Random();
        while(list.size() > 0) {
            int index = rand.nextInt(list.size());
            System.out.println("Selected: "+list.remove(index));
        }
    }
}

Comme l'estimé M. Skeet l'a souligné :
Si n est le nombre de numéros sélectionnés au hasard que vous souhaitez choisir et N est l'espace d'échantillonnage total des nombres disponibles pour la sélection :

1. Si n << N Dans ce cas, il suffit de stocker les numéros que vous avez choisis et de vérifier dans une liste si le numéro choisi s'y trouve.
2. Si n ~= N Dans ce cas, vous devriez probablement utiliser ma méthode, qui consiste à remplir une liste contenant l'ensemble de l'espace d'échantillonnage, puis à en retirer des numéros au fur et à mesure que vous les sélectionnez.

Answer 3

//random numbers are 0,1,2,3 
ArrayList<Integer> numbers = new ArrayList<Integer>();   
Random randomGenerator = new Random();
while (numbers.size() < 4) {

    int random = randomGenerator .nextInt(4);
    if (!numbers.contains(random)) {
        numbers.add(random);
    }
}

Answer 4

La manière la plus efficace et la plus basique d'obtenir des nombres aléatoires non répétitifs est expliquée par ce pseudo-code. Il n'est pas nécessaire d'avoir des boucles imbriquées ou des recherches hachées :

// get 5 unique random numbers, possible values 0 - 19
// (assume desired number of selections < number of choices)

const int POOL_SIZE = 20;
const int VAL_COUNT = 5;

declare Array mapping[POOL_SIZE];
declare Array results[VAL_COUNT];

declare i int;
declare r int;
declare max_rand int;

// create mapping array
for (i=0; i<POOL_SIZE; i++) {
   mapping[i] = i;
}

max_rand = POOL_SIZE-1;  // start loop searching for maximum value (19)

for (i=0; i<VAL_COUNT; i++) {
    r = Random(0, max_rand); // get random number
    results[i] = mapping[r]; // grab number from map array
    mapping[r] = max_rand;  // place item past range at selected location

    max_rand = max_rand - 1;  // reduce random scope by 1
}

Supposons que la première itération ait généré le nombre aléatoire 3 au départ (de 0 à 19). Cela ferait de results[0] = mapping[3], c'est-à-dire la valeur 3. Nous assignerions ensuite mapping[3] à 19.

Dans l'itération suivante, le nombre aléatoire était de 5 (de 0 à 18). Ainsi, résultats[1] = mapping[5], c'est-à-dire la valeur 5. Nous affecterions ensuite mapping[5] à 18.

Supposons maintenant que l'itération suivante choisisse à nouveau 3 (de 0 à 17). results[2] se verrait attribuer la valeur de mapping[3], mais maintenant, cette valeur n'est pas 3, mais 19.

Cette même protection persiste pour tous les numéros, même si vous avez obtenu le même numéro 5 fois de suite. Par exemple, si le générateur de nombres aléatoires vous a donné 0 cinq fois de suite, les résultats seraient les suivants : [ 0, 19, 18, 17, 16 ].

Vous n'obtiendrez jamais deux fois le même numéro.

Answer 5

Au lieu de faire tout cela, créez un LinkedHashSet et des nombres aléatoires à celui-ci par Math.random() .... si une entrée dupliquée se produit, la fonction LinkedHashSet n'ajoutera pas ce nombre à sa liste ... Puisque dans cette classe de collection, les valeurs en double ne sont pas autorisées, vous obtenez une liste de nombres aléatoires sans valeurs en double .... :D