sacar posiciones obtener números numeros numero nombres generar datos como aleatorios aleatorio aleatorias python random numbers

obtener - generar posiciones aleatorias en python



Generando números aleatorios no repetitivos en Python (17)

¿Necesitas que sea criptográficamente seguro o simplemente difícil de adivinar? ¿Qué tan malo son las colisiones? Porque si necesita ser criptográficamente fuerte y tener cero colisiones, es, por desgracia, imposible.

Ok, esta es una de las preguntas más complicadas de lo que parece, así que estoy recurriendo al desbordamiento de la pila porque no puedo pensar en una buena respuesta. Esto es lo que quiero: necesito que Python genere una lista simple de números de 0 a 1,000,000,000 en orden aleatorio para ser utilizada para números de serie (usando un número aleatorio para que no pueda decir cuántos se han asignado o no ataca con la misma facilidad, es decir, adivinando cuál será el siguiente). Estos números se almacenan en una tabla de base de datos (indexada) junto con la información vinculada a ellos. El programa que los genera no se ejecuta para siempre, por lo que no puede depender del estado interno.

No es gran cosa, ¿verdad? Simplemente genere una lista de números, introdúzcalos en una matriz y use Python "random.shuffle (big_number_array)" y terminamos. El problema es que me gustaría evitar tener que almacenar una lista de números (y así leer el archivo, abrir uno, guardarlo y cerrarlo). Prefiero generarlos sobre la marcha. El problema es que las soluciones que puedo pensar tienen problemas:

1) Genere un número aleatorio y luego verifique si ya se utilizó. Si se ha usado, genere un nuevo número, revise, repita según sea necesario hasta que encuentre uno sin usar. El problema aquí es que puedo tener mala suerte y generar una gran cantidad de números usados ​​antes de obtener uno que no se usa. Posible solución: use un grupo de números muy grande para reducir las posibilidades de esto (pero luego termino con números largos tontos).

2) Genere un número aleatorio y luego verifique si ya se utilizó. Si se ha usado, sume o reste uno del número y vuelva a verificar, siga repitiendo hasta que marque un número no utilizado. El problema es que ya no es un número aleatorio ya que he introducido un sesgo (eventualmente obtendré grupos de números y usted podría predecir el próximo número con más posibilidades de éxito).

3) Genere un número aleatorio y luego verifique si ya se utilizó. Si se ha usado, sume o reste otro número aleatorio generado aleatoriamente y vuelva a verificar, el problema es que volvemos a simplemente generar números aleatorios y verificarlos como en la solución 1.

4) Chúpalo y genera la lista aleatoria y guárdala, haz que un daemon los ponga en una Cola para que haya números disponibles (y evita abrir y cerrar constantemente un archivo, llenándolo en lotes).

5) Genere números aleatorios mucho más grandes y los pise (es decir, use MD5) para obtener un valor numérico más pequeño, rara vez tendremos colisiones, pero termino con números más grandes que los necesarios nuevamente.

6) Anteponer o anexar información basada en el tiempo al número aleatorio (es decir, la marca de tiempo unix) para reducir las posibilidades de una colisión, de nuevo obtengo números más grandes que los que necesito.

Alguien tiene ideas inteligentes que reducirán las posibilidades de una "colisión" (es decir, generar un número aleatorio que ya se ha tomado) pero también me permitirán mantener el número "pequeño" (es decir, menos de mil millones (o mil millones para tus europeos =)).

Respuesta y por qué lo acepté:

Así que simplemente voy con 1, y espero que no sea un problema, sin embargo, si es así, voy a ir con la solución determinista de generar todos los números y almacenarlos para que haya una garantía de obtener un nuevo número aleatorio, y puedo use números "pequeños" (es decir, 9 dígitos en lugar de un MD5 / etc.).

Con algunos números aritméticos y primarios modulares, puede crear todos los números entre 0 y una gran prima, fuera de servicio. Si eliges tus números cuidadosamente, el siguiente número es difícil de adivinar.

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

