¿Cómo creo una lista de números aleatorios sin duplicados?

Intenté usar random.randint(0, 100) , pero algunos números eran iguales. ¿Existe un método / módulo para crear una lista de números aleatorios únicos?

 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); 

Related of "¿Cómo creo una lista de números aleatorios sin duplicados?"

Esto devolverá una lista de 10 números seleccionados del rango de 0 a 99, sin duplicados.

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

Con referencia a su ejemplo de código específico, probablemente quiera leer todas las líneas del archivo una vez y luego seleccionar líneas aleatorias de la lista guardada en la memoria. Por ejemplo:

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

De esta manera, solo necesita leer el archivo una vez, antes de su bucle. Es mucho más eficiente hacer esto que buscar de nuevo al inicio del archivo y llamar a f1.readlines() nuevamente para cada iteración de bucle.

Primero puede crear una lista de números de a a b , donde a y b son respectivamente los números más pequeños y más grandes de su lista, luego mezclarlos con el algoritmo de Fisher-Yates o usando el método random.shuffle de Python.

Puedes usar la función aleatoria del módulo aleatorio de esta manera:

 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 

Tenga en cuenta que el método de reproducción aleatoria no devuelve ninguna lista como se puede esperar, solo se baraja la lista aprobada por referencia.

La solución presentada en esta respuesta funciona, pero podría ser problemática con la memoria si el tamaño de la muestra es pequeño, pero la población es enorme (por ejemplo, random.sample(insanelyLargeNumber, 10) ).

Para arreglar eso, me gustaría ir con esto:

 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 

Entonces, me doy cuenta de que esta publicación tiene 6 años, pero hay otra respuesta con (generalmente) mejor rendimiento algorítmico, aunque menos práctico con mayor sobrecarga.

Otras respuestas incluyen el método aleatorio y el método ‘probar hasta que sea válido’ usando conjuntos.

Si elegimos al azar K enteros sin reemplazo del intervalo 0 … N-1, entonces el método de reproducción aleatoria utiliza almacenamiento O (N) y operaciones O (N), lo cual es molesto si elegimos K pequeño de N grande . El método establecido solo usa el almacenamiento O (K), pero tiene el peor caso O (inf) O (n * log (n)) esperado para K cerca de N. (Imagine que intenta obtener el último número de dos respuestas permitidas al azar) , habiendo seleccionado ya 999998, para k = n-1 = 10 ^ 6).

Así que el método de ajuste está bien para K ~ 1, y el método de reproducción aleatoria está bien para K ~ N. Ambos usan llamadas esperadas> K RNG.

De otra manera; puede fingir que realiza la selección aleatoria de Fisher-Yates, y por cada nueva selección aleatoria, realice una operación de búsqueda binaria en sus elementos ya seleccionados para encontrar el valor que obtendría si realmente almacenara una matriz de todos los elementos que no tiene Aún no elegido.

Si sus valores ya seleccionados son [2,4], y su generador de números aleatorios escupe 2 en el intervalo (N – num_already_selected), entonces pretende hacer una selección de entre [0,1,3,5,6, .. .] contando los valores menos que la respuesta que ya ha sido seleccionada. En este caso, su tercer valor seleccionado sería 3. Luego, en el siguiente paso, si su número aleatorio fuera 2 nuevamente , se asignaría a 5 (en la lista de simulación [0,1,5,6]), porque (Índice de potencial de 5 en la lista ordenada de valores ya seleccionados [2,3,4], que es 3) + 2 = 5.

Almacene los valores ya seleccionados en un árbol de búsqueda binaria equilibrada, almacene el rango (número de valores menos que ese valor) en cada nodo, seleccione un número aleatorio R del rango (0 … n- (número ya elegido) ). Luego descienda el árbol como si estuviera buscando, pero su valor de búsqueda es R más el rango de cualquier nodo en el que esté. Cuando llegue a un nodo hoja, agregue el número aleatorio al rango de ese nodo e inserte la sum en el árbol binario balanceado.

Una vez que tenga K elementos, léalos del árbol en una matriz y mezcle (si el orden es importante).

Esto requiere almacenamiento O (K), rendimiento O (K * log (K)) y exactamente K randint.

Ejemplo de implementación de muestreo aleatorio (ordenamiento final no aleatorio, pero puede O (K) barajar después), O (k) almacenamiento y O (k log ^ 2 (k)) rendimiento (no O (k log (k)) porque no podemos descender de forma personalizada árboles binarios equilibrados para esta implementación):

 from sortedcontainers import SortedList def sample(n, k): ''' Return random k-length-subset of integers from 0 to n-1. Uses only O(k) storage. Bounded k*log^2(k) worst case. K RNG calls. ''' ret = SortedList() for i in range(k): to_insert = random.randint(0, n-1 - len(ret)) to_insert = binsearch_adding_rank(ret, to_insert) ret.add(to_insert) return ret def binsearch_adding_rank(A, v): l, u = 0, len(A)-1 m=0 while l <= u: m = l+(ul)//2 if v + m >= A[m]: l = m+1 m+=1 # We're binary searching for partitions, so if the last step was to the right then add one to account for offset because that's where our insert would be. elif v+m < A[m]: u = m-1 return v+m 

