Créer des nombres aléatoires sans doublons

Dans ce cas, le MAX n'est que de 5, donc je pourrais vérifier les doublons un par un, mais comment pourrais-je faire cela 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;
        }

}

Le moyen le plus simple serait de créer une liste des nombres possibles (1..20 ou autre), puis de les mélanger avec Collections.shuffle. Ensuite, prenez le nombre d'éléments que vous souhaitez. C'est génial 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 si bien si vous voulez (disons) 10 éléments aléatoires dans la gamme 1..10 000 - vous finiriez 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 suivant 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);
}

Soyez prudent avec le choix d'ensemble - je l'ai utilisé très délibérément LinkedHashSetcar il maintient l'ordre d'insertion, ce qui nous intéresse ici.

Une autre option encore est de toujours progresser, en réduisant à chaque fois la plage et en compensant les valeurs existantes. Par exemple, supposons que vous vouliez 3 valeurs comprises entre 0 et 9. Lors de la première itération, vous générez n'importe quel nombre compris entre 0 et 9 - disons que vous générez un 4.

Lors de la deuxième itération, vous générez alors un nombre compris entre 0 et 8. Si le nombre généré est inférieur à 4, vous le conserverez tel quel ... sinon vous en ajoutez un. Cela vous donne une plage de résultats de 0..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, vous le conserverez tel quel. Si c'est 4 ou 5, vous en ajouteriez un. Si c'est 6 ou 7, vous en ajouteriez deux. De cette façon, la plage de résultats est 0..9 sans 4 ou 6.

Voici comment je le ferais

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'a souligné M. Skeet, estimé:
Si n est le nombre de nombres sélectionnés au hasard que vous souhaitez choisir et N est l'espace d'échantillonnage total de nombres disponibles pour la sélection:

1. Si n << N , vous devez simplement stocker les numéros que vous avez choisis et vérifier une liste pour voir si le numéro sélectionné y figure.
2. Si n ~ = N , vous devriez probablement utiliser ma méthode, en remplissant une liste contenant tout l'espace échantillon, puis en en supprimant les nombres au fur et à mesure que vous les sélectionnez.

//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);
    }
}

Il existe une autre façon de faire des nombres ordonnés "aléatoires" avec LFSR, jetez un œil à:

http://en.wikipedia.org/wiki/Linear_feedback_shift_register

avec cette technique, vous pouvez obtenir le nombre aléatoire ordonné par index et en vous assurant que les valeurs ne sont pas dupliquées.

Mais ce ne sont pas des nombres aléatoires VRAIS car la génération aléatoire est déterministe.

Mais selon votre cas, vous pouvez utiliser cette technique pour réduire la quantité de traitement lors de la génération de nombres aléatoires lors de l'utilisation de la lecture aléatoire.

