Question Générer des nombres aléatoires non répétitifs en Python


Ok c'est une de ces questions plus délicates que cela ne me semble donc je me tourne vers le débordement de pile car je ne peux pas penser à une bonne réponse. Voici ce que je veux: J'ai besoin de Python pour générer une simple liste de numéros de 0 à 1 000 000 000 dans un ordre aléatoire à utiliser pour les numéros de série (en utilisant un nombre aléatoire pour ne pas savoir combien ont été assignés ou synchronisés) attaque aussi facilement, c'est-à-dire deviner la prochaine Ces numéros sont stockés dans une table de base de données (indexée) avec les informations qui leur sont associées. Le programme qui les génère ne fonctionne pas pour toujours, il ne peut donc pas compter sur l'état interne.

Pas grave non? Il suffit de générer une liste de nombres, de les insérer dans un tableau et d'utiliser Python "random.shuffle (big_number_array)" et nous avons terminé. Le problème est que je voudrais éviter de devoir stocker une liste de nombres (et donc lire le fichier, en ouvrir une, enregistrez le fichier et fermez-le). Je préfère les générer à la volée. Le problème est que les solutions auxquelles je peux penser ont des problèmes:

1) Générez un nombre aléatoire puis vérifiez s'il a déjà été utilisé. S'il a été utilisé, générez un nouveau numéro, vérifiez, répétez au besoin jusqu'à ce que j'en trouve un inutilisé. Le problème ici est que je peux devenir malchanceux et générer beaucoup de nombres utilisés avant d'en obtenir un qui n'est pas utilisé. Correctif possible: utilisez un très grand nombre de chiffres pour réduire les risques (mais je me retrouve avec des nombres longs stupides).

2) Générez un nombre aléatoire et vérifiez s'il a déjà été utilisé. S'il a été utilisé, ajoutez ou soustrayez-en un du nombre et vérifiez à nouveau, continuez à répéter jusqu'à ce que je touche un numéro inutilisé. Le problème est que ce n’est plus un nombre aléatoire car j’ai introduit un biais (j’aurai éventuellement des nombres de nombres et vous pourrez prédire le nombre suivant avec une meilleure chance de succès).

3) Générez un nombre aléatoire, puis vérifiez s'il a déjà été utilisé. S'il a été utilisé, ajouter ou soustraire un autre nombre aléatoire généré aléatoirement et vérifier à nouveau, le problème est que nous sommes simplement revenus à la génération de nombres aléatoires et à la vérification comme dans la solution 1.

4) Suck it up et générer la liste aléatoire et l'enregistrer, faire en sorte qu'un démon les place dans une file d'attente afin qu'il y ait des nombres disponibles (et éviter d'ouvrir et de fermer constamment un fichier, en le groupant plutôt).

5) Générer des nombres aléatoires beaucoup plus importants et les hacher (c'est-à-dire utiliser MD5) pour obtenir une valeur numérique plus petite, nous devrions rarement obtenir des collisions, mais je me retrouve avec des nombres plus grands que nécessaire.

6) Ajouter ou ajouter des informations basées sur le temps au nombre aléatoire (par exemple, timestamp unix) pour réduire les risques de collision, là encore, je reçois des nombres plus importants que nécessaire.

N'importe qui a des idées intelligentes qui réduiront les risques de "collision" (c.-à-d. Générer un nombre aléatoire qui est déjà pris), mais me permettront également de garder le chiffre "petit" (moins d'un milliard vos européens =)).

Répondez et pourquoi je l'ai accepté:

Donc, je vais simplement aller avec 1, et j'espère que ce n'est pas un problème, mais si c'est le cas, j'irai avec la solution déterministe de générer tous les nombres et de les stocker pour qu'il y ait une garantie d'obtenir un nouveau nombre aléatoire, et je peux utilisez des "petits" nombres (c.-à-d. 9 chiffres au lieu d'un MD5 / etc.).


39
2018-01-16 09:27


origine


Réponses:


C’est un problème intéressant, et j’y pense depuis longtemps (avec des solutions similaires à Sjoerd's), mais à la fin, voici ce que je pense:

Utilisez votre point 1) et arrêtez de vous inquiéter.

En supposant un caractère aléatoire réel, la probabilité qu'un nombre aléatoire ait déjà été choisi est le nombre de nombres choisis précédemment divisé par la taille de votre pool, c'est-à-dire le nombre maximal.

Si vous dites que vous n’avez besoin que d’un milliard de chiffres, c’est-à-dire de neuf chiffres: accordez-vous 3 chiffres supplémentaires, vous avez donc des numéros de série à 12 chiffres (trois groupes de quatre chiffres - agréables et lisibles).

Même si vous êtes sur le point d'avoir choisi un milliard de numéros auparavant, la probabilité que votre nouveau numéro soit déjà pris n'est encore que de 0,1%.

Faites l'étape 1 et dessinez à nouveau. Vous pouvez toujours vérifier une boucle "infinie", par exemple, ne pas essayer plus de 1000 fois, puis revenir à l'ajout de 1 (ou autre chose).

Vous gagnerez à la loterie avant que ce repli ne soit utilisé.


25
2018-01-16 10:45



Vous pourriez utiliser Cryptage préservant le format pour crypter un compteur. Votre compteur passe juste de 0 à la hausse et le cryptage utilise une clé de votre choix pour en faire une valeur apparemment aléatoire, quelle que soit la largeur et la largeur souhaitées.

Les chiffres de bloc ont normalement une taille de bloc fixe, par ex. 64 ou 128 bits. Mais Format-Preserving Encryption vous permet de prendre un chiffrement standard comme AES et de faire un chiffrement de plus petite largeur, quelle que soit la largeur et la largeur souhaitées (par exemple, radix 10, largeur 9 pour les paramètres de la question), avec un algorithme encore cryptographiquement robuste.

Il est garanti de ne jamais avoir de collisions (car les algorithmes cryptographiques créent un mappage 1: 1). Il est également réversible (une cartographie bidirectionnelle), vous pouvez donc prendre le nombre résultant et revenir à la valeur de compteur avec laquelle vous avez commencé.

AES-FFX est une méthode standard proposée pour y parvenir.

J'ai expérimenté avec du code Python de base pour AES-FFX--voir le code Python ici (mais notez qu'il ne respecte pas complètement la spécification AES-FFX). Il peut par exemple crypter un compteur à un nombre décimal à 7 chiffres. Par exemple.:

0000000   0731134
0000001   6161064
0000002   8899846
0000003   9575678
0000004   3030773
0000005   2748859
0000006   5127539
0000007   1372978
0000008   3830458
0000009   7628602
0000010   6643859
0000011   2563651
0000012   9522955
0000013   9286113
0000014   5543492
0000015   3230955
...       ...

Pour un autre exemple en Python, en utilisant une autre méthode non-AES-FFX (je pense), voir ce blog "Comment générer un numéro de compte" qui fait FPE en utilisant un chiffrement Feistel. Il génère des nombres de 0 à 2 ^ 32-1.


12
2018-01-16 12:10



Avec des nombres arithmiques et des nombres premiers modulaires, vous pouvez créer tous les nombres entre 0 et un grand nombre premier, dans le désordre. Si vous choisissez soigneusement vos numéros, le prochain numéro est difficile à deviner.

modulo = 87178291199 # prime
incrementor = 17180131327 # relative prime

current = 433494437 # some start value
for i in xrange(1, 100):
    print current
    current = (current + incrementor) % modulo

9
2018-01-16 10:07



S'ils ne doivent pas être aléatoires, mais pas évidemment linéaires (1, 2, 3, 4, ...), alors voici un algorithme simple:

Choisissez deux nombres premiers. L'un d'eux sera le plus grand nombre que vous pouvez générer, il devrait donc être d'environ un milliard. L'autre devrait être assez grand.

max_value = 795028841
step = 360287471
previous_serial = 0
for i in xrange(0, max_value):
    previous_serial += step
    previous_serial %= max_value
    print "Serial: %09i" % previous_serial

Stockez simplement la série précédente à chaque fois afin de savoir où vous en étiez. Je ne peux pas prouver mathématiquement que cela fonctionne (a été trop long depuis ces classes particulières), mais il est manifestement correct avec des nombres premiers plus petits:

s = set()
with open("test.txt", "w+") as f:
    previous_serial = 0
    for i in xrange(0, 2711):
        previous_serial += 1811
        previous_serial %= 2711
        assert previous_serial not in s
        s.add(previous_serial)

Vous pourriez aussi le prouver empiriquement avec des nombres premiers à 9 chiffres, cela prendrait juste un peu plus de travail (ou beaucoup plus de mémoire).

Cela signifie que compte tenu de quelques numéros de série, il serait possible de déterminer quelles sont vos valeurs - mais avec seulement neuf chiffres, il est peu probable que vous choisissiez des nombres impossibles à mesurer.


6
2018-01-16 10:35



Si vous n'avez pas besoin de quelque chose de cryptographiquement sécurisé, mais juste "suffisamment obscurci" ...

Champs Galois

Vous pouvez essayer des opérations dans Champs Galois, par exemple. GF (2)32, pour mapper un compteur incrémenté simple X à un numéro de série apparemment aléatoire y:

x = counter_value
y = some_galois_function(x)
  • Multiplier par une constante
    • Inverse est de multiplier par l'inverse de la constante
  • Élever à un pouvoir: Xn
  • Réciproque X-1
    • Cas particulier de montée en puissance n
    • C'est son propre inverse
  • Exponentiation d'un élément primitif: uneX

Beaucoup de ces opérations ont une inverse, ce qui signifie que, compte tenu de votre numéro de série, vous pouvez calculer la valeur du compteur d'origine à partir de laquelle il a été dérivé.

Quant à trouver une bibliothèque pour Galois Field pour Python ... bonne question. Si vous n'avez pas besoin de vitesse (ce que vous ne voudriez pas pour cela), alors vous pourriez créer le vôtre. Je n'ai pas essayé ces:

Multiplication matricielle dans GF (2)

Choisissez une matrice inversible 32 × 32 appropriée dans GF (2) et multipliez un compteur d’entrée de 32 bits par celui-ci. Ceci est conceptuellement lié à LFSR, comme décrit dans La réponse de S.Lott.

CRC

Une possibilité connexe est d'utiliser un CRC calcul. Basé sur le reste de la longue division avec un polynôme irréductible dans GF (2). Le code Python est facilement disponible pour les CRC (crcmod, pycrc), bien que vous souhaitiez peut-être choisir un polynôme irréductible différent de celui normalement utilisé pour vos besoins. Je suis un peu flou sur la théorie, mais je pense qu'un CRC 32 bits devrait générer une valeur unique pour chaque combinaison possible d'entrées 4 octets. Vérifie ça. Il est assez facile de vérifier cela expérimentalement, en renvoyant la sortie dans l’entrée et en vérifiant qu’elle produit un cycle complet de longueur 2.32-1 (zéro mappe à zéro). Vous devrez peut-être vous débarrasser de tout XOR initial / final dans l'algorithme CRC pour que cette vérification fonctionne.


6
2018-01-17 01:04