Creo que estás sobreestimando los problemas con el enfoque 1). A menos que tenga requisitos de tiempo real, simplemente verificando por elección aleatoria termina bastante rápido. La probabilidad de necesitar más de una cantidad de iteraciones decae exponencialmente. Con 100M de números de salida (10% de factor de relleno), tendrá una probabilidad mil millones de requerir más de 9 iteraciones. Incluso con el 50% de los números tomados, en promedio necesitarás 2 iteraciones y tendrás una posibilidad en mil millones de requerir más de 30 cheques. O incluso el caso extremo en el que ya se tomaron el 99% de los números podría ser razonable: obtendrá un promedio de 100 iteraciones y tendrá un cambio de 1 en un millar de requiriendo 2.062 iteraciones

Empecé a tratar de escribir una explicación del enfoque utilizado a continuación, pero solo implementarlo fue más fácil y más preciso. Este enfoque tiene el extraño comportamiento de que se vuelve más rápido cuanto más números haya generado. Pero funciona, y no requiere que generes todos los números por adelantado.

Como una simple optimización, puede hacer fácilmente que esta clase use un algoritmo probabilístico (generar un número aleatorio, y si no está en el conjunto de números usados, agregarlo al conjunto y devolverlo) al principio, realizar un seguimiento de la tasa de colisión, y cambie al enfoque determinista que se usa aquí una vez que la tasa de colisiones empeora.

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]

Este es un problema claro, y lo he estado pensando por un tiempo (con soluciones similares a las de Sjoerd''s ), pero al final, esto es lo que pienso:

Usa tu punto 1) y deja de preocuparte.

Suponiendo aleatoriedad real, la probabilidad de que un número aleatorio ya haya sido elegido antes es la cuenta de los números elegidos previamente divididos por el tamaño de su conjunto, es decir, el número máximo.

Si dice que solo necesita mil millones de números, es decir, nueve dígitos: disfrute de 3 dígitos más, de modo que tenga números de serie de 12 dígitos (es decir, tres grupos de cuatro dígitos, agradables y legibles).

Incluso cuando está cerca de haber elegido mil millones de números previamente, la probabilidad de que su nuevo número ya esté tomado sigue siendo solo del 0,1%.

Haz el paso 1 y dibuja nuevamente. Todavía puede verificar si hay un bucle "infinito", es decir, no intente más de 1000 veces más o menos, y luego vuelva a agregar 1 (u otra cosa).

Ganarás la lotería antes de que esa reserva se use.

La secuencia de semilla del generador de números aleatorios congruencia lineal estándar NO PUEDE repetirse hasta que se haya generado el conjunto completo de números del valor inicial de la semilla. Entonces DEBE repetir con precisión.

La semilla interna a menudo es grande (48 o 64 bits). Los números generados son más pequeños (generalmente 32 bits) porque el conjunto completo de bits no es aleatorio. Si sigues los valores iniciales, formarán una secuencia distinta no repetitiva.

La pregunta es esencialmente la de encontrar una buena semilla que genere números "suficientes". Puedes elegir una semilla y generar números hasta que vuelvas a la semilla inicial. Esa es la longitud de la secuencia. Puede ser millones o miles de millones de números.

Hay algunas pautas en Knuth para elegir semillas adecuadas que generarán secuencias muy largas de números únicos.

Me encontré con el mismo problema y abrí una pregunta con un título diferente antes de llegar a esta. Mi solución es un generador de muestras aleatorias de índices (es decir, números no repetitivos) en el intervalo [0,maximal) , llamado itersample . Aquí hay algunos ejemplos de uso:

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

o

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

itersample genera enteros aleatorios no repetitivos, la necesidad de almacenamiento se limita a números seleccionados, y el tiempo necesario para elegir n números debe ser (como lo confirman algunas pruebas) O(n log(n)) , respeto de maximal .

