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

je pense que vous surestimez les problèmes avec l'approche 1). À moins que vous n'ayez des exigences en temps réel juste en vérifiant par choix aléatoire se termine assez rapidement. La probabilité d'avoir besoin de plus d'un nombre d'itérations décroît exponentiellement. Avec 100M nombres outputted (10% fillfactor) vous aurez une chance sur milliard d'exiger plus de 9 itérations. Même avec 50% des nombres pris vous aurez en moyenne besoin de 2 itérations et avoir une chance sur un milliard d'exiger plus de 30 vérifier. Ou même le cas extrême où 99% des nombres sont déjà pris pourrait encore être raisonnable - vous aurez une moyenne de 100 itérations et avoir 1 sur un milliard de changement de exiger 2062 itérations

la séquence de graines du générateur de nombres aléatoires congruents linéaires standard ne peut pas être répétée tant que l'ensemble complet de nombres à partir de la valeur de départ n'a pas été généré. Alors il doit répéter précisément.

la graine interne est souvent Grande (48 ou 64 bits). Les nombres générés sont plus petits (32 bits habituellement) parce que l'ensemble des bits ne sont pas aléatoires. Si vous suivez les valeurs de graine elles formeront une séquence non-répétitive distincte.

la question est essentiellement celle de localiser une bonne graine qui génère" assez " de nombres. Vous pouvez choisir une graine, et générer des nombres jusqu'à ce que vous obtenez de nouveau à la graine de départ. C'est la longueur de la séquence. Il peut s'agir de millions ou de milliards de nombres.

il y a quelques lignes directrices à Knuth pour cueillir des graines convenables qui produiront de très longues séquences de nombres uniques.

vous pouvez exécuter 1) sans courir dans le problème de trop de nombres aléatoires erronés si vous diminuez juste l'intervalle aléatoire d'un chaque fois.

pour que cette méthode fonctionne, vous devrez sauvegarder les nombres déjà donnés (ce que vous voulez faire de toute façon) et aussi sauvegarder la quantité de nombres pris.

il est assez évident que, après avoir recueilli 10 nombres, votre pool de nombres aléatoires possibles aura été diminué de 10. Donc, vous ne devez pas choisir un nombre entre 1 et 1.000.000 mais entre 1 et 999.990. Bien sûr, ce nombre n'est pas le nombre réel mais seulement un indice (à moins que les 10 nombres collectés aient été 999.991, 999.992, ...); il faudrait compter maintenant à partir de 1 en omettant tous les nombres déjà collectés.

bien sûr, votre algorithme devrait être plus intelligent que de 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'à Je en avoir un qui s'adapte à chaque. Il se sent juste mal.

My solution https://github.com/glushchenko/python-unique-id , je pense que vous devriez étendre la matrice pour 1.000.000.000 de variations et avoir du plaisir.

Je repenserais au problème lui-même... Vous ne semblez pas faire quelque chose de séquentiel avec les nombres... et vous avez un index sur la colonne. Ont-ils réellement besoin pour être numéros ?

considère un SHA hash... vous n'avez pas réellement besoin de toute chose. Faites ce que git ou d'autres services de raccourcissement d'url font, et prenez les premiers 3/4/5 caractères du hachage. Étant donné que chaque caractère 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 un contrôle rapide sur si la combinaison existe (une requête d'index pure) et une graine comme un timestamp + nombre aléatoire et il devrait faire pour presque n'importe quelle situation.

avez-vous besoin que ce soit cryptographiquement sécurisé ou juste difficile à deviner? Quelles sont les collisions? Parce que si elle doit être cryptographiquement forte et avoir zéro collisions, il est, malheureusement, impossible.

j'ai commencé à essayer d'écrire une explication de l'approche utilisée ci-dessous, mais juste la mettre en œuvre était plus facile et plus précis. Cette approche a le comportement étrange qu'il obtient plus vite les nombres que vous avez générés. Mais cela fonctionne, et cela ne vous oblige pas à générer tous les nombres à l'avance.