Voici un algorithme LFSR en java, (je l'ai pris quelque part, je ne me souviens pas):

public final class LFSR {
    private static final int M = 15;

    // hard-coded for 15-bits
    private static final int[] TAPS = {14, 15};

    private final boolean[] bits = new boolean[M + 1];

    public LFSR() {
        this((int)System.currentTimeMillis());
    }

    public LFSR(int seed) {
        for(int i = 0; i < M; i++) {
            bits[i] = (((1 << i) & seed) >>> i) == 1;
        }
    }

    /* generate a random int uniformly on the interval [-2^31 + 1, 2^31 - 1] */
    public short nextShort() {
        //printBits();

        // calculate the integer value from the registers
        short next = 0;
        for(int i = 0; i < M; i++) {
            next |= (bits[i] ? 1 : 0) << i;
        }

        // allow for zero without allowing for -2^31
        if (next < 0) next++;

        // calculate the last register from all the preceding
        bits[M] = false;
        for(int i = 0; i < TAPS.length; i++) {
            bits[M] ^= bits[M - TAPS[i]];
        }

        // shift all the registers
        for(int i = 0; i < M; i++) {
            bits[i] = bits[i + 1];
        }

        return next;
    }

    /** returns random double uniformly over [0, 1) */
    public double nextDouble() {
        return ((nextShort() / (Integer.MAX_VALUE + 1.0)) + 1.0) / 2.0;
    }

    /** returns random boolean */
    public boolean nextBoolean() {
        return nextShort() >= 0;
    }

    public void printBits() {
        System.out.print(bits[M] ? 1 : 0);
        System.out.print(" -> ");
        for(int i = M - 1; i >= 0; i--) {
            System.out.print(bits[i] ? 1 : 0);
        }
        System.out.println();
    }


    public static void main(String[] args) {
        LFSR rng = new LFSR();
        Vector<Short> vec = new Vector<Short>();
        for(int i = 0; i <= 32766; i++) {
            short next = rng.nextShort();
            // just testing/asserting to make 
            // sure the number doesn't repeat on a given list
            if (vec.contains(next))
                throw new RuntimeException("Index repeat: " + i);
            vec.add(next);
            System.out.println(next);
        }
    }
}

Une autre approche qui vous permet de spécifier le nombre de nombres que vous voulez avec sizeet les valeurs minet maxdes nombres renvoyés

public static int getRandomInt(int min, int max) {
    Random random = new Random();

    return random.nextInt((max - min) + 1) + min;
}

public static ArrayList<Integer> getRandomNonRepeatingIntegers(int size, int min,
        int max) {
    ArrayList<Integer> numbers = new ArrayList<Integer>();

    while (numbers.size() < size) {
        int random = getRandomInt(min, max);

        if (!numbers.contains(random)) {
            numbers.add(random);
        }
    }

    return numbers;
}

Pour l'utiliser, renvoyer 7 nombres entre 0 et 25.

    ArrayList<Integer> list = getRandomNonRepeatingIntegers(7, 0, 25);
    for (int i = 0; i < list.size(); i++) {
        System.out.println("" + list.get(i));
    }

Ce serait beaucoup plus simple dans java-8:

Stream.generate(new Random()::ints)
            .distinct()
            .limit(16) // whatever limit you might need
            .toArray(Integer[]::new);

Le moyen le plus efficace et le plus basique d'avoir des nombres aléatoires non répétitifs est expliqué 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 génère le nombre aléatoire 3 pour commencer (de 0 à 19). Cela donnerait des résultats [0] = mapping [3], c'est-à-dire la valeur 3. Nous attribuerions alors le mapping [3] à 19.

Dans l'itération suivante, le nombre aléatoire était de 5 (de 0 à 18). Cela donnerait des résultats [1] = mapping [5], c'est-à-dire la valeur 5. Nous attribuerions ensuite le 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 donnait 0 cinq fois de suite, les résultats seraient: [0, 19, 18, 17, 16].

Vous n'obtiendrez jamais le même nombre deux fois.

Générer tous les indices d'une séquence est généralement une mauvaise idée, car cela peut prendre beaucoup de temps, surtout si le rapport des nombres à choisir MAXest faible (la complexité devient dominée par O(MAX)). Cela s'aggrave si le rapport des nombres à choisir à se MAXrapproche de un, car alors supprimer les indices choisis de la séquence de tous devient également coûteux (nous approchons O(MAX^2/2)). Mais pour les petits nombres, cela fonctionne généralement bien et n'est pas particulièrement sujet aux erreurs.

Filtrer les indices générés à l'aide d'une collection est également une mauvaise idée, car un certain temps est passé à insérer les indices dans la séquence, et la progression n'est pas garantie car le même nombre aléatoire peut être tiré plusieurs fois (mais pour suffisamment grand, MAXil est peu probable ). Cela pourrait être proche de la complexité
O(k n log^2(n)/2), en ignorant les doublons et en supposant que la collection utilise un arbre pour une recherche efficace (mais avec un coût constant important kd'allocation des nœuds de l'arbre et éventuellement un rééquilibrage ).

Une autre option consiste à générer les valeurs aléatoires uniquement depuis le début, garantissant que des progrès sont réalisés. Cela signifie qu'au premier tour, un index aléatoire [0, MAX]est généré:

items i0 i1 i2 i3 i4 i5 i6 (total 7 items)
idx 0       ^^             (index 2)

Au deuxième tour, seul [0, MAX - 1]est généré (car un élément a déjà été sélectionné):

items i0 i1    i3 i4 i5 i6 (total 6 items)
idx 1          ^^          (index 2 out of these 6, but 3 out of the original 7)

Les valeurs des indices doivent alors être ajustées: si le deuxième indice tombe dans la seconde moitié de la séquence (après le premier index), il doit être incrémenté pour tenir compte de l'écart. Nous pouvons l'implémenter en boucle, nous permettant de sélectionner un nombre arbitraire d'éléments uniques.

Pour les séquences courtes, il s'agit d'un O(n^2/2)algorithme assez rapide :

void RandomUniqueSequence(std::vector<int> &rand_num,
    const size_t n_select_num, const size_t n_item_num)
{
    assert(n_select_num <= n_item_num);

    rand_num.clear(); // !!

    // b1: 3187.000 msec (the fastest)
    // b2: 3734.000 msec
    for(size_t i = 0; i < n_select_num; ++ i) {
        int n = n_Rand(n_item_num - i - 1);
        // get a random number

        size_t n_where = i;
        for(size_t j = 0; j < i; ++ j) {
            if(n + j < rand_num[j]) {
                n_where = j;
                break;
            }
        }
        // see where it should be inserted

        rand_num.insert(rand_num.begin() + n_where, 1, n + n_where);
        // insert it in the list, maintain a sorted sequence
    }
    // tier 1 - use comparison with offset instead of increment
}

Où n_select_numest votre 5 et n_number_numest votre MAX. Le n_Rand(x)retourne des entiers aléatoires dans [0, x](inclus). Cela peut être un peu plus rapide si vous sélectionnez un grand nombre d'éléments (par exemple pas 5 mais 500) en utilisant la recherche binaire pour trouver le point d'insertion. Pour ce faire, nous devons nous assurer de répondre aux exigences.

Nous ferons une recherche binaire avec la comparaison n + j < rand_num[j]qui est la même que
n < rand_num[j] - j. Nous devons montrer qu'il rand_num[j] - js'agit toujours d'une séquence triée pour une séquence triée rand_num[j]. Ceci est heureusement facile à montrer, car la distance la plus basse entre deux éléments de l'original rand_numest un (les nombres générés sont uniques, il y a donc toujours une différence d'au moins 1). En même temps, si nous soustrayons les indices jde tous les éléments
rand_num[j], les différences d'index sont exactement de 1. Donc, dans le «pire» cas, nous obtenons une séquence constante - mais jamais décroissante. La recherche binaire peut donc être utilisée, donnant l' O(n log(n))algorithme:

struct TNeedle { // in the comparison operator we need to make clear which argument is the needle and which is already in the list; we do that using the type system.
    int n;

    TNeedle(int _n)
        :n(_n)
    {}
};

class CCompareWithOffset { // custom comparison "n < rand_num[j] - j"
protected:
    std::vector<int>::iterator m_p_begin_it;

public:
    CCompareWithOffset(std::vector<int>::iterator p_begin_it)
        :m_p_begin_it(p_begin_it)
    {}

    bool operator ()(const int &r_value, TNeedle n) const
    {
        size_t n_index = &r_value - &*m_p_begin_it;
        // calculate index in the array

        return r_value < n.n + n_index; // or r_value - n_index < n.n
    }

    bool operator ()(TNeedle n, const int &r_value) const
    {
        size_t n_index = &r_value - &*m_p_begin_it;
        // calculate index in the array

        return n.n + n_index < r_value; // or n.n < r_value - n_index
    }
};

Et enfin:

void RandomUniqueSequence(std::vector<int> &rand_num,
    const size_t n_select_num, const size_t n_item_num)
{
    assert(n_select_num <= n_item_num);

    rand_num.clear(); // !!

    // b1: 3578.000 msec
    // b2: 1703.000 msec (the fastest)
    for(size_t i = 0; i < n_select_num; ++ i) {
        int n = n_Rand(n_item_num - i - 1);
        // get a random number

        std::vector<int>::iterator p_where_it = std::upper_bound(rand_num.begin(), rand_num.end(),
            TNeedle(n), CCompareWithOffset(rand_num.begin()));
        // see where it should be inserted

        rand_num.insert(p_where_it, 1, n + p_where_it - rand_num.begin());
        // insert it in the list, maintain a sorted sequence
    }
    // tier 4 - use binary search
}

J'ai testé cela sur trois benchmarks. Tout d'abord, 3 numéros ont été choisis sur 7 éléments, et un histogramme des éléments choisis a été accumulé sur 10000 passages:

4265 4229 4351 4267 4267 4364 4257

Cela montre que chacun des 7 items a été choisi approximativement le même nombre de fois, et il n'y a pas de biais apparent causé par l'algorithme. L'exactitude de toutes les séquences a également été vérifiée (unicité du contenu).

Le deuxième critère consistait à choisir 7 numéros sur 5000 articles. Le temps de plusieurs versions de l'algorithme s'est accumulé sur 10 000 000 d'exécutions. Les résultats sont indiqués dans les commentaires dans le code comme b1. La version simple de l'algorithme est légèrement plus rapide.

Le troisième critère consistait à choisir 700 numéros sur 5000 éléments. Le temps de plusieurs versions de l'algorithme s'est à nouveau accumulé, cette fois sur 10 000 exécutions. Les résultats sont indiqués dans les commentaires dans le code comme b2. La version de recherche binaire de l'algorithme est maintenant plus de deux fois plus rapide que la version simple.

La deuxième méthode commence à être plus rapide pour choisir plus de 75 éléments environ sur ma machine (notez que la complexité de l'un ou l'autre algorithme ne dépend pas du nombre d'éléments, MAX).

Il est à noter que les algorithmes ci-dessus génèrent les nombres aléatoires dans l'ordre croissant. Mais il serait simple d'ajouter un autre tableau dans lequel les numéros seraient enregistrés dans l'ordre dans lequel ils ont été générés, et de le renvoyer à la place (à un coût supplémentaire négligeable O(n)). Il n'est pas nécessaire de mélanger la sortie: ce serait beaucoup plus lent.

Notez que les sources sont en C ++, je n'ai pas Java sur ma machine, mais le concept doit être clair.

MODIFIER :

Pour m'amuser, j'ai également implémenté l'approche qui génère une liste avec tous les indices
0 .. MAX, les choisit au hasard et les supprime de la liste pour garantir l'unicité. Depuis que j'ai choisi assez haut MAX(5000), les performances sont catastrophiques:

// b1: 519515.000 msec
// b2: 20312.000 msec
std::vector<int> all_numbers(n_item_num);
std::iota(all_numbers.begin(), all_numbers.end(), 0);
// generate all the numbers

for(size_t i = 0; i < n_number_num; ++ i) {
    assert(all_numbers.size() == n_item_num - i);
    int n = n_Rand(n_item_num - i - 1);
    // get a random number

    rand_num.push_back(all_numbers[n]); // put it in the output list
    all_numbers.erase(all_numbers.begin() + n); // erase it from the input
}
// generate random numbers

J'ai également implémenté l'approche avec une set(une collection C ++), qui arrive en deuxième position sur le benchmark b2, étant seulement environ 50% plus lente que l'approche avec la recherche binaire. Cela est compréhensible, car le setutilise un arbre binaire, où le coût d'insertion est similaire à la recherche binaire. La seule différence est la possibilité d'obtenir des éléments en double, ce qui ralentit la progression.

// b1: 20250.000 msec
// b2: 2296.000 msec
std::set<int> numbers;
while(numbers.size() < n_number_num)
    numbers.insert(n_Rand(n_item_num - 1)); // might have duplicates here
// generate unique random numbers

rand_num.resize(numbers.size());
std::copy(numbers.begin(), numbers.end(), rand_num.begin());
// copy the numbers from a set to a vector

Le code source complet est ici .

Vous pouvez utiliser l'une des classes implémentant l'interface Set ( API ), puis chaque nombre que vous générez, utilisez Set.add () pour l'insérer.

Si la valeur de retour est false, vous savez que le nombre a déjà été généré auparavant.

Au lieu de faire tout cela, créez un LinkedHashSetobjet et des nombres aléatoires par Math.random()fonction .... si une entrée dupliquée se produit, l' LinkedHashSetobjet n'ajoutera pas ce numéro à sa liste ... Puisque dans cette classe de collection aucune valeur en double n'est autorisée. à la fin, vous obtenez une liste de nombres aléatoires sans valeurs dupliquées ....: D

Votre problème semble se réduire à choisir k éléments au hasard dans une collection de n éléments. La réponse Collections.shuffle est donc correcte, mais comme indiqué inefficace: son O (n).

Wikipedia: Le shuffle de Fisher – Yates a une version O (k) lorsque le tableau existe déjà. Dans votre cas, il n'y a pas de tableau d'éléments et la création du tableau d'éléments pourrait être très coûteuse, par exemple si max était de 10000000 au lieu de 20.

L'algorithme de mélange consiste à initialiser un tableau de taille n où chaque élément est égal à son index, à choisir k nombres aléatoires chaque nombre dans une plage avec le maximum inférieur à la plage précédente, puis à permuter les éléments vers la fin du tableau.

Vous pouvez faire la même opération en temps O (k) avec un hashmap bien que j'admette que c'est une sorte de douleur. Notez que cela ne vaut que si k est bien inférieur à n. (c'est-à-dire k ~ lg (n) ou plus), sinon vous devriez utiliser la lecture aléatoire directement.

Vous utiliserez votre hashmap comme une représentation efficace du tableau de sauvegarde dans l'algorithme de lecture aléatoire. Tout élément du tableau égal à son index n'a pas besoin d'apparaître dans la carte. Cela vous permet de représenter un tableau de taille n en temps constant, il n'y a pas de temps passé à l'initialiser.

1. Choisissez k nombres aléatoires: le premier est compris entre 0 et n-1, le second 0 à n-2, le troisième 0 à n-3 et ainsi de suite, à travers k.

2. Traitez vos nombres aléatoires comme un ensemble de swaps. Le premier indice aléatoire passe à la position finale. Le deuxième indice aléatoire passe à l'avant-dernière position. Cependant, au lieu de travailler contre un tableau de sauvegarde, travaillez contre votre hashmap. Votre hashmap stockera chaque élément qui est hors de position.

int getValue(i)
{
    if (map.contains(i)) 
        return map[i];
    return i;
}

void setValue(i, val)
{   
    if (i == val)
        map.remove(i);
    else
        map[i] = val;
}

int[] chooseK(int n, int k)
{
    for (int i = 0; i < k; i++)
    {
        int randomIndex = nextRandom(0, n - i); //(n - i is exclusive)
        int desiredIndex = n-i-1;

        int valAtRandom = getValue(randomIndex);
        int valAtDesired = getValue(desiredIndex);

        setValue(desiredIndex, valAtRandom);
        setValue(randomIndex, valAtDesired);
    }

    int[] output = new int[k];
    for (int i = 0; i < k; i++)
    {
        output[i] = (getValue(n-i-1));
    }

    return output;
}

Le code suivant crée un nombre aléatoire de séquence entre [1, m] qui n'a pas été généré auparavant.

public class NewClass {

    public List<Integer> keys = new ArrayList<Integer>();

    public int rand(int m) {
        int n = (int) (Math.random() * m + 1);
        if (!keys.contains(n)) {
            keys.add(n);
            return n;
        } else {
            return rand(m);
        }
    }

    public static void main(String[] args) {
        int m = 4;
        NewClass ne = new NewClass();
        for (int i = 0; i < 4; i++) {
            System.out.println(ne.rand(m));
        }
        System.out.println("list: " + ne.keys);
    }
}

Il existe un algorithme de lot de cartes: vous créez un tableau ordonné de nombres (le "lot de cartes") et à chaque itération vous en sélectionnez un nombre à une position aléatoire (en supprimant le numéro sélectionné du "lot de cartes" bien sûr).

Voici une solution efficace pour créer rapidement un tableau aléatoire. Après la randomisation, vous pouvez simplement choisir le n-ème élément edu tableau, l'incrémenter net le retourner e. Cette solution a O (1) pour obtenir un nombre aléatoire et O (n) pour l'initialisation, mais comme compromis nécessite une bonne quantité de mémoire si n devient suffisamment grand.

Il existe une solution plus efficace et moins lourde pour les entiers qu'un Collections.shuffle.

Le problème est le même que de sélectionner successivement des articles uniquement à partir des articles non sélectionnés dans un ensemble et de les mettre en ordre ailleurs. C'est exactement comme distribuer des cartes au hasard ou tirer des billets de tombola gagnants dans un chapeau ou une poubelle.

Cet algorithme fonctionne pour charger n'importe quel tableau et obtenir un ordre aléatoire à la fin du chargement. Cela fonctionne également pour l'ajout dans une collection List (ou toute autre collection indexée) et pour obtenir une séquence aléatoire dans la collection à la fin des ajouts.

Cela peut être fait avec un seul tableau, créé une fois, ou une collection ordonnée numériquement, telle qu'une liste, en place. Pour un tableau, la taille initiale du tableau doit être la taille exacte pour contenir toutes les valeurs voulues. Si vous ne savez pas combien de valeurs peuvent apparaître à l'avance, l'utilisation d'une collection ordonnée numériquement, telle qu'une ArrayList ou une List, où la taille n'est pas immuable, fonctionnera également. Il fonctionnera universellement pour un tableau de n'importe quelle taille jusqu'à Integer.MAX_VALUE, soit un peu plus de 2 000 000 000. Les objets de liste auront les mêmes limites d'index. Votre ordinateur peut manquer de mémoire avant d'arriver à un tableau de cette taille. Il peut être plus efficace de charger un tableau typé dans les types d'objet et de le convertir en une collection, après avoir chargé le tableau. Cela est particulièrement vrai si la collection cible n'est pas indexée numériquement.

Cet algorithme, exactement tel qu'il est écrit, créera une distribution très uniforme où il n'y a pas de doublons. Un aspect TRÈS IMPORTANT est qu'il doit être possible que l'insertion de l'élément suivant se produise jusqu'à la taille actuelle + 1. Ainsi, pour le deuxième élément, il pourrait être possible de le stocker à l'emplacement 0 ou à l'emplacement 1 Pour le 20e article, il pourrait être possible de le stocker dans n'importe quel emplacement, de 0 à 19. Il est tout aussi possible que le premier article reste à l'emplacement 0 car il se retrouve à n'importe quel autre emplacement. Il est tout aussi possible que le nouvel élément suivant aille n'importe où, y compris le nouvel emplacement suivant.

Le caractère aléatoire de la séquence sera aussi aléatoire que le caractère aléatoire du générateur de nombres aléatoires.

Cet algorithme peut également être utilisé pour charger des types de référence dans des emplacements aléatoires dans un tableau. Comme cela fonctionne avec un tableau, il peut également fonctionner avec des collections. Cela signifie que vous n'avez pas besoin de créer la collection, puis de la mélanger ou de la classer selon les ordres d'insertion des objets. La collection doit seulement avoir la possibilité d'insérer un élément n'importe où dans la collection ou de l'ajouter.

// RandomSequence.java
import java.util.Random;
public class RandomSequence {

    public static void main(String[] args) {
        // create an array of the size and type for which
        // you want a random sequence
        int[] randomSequence = new int[20];
        Random randomNumbers = new Random();

        for (int i = 0; i < randomSequence.length; i++ ) {
            if (i == 0) { // seed first entry in array with item 0
                randomSequence[i] = 0; 
            } else { // for all other items...
                // choose a random pointer to the segment of the
                // array already containing items
                int pointer = randomNumbers.nextInt(i + 1);
                randomSequence[i] = randomSequence[pointer]; 
                randomSequence[pointer] = i;
                // note that if pointer & i are equal
                // the new value will just go into location i and possibly stay there
                // this is VERY IMPORTANT to ensure the sequence is really random
                // and not biased
            } // end if...else
        } // end for
        for (int number: randomSequence) {
                System.out.printf("%2d ", number);
        } // end for
    } // end main
} // end class RandomSequence

Tout dépend exactement de POURQUOI vous avez besoin de la génération aléatoire, mais voici mon avis.

Commencez par créer une méthode autonome pour générer le nombre aléatoire. Assurez-vous de tenir compte des limites.

public static int newRandom(int limit){
    return generatedRandom.nextInt(limit);  }

Ensuite, vous voudrez créer une structure de décision très simple qui compare les valeurs. Cela peut être fait de deux manières. Si vous avez un nombre très limité de nombres à vérifier, une simple instruction IF suffira:

public static int testDuplicates(int int1, int int2, int int3, int int4, int int5){
    boolean loopFlag = true;
    while(loopFlag == true){
        if(int1 == int2 || int1 == int3 || int1 == int4 || int1 == int5 || int1 == 0){
            int1 = newRandom(75);
            loopFlag = true;    }
        else{
            loopFlag = false;   }}
    return int1;    }

Ce qui précède compare int1 à int2 à int5, tout en s'assurant qu'il n'y a pas de zéros dans les aléas.

Avec ces deux méthodes en place, nous pouvons effectuer les opérations suivantes:

    num1 = newRandom(limit1);
    num2 = newRandom(limit1);
    num3 = newRandom(limit1);
    num4 = newRandom(limit1);
    num5 = newRandom(limit1);

Suivi par:

        num1 = testDuplicates(num1, num2, num3, num4, num5);
        num2 = testDuplicates(num2, num1, num3, num4, num5);
        num3 = testDuplicates(num3, num1, num2, num4, num5);
        num4 = testDuplicates(num4, num1, num2, num3, num5);
        num5 = testDuplicates(num5, num1, num2, num3, num5);

Si vous avez une liste plus longue à vérifier, une méthode plus complexe donnera de meilleurs résultats à la fois en termes de clarté du code et de traitement des ressources.

J'espère que cela t'aides. Ce site m'a tellement aidé que je me suis senti obligé d'au moins ESSAYER d'aider aussi.

J'ai créé un extrait de code qui ne génère aucun entier aléatoire en double. l'avantage de cet extrait de code est que vous pouvez lui affecter la liste d'un tableau et générer également l'élément aléatoire.

Aucune classe de générateur aléatoire de duplication

Le moyen le plus simple consiste à utiliser nano DateTime comme format long. System.nanoTime ();