Aquí está el código 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

Me replantearía el problema en sí ... No parece que estés haciendo nada secuencial con los números ... y tienes un índice en la columna que los tiene. ¿Realmente necesitan ser números ?

Considera un sha hash ... en realidad no necesitas todo el asunto. Haga lo que hacen los git u otros servicios de acortamiento de urls, y tome los primeros 3/4/5 caracteres del hash. Dado que cada personaje ahora tiene 36 valores posibles en lugar de 10, tiene 2,176,782,336 combinaciones en lugar de 999,999 combinaciones (para seis dígitos). Combine eso con una comprobación rápida de si existe la combinación (una consulta de índice pura) y una semilla como una marca de tiempo + número aleatorio y debería servir para casi cualquier situación.

Para generar una lista de números totalmente aleatorios dentro de un umbral definido, de la siguiente manera:

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

Puede ejecutar 1) sin tener que enfrentarse al problema de demasiados números aleatorios incorrectos si solo disminuye el intervalo aleatorio en uno cada vez.

Para que este método funcione, deberá guardar los números ya dados (que de todos modos desea hacer) y también guardar la cantidad de números tomados.

Es bastante obvio que, después de haber recolectado 10 números, su grupo de posibles números aleatorios habrá disminuido en 10. Por lo tanto, no debe elegir un número entre 1 y 1.000.000, pero entre 1 y 999.990. Por supuesto, este número no es el número real sino solo un índice (a menos que los 10 números recolectados hayan sido 999.991, 999.992, ...); Tendría que contar ahora desde 1 omitiendo todos los números ya recopilados.

Por supuesto, su algoritmo debería ser más inteligente que solo contar de 1 a 1.000.000, pero espero que entienda el método.

No me gusta dibujar números aleatorios hasta que obtenga uno que se ajuste a cualquiera de los dos. Simplemente se siente mal.

Puede usar el Cifrado de Preservación de Formato para encriptar un contador. Su contador simplemente va de 0 hacia arriba, y el cifrado utiliza una clave de su elección para convertirlo en un valor aparentemente aleatorio de cualquier raíz y ancho que desee.

Los cifrados de bloque normalmente tienen un tamaño de bloque fijo de, por ejemplo, 64 o 128 bits. Pero el Cifrado de Preservación de Formato le permite tomar un cifrado estándar como AES y hacer un cifrado de ancho más pequeño, de cualquier radix y ancho que desee (por ejemplo, radix 10, ancho 9 para los parámetros de la pregunta), con un algoritmo que todavía está criptográficamente robusto.

Se garantiza que nunca tendrá colisiones (porque los algoritmos criptográficos crean una asignación de 1: 1). También es reversible (un mapeo bidireccional), por lo que puede tomar el número resultante y volver al valor del contador con el que comenzó.

AES-FFX es un método estándar propuesto para lograr esto.

Experimenté con algunos códigos básicos de Python para AES-FFX. Ver el código de Python aquí (pero tenga en cuenta que no cumple totalmente con la especificación AES-FFX). Por ejemplo, puede encriptar un contador a un número decimal de 7 dígitos de aspecto aleatorio. P.ej:

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

Para otro ejemplo en Python, usando otro método que no sea AES-FFX (creo), vea esta publicación de blog "Cómo generar un número de cuenta" que hace FPE usando un cifrado de Feistel. Genera números de 0 a 2 ^ 32-1.

Si es suficiente para usted que un observador casual no pueda adivinar el siguiente valor, puede usar cosas como un generador congruente lineal o incluso un simple registro de desplazamiento de realimentación lineal para generar los valores y mantener el estado en la base de datos en caso de que necesite más valores Si usa estos derechos, los valores no se repetirán hasta el final del universo. Encontrará más ideas en la lista de generadores de números aleatorios .