Comme une simple optimisation, vous pouvez facilement faire de cette classe utilisent un algorithme probabiliste (générer un nombre aléatoire, et si ce n'est pas dans l'ensemble des numéros utilisés ajoutez - le à l'ensemble et retournez-le) dans un premier temps, gardez le cap sur le taux de collision, et passez à l'approche déterministe utilisée ici une fois que le taux de collision devient mauvais.

import random

class NonRepeatingRandom(object):

    def __init__(self, maxvalue):
        self.maxvalue = maxvalue
        self.used = set()

    def next(self):
        if len(self.used) >= self.maxvalue:
            raise StopIteration
        r = random.randrange(0, self.maxvalue - len(self.used))
        result = 0
        for i in range(1, r+1):
            result += 1
            while result in self.used:
                 result += 1
        self.used.add(result)
        return result

    def __iter__(self):
        return self

    def __getitem__(self):
        raise NotImplemented

    def get_all(self):
        return [i for i in self]

>>> n = NonRepeatingRandom(20)
>>> n.get_all()
[12, 14, 13, 2, 20, 4, 15, 16, 19, 1, 8, 6, 7, 9, 5, 11, 10, 3, 18, 17]

S'il vous suffit qu'un observateur occasionnel ne puisse pas deviner la valeur suivante, vous pouvez utiliser des choses comme un générateur de congruence linéaire ou même un simple registre de décalage de rétroaction linéaire pour générer les valeurs et garder l'état dans la base de données dans le cas où vous avez besoin de plus de valeurs. Si vous utilisez ces droits, les valeurs ne se répèteront pas avant la fin de l'univers. Vous trouverez plus d'idées dans la liste des générateurs de nombres aléatoires .

si vous pensez qu'il pourrait y avoir quelqu'un qui aurait un intérêt sérieux à deviner les valeurs suivantes, vous pouvez utiliser une séquence de base de données pour compter les valeurs que vous générez et les chiffrer avec un algorithme de cryptage ou un autre cryptographiquement fort perfect a fonction. Cependant, vous devez prendre soin que l'algorithme de cryptage n'est pas facilement cassable si l'on peut mettre la main sur une séquence de numéros successifs que vous avez généré - un simple RSA par exemple, ne le fera pas à cause de L'attaque de message liée à Franklin-Reiter .

réponse un peu tardive, mais je n'ai vu cela suggéré nulle part.

pourquoi ne pas utiliser le module uuid pour créer identificateurs globaux uniques

pour générer une liste de nombres totalement aléatoires à l'intérieur d'un seuil défini, comme suit:

plist=list()
length_of_list=100
upbound=1000
lowbound=0
while len(pList)<(length_of_list):
     pList.append(rnd.randint(lowbound,upbound))
     pList=list(set(pList))

je suis tombé sur le même problème et j'ai ouvert une question avec un titre différent avant d'arriver à celle-ci. Ma solution est un échantillon aléatoire générateur d'index (c'est à dire la non-répétition des nombres) dans l'intervalle [0,maximal) , appelé itersample . Voici quelques exemples d'utilisation:

import random
generator=itersample(maximal)
another_number=generator.next() # pick the next non-repeating random number

ou

import random
generator=itersample(maximal)
for random_number in generator:
    # do something with random_number
    if some_condition: # exit loop when needed
        break

itersample génère des entiers aléatoires non répétitifs, besoin de stockage est limité aux numéros choisis, et le temps nécessaire pour choisir n numéros doivent être (comme certains tests le confirment) O(n log(n)) , quel que soit maximal .

voici le code de itersample :

import random
def itersample(c): # c = upper bound of generated integers
    sampled=[]
    def fsb(a,b): # free spaces before middle of interval a,b
        fsb.idx=a+(b+1-a)/2
        fsb.last=sampled[fsb.idx]-fsb.idx if len(sampled)>0 else 0
        return fsb.last
    while len(sampled)<c:
        sample_index=random.randrange(c-len(sampled))
        a,b=0,len(sampled)-1
        if fsb(a,a)>sample_index:
            yielding=sample_index
            sampled.insert(0,yielding)
            yield yielding
        elif fsb(b,b)<sample_index+1:
            yielding=len(sampled)+sample_index
            sampled.insert(len(sampled),yielding)
            yield yielding
        else: # sample_index falls inside sampled list
            while a+1<b:
                if fsb(a,b)<sample_index+1:
                    a=fsb.idx
                else:
                    b=fsb.idx
            yielding=a+1+sample_index
            sampled.insert(a+1,yielding)
            yield yielding

vous déclarez que vous stockez les numéros dans une base de données.

ne serait-il pas alors plus facile d'y stocker tous les numéros et de demander à la base de données un numéro aléatoire non utilisé? La plupart des bases de données soutiennent une telle demande.

exemples

MySQL:

SELECT column FROM table
ORDER BY RAND()
LIMIT 1

PostgreSQL:

SELECT column FROM table
ORDER BY RANDOM()
LIMIT 1