Y para demostrar validez:

Si estuviéramos haciendo el shuffle de fisher-yates, habiendo elegido ya [1,4,6,7,8,9,15,16], con el número aleatorio 5, nuestra matriz aún por ser elegida se vería como [0 , 2,3,5,10,11,12, ...], entonces el elemento 5 es 11. Por lo tanto, nuestra función de búsqueda de bins debería devolver 11, dado 5 y [1,4,6,7,8,9,15 ,dieciséis]:

 assert binsearch_adding_rank([1,4,6,7,8,9,15,16], 5) == 11 

El inverso de [1,2,3] es [0,4,5,6,7,8, ...], el quinto elemento de los cuales es 8, por lo que:

 assert binsearch_adding_rank([1,2,3], 5) == 8 

Inverso de [2,3,5] es [0,1,4,6, ...], el primer elemento de los cuales es (todavía) 1, por lo que:

 assert binsearch_adding_rank([2,3,5], 1) == 1 

Inverso es [0,6,7,8, ...], 3er elemento es 8, y:

 assert binsearch_adding_rank([1,2,3,4,5,10], 3) == 8 

Y para probar la función general:

 # Edge cases: assert sample(50, 0) == [] assert sample(50, 50) == list(range(0,50)) # Variance should be small and equal among possible values: x = [0]*10 for i in range(10_000): for v in sample(10, 5): x[v] += 1 for v in x: assert abs(5_000 - v) < 250, v del x # Check for duplication: y = sample(1500, 1000) assert len(frozenset(y)) == len(y) del y 

Sin embargo, en la práctica, utilice el método de orden aleatorio para K ~> N / 2 y el método establecido para K ~

Edición: ¡Aquí hay otra forma de hacerlo usando la recursión! O (k * log (n)) Creo.

 def divide_and_conquer_sample(n, k, l=0): u = n-1 # Base cases: if k == 0: return [] elif k == nl: return list(range(l, n)) elif k == 1: return [random.randint(l, u)] # Compute how many left and how many right: m = l + (ul)//2 k_right = 0 k_left = 0 for i in range(k): # Base probability: (# of available values in right interval) / (total available values) if random.random() <= (nm - k_right)/(nl-k_right-k_left): k_right += 1 else: k_left += 1 # Recur return divide_and_conquer_sample(n, k_right, m) + divide_and_conquer_sample(m, k_left, l) 

Si necesita muestrear números extremadamente grandes, no puede usar el range

 random.sample(range(10000000000000000000000000000000), 10) 

porque arroja:

 OverflowError: Python int too large to convert to C ssize_t 

Además, si random.sample no puede producir el número de elementos que desea debido a que el rango es demasiado pequeño

  random.sample(range(2), 1000) 

arroja:

  ValueError: Sample larger than population 

Esta función resuelve ambos problemas:

 import random def random_sample(count, start, stop, step=1): def gen_random(): while True: yield random.randrange(start, stop, step) def gen_n_unique(source, n): seen = set() seenadd = seen.add for i in (i for i in source() if i not in seen and not seenadd(i)): yield i if len(seen) == n: break return [i for i in gen_n_unique(gen_random, min(count, int(abs(stop - start) / abs(step))))] 

Uso con números extremadamente grandes:

 print('\n'.join(map(str, random_sample(10, 2, 10000000000000000000000000000000)))) 

Resultado de la muestra:

 7822019936001013053229712669368 6289033704329783896566642145909 2473484300603494430244265004275 5842266362922067540967510912174 6775107889200427514968714189847 9674137095837778645652621150351 9969632214348349234653730196586 1397846105816635294077965449171 3911263633583030536971422042360 9864578596169364050929858013943 

Uso donde el rango es menor que el número de elementos solicitados:

 print(', '.join(map(str, random_sample(100000, 0, 3)))) 

Resultado de la muestra:

 2, 0, 1 

También funciona con rangos y pasos negativos:

 print(', '.join(map(str, random_sample(10, 10, -10, -2)))) print(', '.join(map(str, random_sample(10, 5, -5, -2)))) 

Resultados de la muestra:

 2, -8, 6, -2, -4, 0, 4, 10, -6, 8 -3, 1, 5, -1, 3 

Si la lista de N números del 1 al N se genera aleatoriamente, entonces sí, existe la posibilidad de que algunos números se repitan.

Si desea una lista de números del 1 al N en un orden aleatorio, complete una matriz con números enteros del 1 al N, y luego use un shuffle de Fisher-Yates o random.shuffle() de Python random.shuffle() .

Generador de números pseudoaleatorios congruentes lineales

O (1) Memoria