Si crees que puede haber alguien que tenga un interés serio en adivinar los próximos valores, puedes usar una secuencia de base de datos para contar los valores que generas y encriptarlos con un algoritmo de encriptación u otra función perfecta criptográficamente fuerte. Sin embargo, debe tener cuidado de que el algoritmo de encriptación no se pueda romper fácilmente si se puede obtener una secuencia de números sucesivos generados: un simple RSA , por ejemplo, no lo hará debido al ataque de mensajes relacionados con Franklin-Reiter. .

Si no necesita algo criptográficamente seguro, sino simplemente "suficientemente ofuscado" ...

Campos de Galois

Puede probar las operaciones en Galois Fields , por ejemplo, GF (2) 32 , para asignar un contador de aumento simple x a un número de serie aparentemente aleatorio y :

x = counter_value y = some_galois_function(x)

  • Multiplicar por una constante
    • Inverso es multiplicar por el recíproco de la constante
  • Elevar a una potencia : x n
  • Recíproco x -1
    • Caso especial de elevar al poder n
    • Es su propio inverso
  • Exponenciación de un elemento primitivo: a x
    • Tenga en cuenta que esto no tiene un inverso fácil de calcular (logaritmo discreto)
    • Asegúrese de que a es un elemento primitivo , también conocido como generator

Muchas de estas operaciones tienen una inversa, lo que significa que, dado su número de serie, puede calcular el valor del contador original del que se deriva.

En cuanto a encontrar una biblioteca para Galois Field para Python ... buena pregunta. Si no necesita velocidad (lo que no haría por esto), entonces podría hacer la suya. No he probado estos:

La multiplicación de matriz en GF (2)

Elija una matriz invertible adecuada de 32 × 32 en GF (2) y multiplique un contador de entrada de 32 bits. Esto está conceptualmente relacionado con LFSR, como se describe en la respuesta de S.Lott .

CRC

Una posibilidad relacionada es usar un cálculo de CRC . Basado en el resto de división larga con un polinomio irreductible en GF (2). El código de Python está disponible para los CRC ( crcmod , pycrc ), aunque es posible que desee elegir un polinomio irreducible diferente al que normalmente se usa para sus propósitos. Estoy un poco confuso con la teoría, pero creo que un CRC de 32 bits debería generar un valor único para cada combinación posible de entradas de 4 bytes. Mira esto. Es bastante fácil verificarlo experimentalmente, al volver a introducir la salida en la entrada y verificar que produzca un ciclo completo de longitud 2 32 -1 (cero solo asigna a cero). Es posible que deba deshacerse de cualquier XOR inicial / final en el algoritmo CRC para que funcione esta comprobación.

Si no tienen que ser aleatorios, sino simplemente no obviamente lineales (1, 2, 3, 4, ...), aquí hay un algoritmo simple:

Elige dos números primos. Uno de ellos será el número más grande que pueda generar, por lo que debería ser de alrededor de mil millones. El otro debe ser bastante grande.

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

Solo almacene la serie anterior cada vez para que sepa dónde la dejó. No puedo probar matemáticamente que esto funciona (ha pasado demasiado tiempo desde esas clases particulares), pero es demostrablemente correcto con números primos más pequeños:

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)

También podría probarlo empíricamente con números primos de 9 dígitos, simplemente requeriría un poco más de trabajo (o mucha más memoria).

Esto significa que, dados algunos números de serie, sería posible determinar cuáles son tus valores, pero con solo nueve dígitos, no es probable que estés buscando números indescifrables.

Usted está declarando que almacena los números en una base de datos.

¿No sería más fácil almacenar todos los números allí, y pedir a la base de datos un número aleatorio no utilizado? La mayoría de las bases de datos admiten tal solicitud.

Ejemplos

MySQL:

SELECT column FROM table ORDER BY RAND() LIMIT 1

PostgreSQL:

SELECT column FROM table ORDER BY RANDOM() LIMIT 1