Créer une séquence de nombres aléatoires sans répétitions

Question

Duplicata :

Des nombres aléatoires uniques en O(1) ?

Je veux un générateur de nombres pseudo-aléatoires capable de générer des nombres sans répétitions dans un ordre aléatoire.

Par exemple :

aléatoire(10)

m [ ]

Y a-t-il une meilleure façon de procéder que de créer une plage de nombres et de les mélanger, ou de vérifier que la liste générée ne contient pas de répétitions ?

---

Editar:

Je veux aussi qu'il soit efficace pour générer de grands nombres sans la gamme entière.

---

Editar:

Je vois que tout le monde suggère des algorithmes de brassage. Mais si je veux générer un grand nombre aléatoire (1024 octets+), cette méthode prendrait beaucoup plus de mémoire que si j'utilisais un RNG normal et l'insérait dans un ensemble jusqu'à ce qu'il ait une longueur spécifiée, n'est-ce pas ? N'y a-t-il pas de meilleur algorithme mathématique pour cela ?

Answer 1

Vous pourriez être intéressé par un registre à décalage à rétroaction linéaire. Nous avions l'habitude de les construire à partir de matériel, mais j'en ai aussi fait en logiciel. Il utilise un registre à décalage dont certains bits sont xorés et renvoyés à l'entrée, et si vous choisissez les bons "taps", vous pouvez obtenir une séquence aussi longue que la taille du registre. En d'autres termes, un RFS 16 bits peut produire une séquence de 65535 caractères sans répétitions. C'est statistiquement aléatoire mais bien sûr éminemment répétable. De plus, si l'on s'y prend mal, on peut obtenir des séquences très courtes et embarrassantes. Si vous recherchez le lfsr, vous trouverez des exemples de la façon de les construire correctement (c'est-à-dire de la "longueur maximale").

Answer 2

Un shuffle est un excellent moyen de le faire (à condition de ne pas introduire de biais en utilisant l'algorithme naïf). Voir Le remaniement Fisher-Yates .

Answer 3

Afin de s'assurer que la liste ne se répète pas, il faudrait conserver une liste des numéros précédemment retournés. Comme il doit donc générer la liste entière à la fin de l'algorithme, cela équivaut, en termes de besoins de stockage, à générer la liste ordonnée puis à la mélanger.

Pour en savoir plus sur le brassage, cliquez ici : http://stackoverflow.com/questions/168037/creating-a-random-ordered-list-from-an-ordered-list

Cependant, si la plage des nombres aléatoires est très large mais que la quantité de nombres requise est faible (vous avez laissé entendre que c'est la condition réelle dans un commentaire), alors générer une liste complète et la mélanger est un gaspillage. Le brassage d'un énorme tableau implique d'accéder à des pages de mémoire virtuelle d'une manière qui (par définition) mettra en échec le système de pagination du système d'exploitation (à plus petite échelle, le même problème se poserait avec le cache mémoire du CPU).

Dans ce cas, la recherche dans la liste jusqu'à présent sera beaucoup plus efficace. L'idéal serait donc d'utiliser une heuristique (déterminée par l'expérience) pour choisir la bonne implémentation pour les arguments donnés. (Je m'excuse de donner des exemples en C# plutôt qu'en C++ mais ASFAC++B Je m'entraîne à penser en C#).

IEnumerable<int> GenerateRandomNumbers(int range, int quantity)
{
    int[] a = new int[quantity];

    if (range < Threshold)
    {
        for (int n = 0; n < range; n++)
            a[n] = n;

        Shuffle(a);
    }
    else
    {
        HashSet<int> used = new HashSet<int>();

        for (int n = 0; n < quantity; n++)
        {
            int r = Random(range);

             while (!used.Add(r))
                 r = Random(range);

             a[n] = r;
        }
    }

    return a;
}

Le coût de la vérification des nombres répétés, des boucles lorsqu'il y a des collisions, etc. sera élevé, mais il y aura probablement un certain nombre d'améliorations. Threshold où cela devient plus rapide que d'allouer pour la plage entière.

Pour des besoins en quantité suffisamment faible, il peut être plus rapide d'utiliser un tableau pour used et faire des recherches linéaires dans celui-ci, en raison de la plus grande localité, de la moindre surcharge, de l'économie de la comparaison...

De même, pour de grandes quantités ET de grandes plages, il peut être préférable de renvoyer un objet qui produit les numéros de la séquence sur demande, au lieu d'allouer d'emblée le tableau des résultats. Ceci est très facile à mettre en œuvre en C# grâce à la fonction yield return mot-clé :

IEnumerable<int> ForLargeQuantityAndRange(int quantity, int range)
{
    for (int n = 0; n < quantity; n++)
    {
        int r = Random(range);

        while (!used.Add(r))
            r = Random(range);

        yield return r;
    }
}

Answer 4

Si l'on garantit qu'un nombre aléatoire ne se répète jamais, il n'est plus aléatoire et la quantité d'erreurs de calcul est réduite. aléatoire diminue au fur et à mesure que les numéros sont générés (après neuf numéros random(10) est plutôt prévisible et même après seulement huit, vous avez une chance sur deux).

Answer 5

Un shuffle est ce que vous pouvez faire de mieux pour obtenir des nombres aléatoires dans une plage spécifique sans répétitions. La raison pour laquelle la méthode que vous décrivez (générer des nombres aléatoires et les placer dans un ensemble jusqu'à ce que vous atteigniez une longueur spécifique) est moins efficace est due aux doublons. Théoriquement, cet algorithme pourrait ne jamais se terminer. Au mieux, il se terminera dans un temps indéterminable, par rapport à un shuffle, qui s'exécutera toujours dans un temps hautement prévisible.

---

Réponse aux vérifications et aux commentaires :

Si, comme vous l'indiquez dans les commentaires, la plage de nombres est très large et que vous souhaitez en sélectionner relativement peu au hasard sans répétition, la probabilité de répétitions diminue rapidement. Plus la différence de taille entre la plage et le nombre de sélections est grande, plus la probabilité de répétitions est faible, et plus les performances de l'algorithme de sélection et de vérification que vous décrivez dans la question seront bonnes.