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

Cela renvoie une liste de 10 numéros sélectionnés dans la plage de 0 à 99, sans doublons.

import random
random.sample(range(100), 10)

En référence à votre exemple de code spécifique, vous voulez probablement lire toutes les lignes du fichier une fois puis sélectionnez des lignes aléatoires dans la liste enregistrée en mémoire. Par exemple :

all_lines = f1.readlines()
for i in range(50):
    lines = random.sample(all_lines, 40)

De cette façon, vous n'avez besoin de lire le fichier qu'une seule fois, avant votre boucle. Il est beaucoup plus efficace de procéder ainsi que de revenir au début du fichier et d'appeler f1.readlines() à nouveau pour chaque itération de la boucle.

Answer 2

Vous pouvez utiliser le remue-ménage de la fonction au hasard module comme celui-ci :

import random

my_list = list(xrange(1,100)) # list of integers from 1 to 99
                              # adjust this boundaries to fit your needs
random.shuffle(my_list)
print my_list # <- List of unique random numbers

Notez ici que la méthode shuffle ne renvoie pas de liste comme on pourrait s'y attendre, elle ne fait que mélanger la liste passée par référence.

Answer 3

Vous pouvez d'abord créer une liste de numéros à partir de a a b , donde a y b sont respectivement le plus petit et le plus grand nombre dans votre liste, puis mélangez-la avec Fisher-Yates ou en utilisant l'algorithme de Python. random.shuffle méthode.

Answer 4

Générateur de nombres pseudo-aléatoires congruentiels linéaires

Mémoire O(1)

Opérations O(k)

Ce problème peut être résolu par une simple Générateur linéaire de congruence . Cela nécessite une charge mémoire constante (8 entiers) et au plus 2*(longueur de la séquence) de calculs.

Toutes les autres solutions utilisent plus de mémoire et plus de calcul ! Si vous n'avez besoin que de quelques séquences aléatoires, cette méthode sera nettement moins chère. Pour les plages de taille N si vous souhaitez générer un chiffre d'affaires de l'ordre de 1,5 milliard d'euros. N unique k -ou plus, je recommande la solution acceptée en utilisant les méthodes intégrées. random.sample(range(N),k) comme ceci a été optimisé en python pour plus de rapidité.

Code

# Return a randomized "range" using a Linear Congruential Generator
# to produce the number sequence. Parameters are the same as for 
# python builtin "range".
#   Memory  -- storage for 8 integers, regardless of parameters.
#   Compute -- at most 2*"maximum" steps required to generate sequence.
#
def random_range(start, stop=None, step=None):
    import random, math
    # Set a default values the same way "range" does.
    if (stop == None): start, stop = 0, start
    if (step == None): step = 1
    # Use a mapping to convert a standard range into the desired range.
    mapping = lambda i: (i*step) + start
    # Compute the number of numbers in this range.
    maximum = (stop - start) // step
    # Seed range with a random integer.
    value = random.randint(0,maximum)
    # 
    # Construct an offset, multiplier, and modulus for a linear
    # congruential generator. These generators are cyclic and
    # non-repeating when they maintain the properties:
    # 
    #   1) "modulus" and "offset" are relatively prime.
    #   2) ["multiplier" - 1] is divisible by all prime factors of "modulus".
    #   3) ["multiplier" - 1] is divisible by 4 if "modulus" is divisible by 4.
    # 
    offset = random.randint(0,maximum) * 2 + 1      # Pick a random odd-valued offset.
    multiplier = 4*(maximum//4) + 1                 # Pick a multiplier 1 greater than a multiple of 4.
    modulus = int(2**math.ceil(math.log2(maximum))) # Pick a modulus just big enough to generate all numbers (power of 2).
    # Track how many random numbers have been returned.
    found = 0
    while found < maximum:
        # If this is a valid value, yield it in generator fashion.
        if value < maximum:
            found += 1
            yield mapping(value)
        # Calculate the next value in the sequence.
        value = (value*multiplier + offset) % modulus

Utilisation

L'utilisation de cette fonction "random_range" est la même que pour tout générateur (comme "range"). Un exemple :

# Show off random range.
print()
for v in range(3,6):
    v = 2**v
    l = list(random_range(v))
    print("Need",v,"found",len(set(l)),"(min,max)",(min(l),max(l)))
    print("",l)
    print()

Résultats de l'échantillon

Required 8 cycles to generate a sequence of 8 values.
Need 8 found 8 (min,max) (0, 7)
 [1, 0, 7, 6, 5, 4, 3, 2]

Required 16 cycles to generate a sequence of 9 values.
Need 9 found 9 (min,max) (0, 8)
 [3, 5, 8, 7, 2, 6, 0, 1, 4]

Required 16 cycles to generate a sequence of 16 values.
Need 16 found 16 (min,max) (0, 15)
 [5, 14, 11, 8, 3, 2, 13, 1, 0, 6, 9, 4, 7, 12, 10, 15]

Required 32 cycles to generate a sequence of 17 values.
Need 17 found 17 (min,max) (0, 16)
 [12, 6, 16, 15, 10, 3, 14, 5, 11, 13, 0, 1, 4, 8, 7, 2, ...]

Required 32 cycles to generate a sequence of 32 values.
Need 32 found 32 (min,max) (0, 31)
 [19, 15, 1, 6, 10, 7, 0, 28, 23, 24, 31, 17, 22, 20, 9, ...]

Required 64 cycles to generate a sequence of 33 values.
Need 33 found 33 (min,max) (0, 32)
 [11, 13, 0, 8, 2, 9, 27, 6, 29, 16, 15, 10, 3, 14, 5, 24, ...]

Answer 5

La solution présentée dans cette réponse fonctionne, mais il pourrait devenir problématique avec la mémoire si la taille de l'échantillon est petite, mais que la population est énorme (par ex. random.sample(insanelyLargeNumber, 10) ).

Pour réparer ça, je ferais ceci :

answer = set()
sampleSize = 10
answerSize = 0

while answerSize < sampleSize:
    r = random.randint(0,100)
    if r not in answer:
        answerSize += 1
        answer.add(r)

# answer now contains 10 unique, random integers from 0.. 100