O (k) Operaciones

Este problema se puede resolver con un simple generador lineal congruente . Esto requiere una sobrecarga de memoria constante (8 enteros) y, como máximo, cálculos de 2 * (longitud de secuencia).

¡Todas las demás soluciones usan más memoria y más cómputo! Si solo necesitas unas pocas secuencias aleatorias, este método será significativamente más barato. Para rangos de tamaño N , si desea generar en el orden de N secuencias k únicas o más, recomiendo la solución aceptada utilizando los métodos incorporados random.sample(range(N),k) ya que se ha optimizado en python por velocidad.

Código

 # 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 

Uso

El uso de esta función "random_range" es el mismo que para cualquier generador (como "range"). Un ejemplo:

 # 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() 

Resultados de la muestra

 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, ...] 

Si desea asegurarse de que los números que se agregan son únicos, puede usar un objeto Establecer

Si usa 2.7 o más, o importe el módulo de conjuntos si no.

Como otros han mencionado, esto significa que los números no son verdaderamente aleatorios.

Puede usar la biblioteca Numpy para una respuesta rápida como se muestra a continuación:

El fragmento de código dado muestra 6 números únicos entre el rango de 0 a 5. Puede ajustar los parámetros para su comodidad.

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

Salida

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

No pone ninguna restricción como vemos en random.sample como se menciona aquí .

Espero que esto ayude un poco.

Una función muy simple que también resuelve tu problema.

 from random import randint data = [] def unique_rand(inicial, limit, total): data = [] i = 0 while i < total: number = randint(inicial, limit) if number not in data: data.append(number) i += 1 return data data = unique_rand(1, 60, 6) print(data) """ prints something like [34, 45, 2, 36, 25, 32] """ 

La respuesta que se proporciona aquí funciona muy bien con respecto al tiempo y la memoria, pero es un poco más complicada, ya que utiliza construcciones avanzadas de python, como el rendimiento. La respuesta más simple funciona bien en la práctica, pero el problema con esa respuesta es que puede generar muchos enteros falsos antes de construir el conjunto requerido. Pruébelo con populationSize = 1000, sampleSize = 999. En teoría, existe la posibilidad de que no termine.

La respuesta a continuación aborda ambos problemas, ya que es determinista y algo eficiente, aunque actualmente no es tan eficiente como los otros dos.

 def randomSample(populationSize, sampleSize): populationStr = str(populationSize) dTree, samples = {}, [] for i in range(sampleSize): val, dTree = getElem(populationStr, dTree, '') samples.append(int(val)) return samples, dTree 

donde las funciones getElem, percolateUp son como se definen a continuación

 import random def getElem(populationStr, dTree, key): msd = int(populationStr[0]) if not key in dTree.keys(): dTree[key] = range(msd + 1) idx = random.randint(0, len(dTree[key]) - 1) key = key + str(dTree[key][idx]) if len(populationStr) == 1: dTree[key[:-1]].pop(idx) return key, (percolateUp(dTree, key[:-1])) newPopulation = populationStr[1:] if int(key[-1]) != msd: newPopulation = str(10**(len(newPopulation)) - 1) return getElem(newPopulation, dTree, key) def percolateUp(dTree, key): while (dTree[key] == []): dTree[key[:-1]].remove( int(key[-1]) ) key = key[:-1] return dTree 

Finalmente, el tiempo promedio fue de unos 15 ms para un gran valor de n, como se muestra a continuación,

 In [3]: n = 10000000000000000000000000000000 In [4]: %time l,t = randomSample(n, 5) Wall time: 15 ms In [5]: l Out[5]: [10000000000000000000000000000000L, 5731058186417515132221063394952L, 85813091721736310254927217189L, 6349042316505875821781301073204L, 2356846126709988590164624736328L] 

El problema con los enfoques basados ​​en conjuntos (“si hay valores aleatorios en valores de retorno, inténtelo de nuevo”) es que su tiempo de ejecución no está determinado debido a colisiones (que requieren otra iteración de “intentar nuevamente”), especialmente cuando se devuelve una gran cantidad de valores aleatorios de la gama.

Una alternativa que no es propensa a este tiempo de ejecución no determinista es la siguiente:

 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] 
 import random result=[] for i in range(1,50): rng=random.randint(1,20) result.append(rng) 

Desde el CLI en win xp:

 python -c "import random; print(sorted(set([random.randint(6,49) for i in range(7)]))[:6])" 

En Canadá tenemos el 6/49 Lotto. Simplemente envuelvo el código anterior en lotto.bat y ejecuto C:\home\lotto.bat o simplemente C:\home\lotto .

Debido a que random.randint menudo repite un número, uso set con range(7) y luego lo acorto a una longitud de 6.

Ocasionalmente, si un número se repite más de 2 veces, la longitud de la lista resultante será menor que 6.

EDITAR: Sin embargo, random.sample(range(6,49),6) es la forma correcta de hacerlo.