Comment rendre les nombres aléatoires uniques

Tout le monde a des attentes intéressantes en ce qui concerne les nombres aléatoires – apparemment, vous vous attendez à ce que les nombres aléatoires soient uniques ! Si vous utilisez un bon générateur de nombres aléatoires, vos nombres aléatoires ne seront jamais garantis comme étant uniques.

Pour que cela soit plus évident, si vous vouliez générer des nombres aléatoires compris dans la plage [1, 2] et que vous deviez générer deux nombres, vous obtiendriez (normalement, attendez-vous à) l’une des quatre possibilités suivantes avec une probabilité égale:

1, 2
2, 1
1, 1
2, 2

Cela n’a aucun sens de demander à un bon générateur de nombres aléatoires de générer les deux premiers, mais pas les deux derniers.

Maintenant, prenez une seconde pour penser à quoi vous attendre si vous avez demandé de générer trois nombres dans la même plage … 1, 2, alors quoi ??

L’unicité, par conséquent, n’est pas et ne sera pas une propriété d’un générateur de nombres aléatoires.

Votre problème spécifique peut toutefois nécessiter un caractère unique. Dans ce cas, vous devez effectuer des travaux supplémentaires pour garantir l’unicité.

Une solution consiste à garder un onglet sur lequel les numéros sont déjà choisis. Vous pouvez les conserver dans un set et les repasser si vous en avez un que vous avez obtenu plus tôt. Toutefois, cela n’est efficace que si vous choisissez un petit ensemble de nombres par rapport à votre plage; si vous choisissez la plus grande partie de la plage, la fin du processus devient inefficace.

Si le nombre que vous allez sélectionner correspond à la plus grande partie de la plage, il est préférable d’utiliser un tableau de la plage et d’utiliser un algorithme de réorganisation méticuleux pour mélanger les chiffres. (Le mélange Fisher-Yates devrait faire l’affaire.)

Indice 0: Utilisez le résidu quadratique de la théorie des nombres; un entier q est appelé résidu quadratique modulo p s’il est congruent à un carré parfait modulo p ; c’est-à-dire, s’il existe un entier x tel que:

x ² ≡ q (mod p)

Astuce 1: Théorème: En supposant que p est un nombre premier, le résidu quadratique de x est unique tant que 2x

0 ² ≡ 0 (mod 13)

1 ² ≡ 1 (mod 13)

2 ² ≡ 4 (mod 13)

3 ² ≡ 9 (mod 13)

4 ² ≡ 3 (mod 13)

5 ² ≡ 12 (mod 13)

6 ² ≡ 10 (mod 13)

Astuce 2: Théorème: En supposant que p est un nombre premier tel que p ≡ 3 (mod 4), non seulement x ² % p (le résidu quadratique) est unique pour 2x

2 % p est également unique pour 2x> p. Par exemple:

0 ² % 11 = 0

1 ² % 11 = 1

2 ² % 11 = 4

3 ² % 11 = 9

4 ² % 11 = 5

5 ² % 11 = 3

11 – 6 ² % 11 = 8

11 – 7 ² % 11 = 6

11 – 8 ² % 11 = 2

11 – 9 ² % 11 = 7

11 – 10 ² % 11 = 10

Ainsi, cette méthode nous fournit une permutation parfaite de 1 à 1 sur les entiers inférieurs à p, p pouvant être tout nombre premier tel que p ≡ 3 (mod 4).

Astuce 3:

 unsigned int UniqueRandomMapping(unsigned int x) { const unsigned int p = 11; //any prime number satisfying p ≡ 3 (mod 4) unsigned int r = ((unsigned long long) x * x) % p; if (x <= p / 2) return r; else return p - r; } 

Je ne me suis pas inquiété des mauvais nombres d'entrée (par exemple, hors de scope).

Remarques

• Pour les entiers 32 bits, vous pouvez choisir le nombre premier le plus grand, tel que p ≡ 3 (mod 4), qui est inférieur à 2 ^32, soit 4294967291.
• Même si cette méthode vous donne un mappage 1-à-1 pour générer un nombre aléatoire, elle souffre du problème du clustering.
• Pour améliorer le caractère aléatoire de la méthode susmentionnée, combinez-la avec d'autres méthodes de mappage aléatoire uniques telles que l'opérateur XOR.

Je suppose que vous pouvez trouver un moyen de déterminer le nombre de nombres que vous souhaitez utiliser. C’est assez simple, car une entrée utilisateur de 2 va de 10 à 99, 3 de 100 à 999, etc.

Si vous voulez créer votre propre implémentation de nombres uniques générés de manière aléatoire, consultez ces liens.

http://en.wikipedia.org/wiki/Fisher%E2%80%93Yates_shuffle

Voici une implémentation très similaire: https://stackoverflow.com/a/196065/2142219

En substance, vous créez un tableau d’entiers X, tous définis sur la valeur de leur index. Vous sélectionnez de manière aléatoire un index entre 0 et MAX, en prenant la valeur de cet index et en l’échangeant avec la valeur max. MAX est alors décrémenté de 1 et vous pouvez le répéter en sélectionnant de manière aléatoire un index compris entre 0 et MAX – 1.

Cela vous donne un tableau aléatoire de 0 à 999 nombres entiers sans doublons.

Voici deux approches possibles pour générer des nombres aléatoires uniques dans une plage.

1. Gardez une trace des numéros que vous avez déjà générés en utilisant std::set , et jetez et régénérez les nombres tant qu’ils sont déjà dans l’ensemble. Cette approche n’est pas recommandée si vous souhaitez générer un grand nombre de nombres aléatoires, en raison du paradoxe de l’anniversaire.
2. Générez tous les nombres de votre plage, effectuez une permutation aléatoire de ceux-ci et indiquez le nombre de fois souhaité par l’utilisateur.

Les générateurs aléatoires standard ne généreraient jamais de nombres uniques, dans ce cas ils ne seraient pas indépendants.

Pour générer des numéros uniques, vous devez:

• Sauvegardez tous les nombres générés et comparez les nouveaux avec les anciens. S’il y a une coïncidence, régénérez.

ou

• Utilisez la fonction random_shuffle: http://fr.cppreference.com/w/cpp/algorithm/random_shuffle pour obtenir toutes les séquences à l’avance.

Tout d’abord, srand() / rand() ont généralement une période de 2 ^ 32, ce qui signifie qu’après avoir appelé srand() , rand() itérera en interne sur des entiers distincts lors des 2 ^ 32 premiers appels à rand() . Néanmoins, rand() peut très bien renvoyer un résultat de moins de 32 bits: par exemple, un int compris entre 0 et RAND_MAX où RAND_MAX est 2 ^ 31-1 ou 2 ^ 15-1, de sorte que vous pouvez voir des résultats répétés en tant qu’appelant de rand() Vous avez probablement lu sur la période cependant, ou le commentaire de quelqu’un l’a fait avec conscience, et d’une manière ou d’une autre, cela a été confondu avec l’unicité …

Deuxièmement, tout appel à rand() génère un nombre beaucoup plus grand que vous le souhaitez, et vous le faites …

 number1 % max 

Le résultat de ” number1 % max ” se situe dans la plage 0 <= N <= max , mais le nombre aléatoire lui-même peut avoir été un multiple de max supérieur à celui-ci. En d'autres termes, deux nombres aléatoires distincts qui diffèrent par un multiple de max produisent toujours le même résultat pour number1 % max dans votre programme.

Pour obtenir des nombres aléatoires distincts dans une plage, vous pouvez préremplir un std::vector avec tous les nombres, puis std::shuffle .