Comment créer une liste de nombres aléatoires sans doublons ?

Question

J'ai essayé d'utiliser random.randint(0, 100) mais certains numéros sont les mêmes. Existe-t-il une méthode/module pour créer une liste de nombres aléatoires uniques ?

Note : Le code suivant est sur la base d'une réponse et a été ajouté après que la réponse ait été postée. Il ne fait pas partie de la question ; il constitue la solution.

def getScores():
    # open files to read and write
    f1 = open("page.txt", "r");
    p1 = open("pgRes.txt", "a");

    gScores = [];
    bScores = [];
    yScores = [];

    # run 50 tests of 40 random queries to implement "bootstrapping" method 
    for i in range(50):
        # get 40 random queries from the 50
        lines = random.sample(f1.readlines(), 40);

Answer 1

Afin d'obtenir un programme qui génère une liste de valeurs aléatoires sans doublons, qui soit déterministe, efficace et construit avec des constructions de programmation de base, considérez la fonction extractSamples définis ci-dessous,

def extractSamples(populationSize, sampleSize, intervalLst) :
    import random
    if (sampleSize > populationSize) :
        raise ValueError("sampleSize = "+str(sampleSize) +" > populationSize (= " + str(populationSize) + ")")
    samples = []
    while (len(samples) < sampleSize) :
        i = random.randint(0, (len(intervalLst)-1))
        (a,b) = intervalLst[i]
        sample = random.randint(a,b)
        if (a==b) :
            intervalLst.pop(i)
        elif (a == sample) : # shorten beginning of interval                                                                                                                                           
            intervalLst[i] = (sample+1, b)
        elif ( sample == b) : # shorten interval end                                                                                                                                                   
            intervalLst[i] = (a, sample - 1)
        else :
            intervalLst[i] = (a, sample - 1)
            intervalLst.append((sample+1, b))
        samples.append(sample)
    return samples

L'idée de base est de garder une trace des intervalles intervalLst pour les valeurs possibles parmi lesquelles nous pouvons sélectionner les éléments requis. Il s'agit d'un processus déterministe dans le sens où nous avons la garantie de générer un échantillon en un nombre fixe d'étapes (qui dépend uniquement de la valeur de l'échantillon). populationSize y sampleSize ).

Pour utiliser la fonction ci-dessus afin de générer notre liste requise,

In [3]: populationSize, sampleSize = 10**17, 10**5

In [4]: %time lst1 = extractSamples(populationSize, sampleSize, [(0, populationSize-1)])
CPU times: user 289 ms, sys: 9.96 ms, total: 299 ms
Wall time: 293 ms

Nous pouvons également comparer avec une solution antérieure (pour une valeur inférieure de populationSize)

In [5]: populationSize, sampleSize = 10**8, 10**5

In [6]: %time lst = random.sample(range(populationSize), sampleSize)
CPU times: user 1.89 s, sys: 299 ms, total: 2.19 s
Wall time: 2.18 s

In [7]: %time lst1 = extractSamples(populationSize, sampleSize, [(0, populationSize-1)])
CPU times: user 449 ms, sys: 8.92 ms, total: 458 ms
Wall time: 442 ms

Notez que j'ai réduit populationSize car il produit une erreur de mémoire pour les valeurs plus élevées lors de l'utilisation de l'outil de gestion de la mémoire. random.sample solution (également mentionnée dans les réponses précédentes aquí y aquí ). Pour les valeurs ci-dessus, nous pouvons également observer que extractSamples surpasse le random.sample approche.

P.S. : Bien que l'approche de base soit similaire à celle de ma réponse précédente Les modifications apportées à la mise en œuvre et à l'approche, ainsi que l'amélioration de la clarté, sont substantielles.

Answer 2

Vous pouvez utiliser Numpy bibliothèque pour une réponse rapide comme indiqué ci-dessous -

L'extrait de code suivant énumère 6 unique des chiffres compris entre 0 et 5. Vous pouvez ajuster les paramètres pour votre confort.

import numpy as np
import random
a = np.linspace( 0, 5, 6 )
random.shuffle(a)
print(a)

Sortie

[ 2.  1.  5.  3.  4.  0.]

Il ne met pas de contraintes comme nous le voyons dans random.sample comme référencé. aquí .

J'espère que cela vous aidera un peu.

Answer 3

Le problème avec les approches basées sur les ensembles ("si valeur aléatoire dans les valeurs retournées, réessayer") est que leur durée d'exécution est indéterminée en raison des collisions (qui nécessitent une autre itération "réessayer"), en particulier lorsqu'une grande quantité de valeurs aléatoires sont retournées à partir de la plage.

Une alternative qui n'est pas sujette à ce temps d'exécution non déterministe est la suivante :

import bisect
import random

def fast_sample(low, high, num):
    """ Samples :param num: integer numbers in range of
        [:param low:, :param high:) without replacement
        by maintaining a list of ranges of values that
        are permitted.

        This list of ranges is used to map a random number
        of a contiguous a range (`r_n`) to a permissible
        number `r` (from `ranges`).
    """
    ranges = [high]
    high_ = high - 1
    while len(ranges) - 1 < num:
        # generate a random number from an ever decreasing
        # contiguous range (which we'll map to the true
        # random number).
        # consider an example with low=0, high=10,
        # part way through this loop with:
        #
        # ranges = [0, 2, 3, 7, 9, 10]
        #
        # r_n :-> r
        #   0 :-> 1
        #   1 :-> 4
        #   2 :-> 5
        #   3 :-> 6
        #   4 :-> 8
        r_n = random.randint(low, high_)
        range_index = bisect.bisect_left(ranges, r_n)
        r = r_n + range_index
        for i in xrange(range_index, len(ranges)):
            if ranges[i] <= r:
                # as many "gaps" we iterate over, as much
                # is the true random value (`r`) shifted.
                r = r_n + i + 1
            elif ranges[i] > r_n:
                break
        # mark `r` as another "gap" of the original
        # [low, high) range.
        ranges.insert(i, r)
        # Fewer values possible.
        high_ -= 1
    # `ranges` happens to contain the result.
    return ranges[:-1]

Answer 4

import random

sourcelist=[]
resultlist=[]

for x in range(100):
    sourcelist.append(x)

for y in sourcelist:
    resultlist.insert(random.randint(0,len(resultlist)),y)

print (resultlist)

Answer 5

Si vous souhaitez vous assurer que les nombres ajoutés sont uniques, vous pouvez utiliser une balise Définir l'objet

si vous utilisez la version 2.7 ou supérieure, ou importez le module sets si ce n'est pas le cas.

Comme d'autres l'ont mentionné, cela signifie que les numéros ne sont pas vraiment aléatoires.