Je pense que vous surestimez les problèmes avec l'approche 1). Sauf si vous avez des exigences en temps réel, la vérification par choix aléatoire se termine assez rapidement. La probabilité d'avoir besoin de plus d'un nombre d'itérations diminue de façon exponentielle. Avec 100 millions de numéros émis (facteur de remplissage de 10%), vous aurez une chance sur plusieurs milliards d'exiger plus de 9 itérations. Même avec 50% des chiffres, vous aurez besoin de 2 itérations en moyenne et vous aurez une chance sur 300 de demander plus de 30 contrôles. Ou même dans le cas extrême où 99% des nombres sont déjà pris, cela peut toujours être raisonnable - vous aurez une moyenne de 100 itérations et vous aurez 1 changement sur 1 milliard d'exigences d'itérations 2062


5
2018-01-16 12:26



La séquence de départ du générateur de nombres aléatoires linéaire linéaire standard ne peut PAS être répétée jusqu'à ce que le jeu complet de nombres de la valeur de départ ait été généré. Ensuite, il DOIT répéter avec précision.

La graine interne est souvent grande (48 ou 64 bits). Les nombres générés sont plus petits (32 bits en général) car l'ensemble des bits ne sont pas aléatoires. Si vous suivez les valeurs de départ, elles formeront une séquence distincte non répétée.

La question est essentiellement de trouver une bonne graine qui génère des nombres "suffisants". Vous pouvez choisir une graine et générer des nombres jusqu'à ce que vous reveniez à la graine de départ. C'est la longueur de la séquence. Ce peut être des millions ou des milliards de chiffres.

Knuth propose des directives pour la sélection de semences appropriées qui génèreront de très longues séquences de numéros uniques.


4
2018-01-16 13:09



Vous pouvez exécuter 1) sans rencontrer le problème d'un trop grand nombre de nombres aléatoires erronés si vous réduisez simplement l'intervalle aléatoire d'une fois à chaque fois.

Pour que cette méthode fonctionne, vous devrez enregistrer les numéros déjà donnés (que vous voulez faire de toute façon) et enregistrer également la quantité de numéros pris.

Il est assez évident que, après avoir collecté 10 numéros, votre pool de nombres aléatoires possibles aura été réduit de 10. Par conséquent, vous ne devez pas choisir un nombre entre 1 et 1.000.000 mais entre 1 et 999.990. Bien entendu, ce nombre n’est pas le nombre réel, mais seulement un index (à moins que les 10 numéros collectés aient été 999.991, 999.992, ...); Vous devez maintenant compter 1 en omettant tous les chiffres déjà recueillis.

Bien sûr, votre algorithme devrait être plus intelligent que de simplement compter de 1 à 1 000 000 mais j'espère que vous comprenez la méthode.

Je n'aime pas dessiner des nombres aléatoires jusqu'à ce que j'en trouve un qui corresponde non plus. Il se sent juste mal.


1
2018-01-18 01:18



Ma solution https://github.com/glushchenko/python-unique-idJe pense que vous devriez étendre la matrice pour 1 000 000 000 de variations et vous amuser.


1
2017-08-27 00:26



Je repenserais le problème lui-même ... Vous ne semblez pas faire de séquence avec les chiffres ... et vous avez un index sur la colonne qui les contient. Ont-ils réellement avoir besoin être Nombres?

Considérez un sha hash ... vous n'avez pas vraiment besoin de tout. Faites ce que font git ou d'autres services de raccourcis d'URL, et prenez les premiers 3/4/5 caractères du hachage. Étant donné que chaque personnage a maintenant 36 valeurs possibles au lieu de 10, vous avez 2 176 782 336 combinaisons au lieu de 999 999 combinaisons (pour six chiffres). Combinez cela avec une vérification rapide pour savoir si la combinaison existe (une requête d'index pur) et une graine comme un timestamp + un nombre aléatoire et il devrait faire pour presque n'importe quelle situation.


0
2018-01-16 09:51



Avez-vous besoin de cela pour être cryptographiquement sécurisé ou juste difficile à deviner? Quelle est la gravité des collisions? Parce que si elle doit être cryptographiquement forte et avoir des collisions nulles, c'est malheureusement impossible.


0
2018-01-16 10:35