Me gustaría generar única de números aleatorios entre 0 y 1000 que nunca se repita (es decir, 6 no se presenta dos veces), pero eso no recurrir a algo así como un O(N) en la búsqueda de los valores anteriores para hacerlo. Es esto posible?

InformationsquelleAutor dicroce | 2008-10-12

21 Comentarios

  1. 238

    Inicializar una matriz de 1001 enteros con los valores de 0-1000 y establecer una variable, máximo, la corriente máxima índice de la matriz (a partir de 1000). Elegir un número aleatorio r entre 0 y max, cambie el número en la posición r con el número en la posición max y devolver el número ahora en la posición max. Decremento max 1 y continuar. Cuando max es 0, establecer max de vuelta para el tamaño de la matriz a – 1 y empezar de nuevo sin la necesidad de reinicializar la matriz.

    Actualización:
    Aunque me encontré con este método en mi propia cuando respondió a la pregunta, después de investigar un poco me doy cuenta de que esta es una versión modificada de Fisher-Yates conocido como Durstenfeld-Fisher-Yates o Knuth-Fisher-Yates. Desde la descripción puede ser un poco difícil de seguir, me han proporcionado un ejemplo a continuación (con 11 elementos en lugar de 1001):

    Matriz comienza con 11 elementos inicializa la matriz[n] = n, max comienza a las 10:

    +--+--+--+--+--+--+--+--+--+--+--+
    | 0| 1| 2| 3| 4| 5| 6| 7| 8| 9|10|
    +--+--+--+--+--+--+--+--+--+--+--+
                                    ^
                                   max    
    

    En cada iteración, un número aleatorio r se selecciona entre el 0 y el máximo, de la matriz[r] y la matriz[max] se intercambian, la nueva matriz[max] se devuelve, y max se decrementa:

    max = 10, r = 3
               +--------------------+
               v                    v
    +--+--+--+--+--+--+--+--+--+--+--+
    | 0| 1| 2|10| 4| 5| 6| 7| 8| 9| 3|
    +--+--+--+--+--+--+--+--+--+--+--+
    
    max = 9, r = 7
                           +-----+
                           v     v
    +--+--+--+--+--+--+--+--+--+--+--+
    | 0| 1| 2|10| 4| 5| 6| 9| 8| 7: 3|
    +--+--+--+--+--+--+--+--+--+--+--+
    
    max = 8, r = 1
         +--------------------+
         v                    v
    +--+--+--+--+--+--+--+--+--+--+--+
    | 0| 8| 2|10| 4| 5| 6| 9| 1: 7| 3|
    +--+--+--+--+--+--+--+--+--+--+--+
    
    max = 7, r = 5
                     +-----+
                     v     v
    +--+--+--+--+--+--+--+--+--+--+--+
    | 0| 8| 2|10| 4| 9| 6| 5: 1| 7| 3|
    +--+--+--+--+--+--+--+--+--+--+--+
    
    ...
    

    Después del 11 de iteraciones, todos los números en la matriz han sido seleccionadas, max == 0, y los elementos de la matriz son revueltos:

    +--+--+--+--+--+--+--+--+--+--+--+
    | 4|10| 8| 6| 2| 0| 9| 5| 1| 7| 3|
    +--+--+--+--+--+--+--+--+--+--+--+
    

    En este punto, max se pueden restablecer a 10 y el proceso puede continuar.

    • Si la matriz no empieza revueltos (y no con el algoritmo ingenuo; ver a Jeff post en arrastrando los pies), no esta de introducir un sesgo sutil?
    • Hay sesgo. Esto es sólo una extensión de salida de la versión de un mismo algoritmo.
    • Jeff post en arrastrando los pies sugiere que esto no volverá buenos números aleatorios.. codinghorror.com/blog/archives/001015.html
    • Rounce: yo creo que no; esto a mí me parece que el Pescador algoritmo de Yates, también citado en de Jeff post (como el chico bueno).
    • Lo Siento, Knuth-Fisher-Yates
    • Perl6/Parrot tendrá perezoso listas, que sólo va a mantener un seguimiento de los elementos modificados. Lo que significa que no tendrá el golpe inicial que otros sistemas tendrían.
    • No estoy realmente seguro de lo que está hablando. Lo «golpe inicial» se refiere y cómo se Perl6/Parrot evitar que exactamente?
    • El algoritmo que describe tiene O(n log n) tiempo para generar la lista o O(log n) amortizado en el tiempo por elemento.
    • ¿Cómo se puede llegar con eso?
    • Porque se está generando un (lg n) bits número aleatorio para cada número de la lista, y esto se lleva a Omega(log n) tiempo.
    • Creo que su lógica es defectuosa, se puede tomar O(n) tiempo para generar la lista original de los números si usted no tiene ya esta configurado pero toma O(1) tiempo para generar cada número de la lista que es la que se está preguntando.
    • Este método no genera la lista en O(n), se toma O(n log n). No me puedo imaginar que la solicitud significaba que nos permite infinito tiempo de pre-procesado, porque en ese caso cualquier método funciona, solo haz lo que necesites hacer, luego de generar cada elemento y almacenar en una tabla. Para mí es claro que el tiempo debe incluir el costo inicial, que es log n por elemento. (En realidad, el algoritmo puede ser modificado para generar cada elemento en O(log n) tiempo en lugar de O(log n) amortizado en el tiempo).
    • La lista inicial toma O(n) tiempo para inicializar (tarda el doble de tiempo para inicializar 2 enteros del mismo tamaño como inicializar una de esas entero). El tiempo que la generación de números aleatorios depende de la aplicación. Una vez que tenga el número aleatorio toma constante de tiempo para ejecutar el algoritmo que he presentado. El OP pidió algo «que no recurre a algo así como un O(N) en la búsqueda de los valores anteriores para hacerlo», que indica que el O(1) parte de la selección. Ya que este es el aceptado la respuesta, creo que se reunió con el OP requisitos.
    • El método requiere de Theta(n log n) bits aleatorios: en realidad, precisamente lg n! bits. Está usted diciendo que usted puede generar Theta(n log n) bits en tiempo O(n)?
    • la demanda es lo que puse en mi respuesta. Lea la pregunta y mi respuesta, si usted siente que tiene una mejor respuesta que más que libre de publicar.
    • Yo sólo quería señalar que no produce, como en el nombre de la pregunta, «única de números aleatorios en O(1)».
    • Justo lo suficiente, aunque nadie dijo que lo hizo y la cuestión se profundiza bastante bien en lo que se deseaba que se debe evitar la confusión aunque supongo que el título puede ser actualizado para reflejar mejor la cuestión que realmente se le preguntó y respondió.
    • Yep. (En honor a la verdad, yo no reclamo que nadie afirmaron que esto era O(1) – me acaba de señalar la complejidad, ya que no se había mencionado hasta que punto).
    • suponiendo que usted está tratando con tamaño fijo equipo de 32 bits enteros (que es una suposición razonable dada la pregunta y escalas de números enteros discutido) sólo es necesario en la mayoría de los 32 bits aleatorios por ejemplo. La generación que es una operación O(1) de la operación, por lo tanto, este debe ser considerado como una operación O(1) algoritmo para la práctica (en oposición a teórico) a los efectos.
    • De acuerdo, aunque técnicamente si usted está usando fija el tamaño de los números enteros el conjunto de la lista pueden ser generados en O(1) (con una gran constante, viz. 2^32). También, para fines prácticos, la definición de «random» es importante-si usted realmente desea utilizar su sistema de entropía, el límite es el cálculo de los bits aleatorios en lugar de los cálculos de sí mismos, y en ese caso n log n es relevante otra vez. Pero en el caso probable de que usted va a utilizar (el equivalente a) /dev/urandom en lugar de /dev/random, estás de vuelta en el ‘prácticamente’ O(n).
    • Estoy un poco confundido, no el hecho de que usted tiene que realizar N iteraciones (11 en este ejemplo) para obtener el resultado deseado cada vez que quiere decir que O(n)? Como usted necesita para hacer N iteraciones para obtener N! combinaciones desde el mismo estado inicial, de lo contrario su salida sólo será uno de los N estados.
    • Claramente, este es el Juego-Durstenfeld-Fisher-Yates algoritmo 🙂
    • Es completamente innecesario para realizar todos los «11 iteraciones» antes de empezar de nuevo. Así, el método es estrictamente inferior a la de Fisher-Yates con ninguna ganancia. Sólo una cosa, Jeff advertido en su blog como señaló el pro.

  2. 72

    Usted puede hacer esto:

    1. Crear una lista, 0..1000.
    2. Shuffle en la lista. (Ver Fisher-Yates shuffle una buena manera de hacer esto).
    3. Retorno de los números en el orden de la baraja lista.

    Así que esto no requiere de una búsqueda de los viejos valores de cada tiempo, pero todavía se requiere O(N) para la inicial aleatoria. Pero como Nils se señaló en los comentarios, este es amortizado O(1).

    • No estoy de acuerdo que es amortizado. El total del algoritmo es O(N) porque el revolver. Supongo que se podría decir que es O(.001N) porque cada valor sólo consume 1/1000 de un O(N) shuffle, pero que sigue siendo O(N) (aunque con un pequeño coeficiente).
    • Algunos Hombre N = 1000, por lo que usted está diciendo que es O(N/N), que es O(1)
    • Si cada insertar en la baraja de la matriz es una operación, a continuación, después de insertar el valor 1, usted puede obtener 1 valor aleatorio. 2 para valores de 2, y así sucesivamente, n para n valores. Toma n operaciones para generar la lista, de modo que todo algoritmo es O(n). Si usted necesita 1.000.000 de valores aleatorios, que se llevará a 1.000.000 de ops
    • Piense en ello de esta manera, si fue una constante de tiempo, tomaría la misma cantidad de tiempo para 10 números aleatorios de 10 mil millones de dólares. Pero debido a la mezcla de tomar O(n), sabemos que esto no es cierto.
    • Cualquier método que requiere que usted para inicializar una matriz de tamaño N con valores va a tener un O(N) inicialización de los costos; al mover el shuffle al iniciar o hacer una repetición de la reproducción aleatoria por la petición no hace ninguna diferencia.
    • «Es O(1)… N veces!»
    • Esta realidad lleva a amortizar en tiempo O(log n), ya que se necesita para generar n lg n de bits aleatorios.
    • He estado tentado de años para enmendar @AdamRosenfield edición de decir «amortizado» en lugar de «amortizado», pero no puedo decidirme a hacer una pequeña edición con ningún otro cambio, especialmente ya que la edición es de 5 años de edad. Aún así, yo al menos debería de estado para el registro.
    • Y ahora, tengo toda la justificación para hacerlo! meta.stackoverflow.com/q/252503/13

  3. 58

    Utilizar un Máxima Linear Feedback Shift Register.

    Es implementable en un par de líneas de C y en tiempo de ejecución hace poco más de un par de pruebas/ramas, un poco de suma y desplazamiento bit a bit. No es azar, sino que engaña a la mayoría de la gente.

    • «No es al azar, sino que engaña a la mayoría de la gente». Que se aplica a todos los pseudo-generadores de números aleatorios y todos los posibles respuestas a esta pregunta. Pero la mayoría de la gente no piensa acerca de ello. De modo que la omisión de esta nota, podría resultar en más upvotes…
    • +1 para usar sólo O(1) de la memoria.
    • Por qué fingir cuando usted puede hacerlo correctamente?
    • O(1) la memoria es el por qué.
    • Para guardar 4KB de RAM? Para este problema en particular, no veo ninguna razón para fingir. Otros problemas tal vez.
    • Nit: es O(log N) de la memoria.
    • Con ese método, ¿cómo generar números digamos entre 0 y 800000 ? Algunos podrían utilizar un LFSR plazo en el que se 1048575 (2^20 – 1) y obtener la siguiente si el número está fuera de rango, pero esto no será eficiente.
    • Como un LFSR, este no produce uniformemente distribuida secuencias: toda la secuencia que se genera es definido por el primer elemento.

  4. 20

    Usted podría utilizar Un Lineal Congruential Generador. Donde m (el módulo), que sería el más cercano prime mayor que 1000. Cuando usted obtiene un número fuera de rango, acaba de obtener la siguiente. La secuencia solo se repiten una vez para todos los elementos que se han producido, y usted no tiene que usar una tabla. Ser conscientes de las desventajas de este generador, aunque (como la falta de aleatoriedad).

    • 1009 es el primer presidente después de 1000.
    • Un LCG tiene una alta correlación entre números consecutivos, por lo tanto combinaciones de no va a ser muy aleatoria en general (por ejemplo, números de más de k aparte de la secuencia puede no ocurrir nunca juntos).
    • m debe ser el número de elementos 1001 (1000 + 1 por cero) y usted puede hacer uso de Next = (1002 * Corriente + 757) mod 1001;
  5. 17

    Usted podría utilizar Formato De Preservación De Cifrado para cifrar un contador. El contador se va de 0 hacia arriba, y el cifrado que utiliza una clave de su elección para convertirlo en un aparentemente al azar el valor de cualquier base y el ancho que desee. E. g. para el ejemplo en esta pregunta: radix 10, anchura 3.

    Los cifrados en bloque normalmente tienen un tamaño de bloque fijo de, por ejemplo, de 64 o 128 bits. Pero el Formato de la Preservación de Cifrado permite adoptar un estándar de cifrado como AES y hacer una pequeña anchura de cifrado, sea de la base y el ancho que desee, con un algoritmo que es todavía criptografía robusta.

    Que está garantizado que nunca han colisiones (debido a que los algoritmos criptográficos crear una asignación 1:1). También es reversible (2-forma de asignación), así que usted puede tomar el número resultante y recuperar el valor de un contador con el que comenzó.

    Esta técnica no necesita de la memoria para almacenar un barajan matriz etc, que puede ser una ventaja en los sistemas con memoria limitada.

    AES-FFX es un estándar propuesto por el método para lograr esto. He probado con algunos básicos de Python de código que se basa en el AES-FFX idea, aunque no es completamente compatible–ver el código de Python aquí. Se puede por ejemplo, cifrar un contador al azar a una de aspecto 7-dígitos de número decimal, o un número de 16 bits. Aquí es un ejemplo de base 10, ancho 3 (para dar un número entre 0 y 999 inclusive) como la pregunta declaró:

    000   733
    001   374
    002   882
    003   684
    004   593
    005   578
    006   233
    007   811
    008   072
    009   337
    010   119
    011   103
    012   797
    013   257
    014   932
    015   433
    ...   ...
    

    Para obtener diferentes que no se repiten pseudo-aleatorio de secuencias, cambiar la clave de cifrado. Cada clave de cifrado se produce una diferente y no repetir secuencia pseudo-aleatoria.

    • Esto es esencialmente una correlación simple, por lo tanto no se diferencia de la LCG y LFSR, con todos los kinks (por ejemplo, valores de más de k aparte de la secuencia puede no ocurrir nunca juntos).
    • Estoy teniendo dificultades para entender el sentido de tu comentario. Puede usted explicar lo que está mal con esta asignación, ¿qué son «todos los kinks», y lo que es k?
    • Todos los «cifrado» efectivamente hace aquí es reemplazar la secuencia 1,2,...,N con una secuencia de los mismos números en algunos otros, pero siendo constante, el orden. Los números se extraen de esta secuencia, uno por uno. k es el número de valores recogidos (el OP no especificar una carta para él, así que me tenía que presentar a uno).
    • Ya que la secuencia es constante y cada número es único, la combinación devuelto está totalmente definido por el primer número. Por lo tanto no es completamente aleatorio sólo un pequeño subconjunto de las posibles combinaciones que se pueden generar.
    • LFSRs y LCGs tienen la misma propiedad, por lo que sus otros defectos relacionados con la también aplicar.
    • Lo que yo veo. Sin embargo, en el caso del formato de la preservación de la codificación, usted puede obtener un diferente «al azar» de la secuencia para cada clave de cifrado. Con una de 128 bits o 256 bits de la clave, que le da un montón de secuencias posibles. Para cualquier tecla elegida, la que genera la secuencia está garantizado a ser el conjunto completo de números de manera efectiva revueltos.
    • Con respecto a los «valores de más de k aparte» consideración — usted sólo tiene que elegir una adecuada base r y ancho w para adaptarse a sus necesidades para conseguir k = rʷ, y luego generar el mayor número de n valores como quieras, donde n ≤ k. Por ejemplo, en mi respuesta me mostró cómo obtener 16 de no-repetición de números en el rango de 0..999.
    • Por supuesto, las deficiencias de una constante de la secuencia de PRNG (fuerte correlación entre los resultados) sólo se manifiestan cuando se utiliza la misma configuración que más de una vez. Si se utiliza una vez y nunca más, es al azar de acuerdo. Pero la generación de una nueva instalación de cada vez (al azar, con un mejor RNG!) bastante derrotas el propósito de la construcción de la propia PRNG.
    • Eso es porque la «clave» aproximadamente igual a la misma cantidad de «buena» números aleatorios (debe tener N! valores posibles para cubrir todas las posibles secuencias), además de todo el trabajo extra.
    • No es el caso que FPE debe implementar un determinado asignación estática, o que «la combinación devuelto está totalmente definido por el primer número de». Desde el parámetro de configuración es mucho más grande que el tamaño de la primera serie (que tiene sólo mil miembros), debe haber varias secuencias que comienzan con el mismo valor inicial y, a continuación, proceder a diferentes posterior valores. Realista generador va a fallar a cubrir todo el espacio posible de permutaciones; no vale la pena criar a ese modo de fallo cuando el OP no la pida.
    • +1. Cuando se implementa correctamente, utilizando un seguro de bloque de cifrado con una clave elegida uniformemente al azar, las secuencias generadas con este método se computacionalmente indistinguible de un verdadero aleatoria shuffle. Es decir, no hay manera de distinguir los resultados de este método de una verdadera aleatoria shuffle significativamente más rápido que por probar todas las posibles claves de cifrado de bloque y ver si alguno de ellos genera el mismo resultado. Para un sistema de cifrado con una de 128 bits keyspace, este es, probablemente, más allá de la potencia de cálculo disponible actualmente a la humanidad; con claves de 256 bits, es probable que sea siempre así.
    • Aún así, la respuesta es incompleta sin especificar que se necesita una nueva clave aleatoria para cada permutación, algunos puntos de su longitud requerida y el «doesn no generar todas las permutaciones posibles, pero indistinguibles» el habla.
    • Tal vez este no es exactamente la persona que pregunta quiere, pero es lo que estoy buscando 😉

  6. 7

    Para números bajos como 0…1000, la creación de una lista que contiene todos los números y arrastrando los pies es directa. Pero si el conjunto de los números para el sorteo es muy grande hay otra manera elegante: Usted puede construir un pseudoaleatoria de permutación con una clave y una función hash criptográfica. Consulte el siguiente C++-ish ejemplo de pseudo código:

    unsigned randperm(string key, unsigned bits, unsigned index) {
      unsigned half1 =  bits    /2;
      unsigned half2 = (bits+1) /2;
      unsigned mask1 = (1 << half1) - 1;
      unsigned mask2 = (1 << half2) - 1;
      for (int round=0; round<5; ++round) {
        unsigned temp = (index >> half1);
        temp = (temp << 4) + round;
        index ^= hash( key + "/" + int2str(temp) ) & mask1;
        index = ((index & mask2) << half1) | ((index >> half2) & mask1);
      }
      return index;
    }
    

    Aquí, hash sólo es arbitraria en el pseudo-aleatorios función que se asigna a una cadena de caracteres a una posibilidad enorme de enteros sin signo. La función randperm es una permutación de todos los números dentro de 0…pow(2,bits)-1 suponiendo una clave fija. Esto se deduce de la construcción debido a que cada paso que cambia la variable index es reversible. Esto está inspirado por un Sistema de cifrado de Feistel.

    • Igual que stackoverflow.com/a/16097246/648265, falla la aleatoriedad de las secuencias de la misma.
    • En teoría, asumiendo infinito poder de computación, sí. Sin embargo, suponiendo que hash(), tal como se utiliza en el código de arriba, es una función pseudoaleatoria, esta construcción se puede probar (Luby & Rackoff, 1988) dan lugar a una pseudoaleatoria permutación, que no puede ser distinguido de un verdadero aleatoria shuffle con menos esfuerzo de una exhaustiva búsqueda de la clave de todo el espacio, que es exponencial en la longitud de la clave. Incluso razonablemente teclas de tamaño (por ejemplo, 128 bits), esto es más que el total de la potencia de cálculo disponible en la Tierra.
    • (Por CIERTO, sólo para que este argumento un poco más riguroso, prefiero reemplazar el ad hoc hash( key + "/" + int2str(temp) ) construcción arriba con HMAC, cuya seguridad puede a su vez ser demostrablemente reduce a la de la subyacente hash función de compresión. Además, el uso de HMAC puede hacer que sea menos probable que alguien por error intentar usar esta construcción con una inseguridad que no crypto función hash.)
  7. 6

    Usted puede utilizar mi Xincrol algoritmo se describe a continuación:

    http://openpatent.blogspot.co.il/2013/04/xincrol-unique-and-random-number.html

    Esto es un puro método algorítmico de la generación al azar, sino única de números sin matrices, listas, permutaciones o pesada carga de la CPU.

    Última versión permite también establecer el rango de los números, Por ejemplo, si quiero único de números aleatorios en el rango de 0-1073741821.

    He utilizado prácticamente para

    • Reproductor de MP3 que desempeña cada una de las canciones al azar, pero sólo una vez por álbum/directorio de
    • Pixel sabio fotogramas de vídeo disolución de efecto (rápido y suave)
    • La creación de un secreto «ruido» de la niebla sobre la imagen para firmas y marcas (esteganografía)
    • De datos de Identificadores de Objeto para la serialización de la gran cantidad de objetos Java a través de Bases de datos
    • Triple Mayoría bits de memoria protección
    • La dirección+valor de cifrado (cada byte no es sólo que se cifran, pero también se trasladó a un nuevo cifrado ubicación en el buffer). Esto realmente hizo criptoanálisis becarios loco en mí 🙂
    • De Texto plano sin formato, Como la Cripta de Texto cifrado para mensajes SMS, correos electrónicos etc.
    • Mi Texas Hold’em Poker Calculadora (THC)
    • Varios de mis juegos de simulaciones, «revolver», ranking
    • más

    Es abierta, libre. Darle una oportunidad…

    • Puede que el método de trabajo para un valor decimal, por ejemplo de codificación de un decimal de 3 dígitos contador para tener siempre un decimal de 3 dígitos resultado?
    • Como un ejemplo de Xorshift algoritmo, es un LFSR, con todos los kinks (por ejemplo, valores de más de k aparte de la secuencia puede no ocurrir nunca juntos).
  8. 5

    Usted ni siquiera necesita una matriz para resolver esta.

    Necesita una máscara de bits y un contador.

    Inicializar el contador a cero y el incremento en las sucesivas llamadas. XOR el contador con la máscara de bits (seleccionados al azar en el inicio, o fijo) para generar un psuedorandom número. Si usted no puede tener números que superan los 1000, no utilice una máscara de bits más amplia de 9 bits. (En otras palabras, la máscara de bits es un número entero no por encima 511.)

    Asegúrese de que cuando el contador pasa de 1000, se restablece a cero. En este momento usted puede seleccionar otro al azar máscara de bits — si te gusta — para producir el mismo conjunto de números en un orden diferente.

    • Que se engaña a menos gente que un LFSR.
    • «máscara de bits» dentro de 512…1023 está bien, también. Para un poco más falsa que la aleatoriedad ver mi respuesta. 🙂
    • Esencialmente equivalente a stackoverflow.com/a/16097246/648265, también falla la aleatoriedad de las secuencias.
  9. 3

    Aquí está el código que he escrito arriba que utiliza la lógica de la primera solución. Sé que esto es «independiente del idioma», pero sólo quería presentar esto como un ejemplo en C# en el caso de que alguien está buscando una rápida solución práctica.

    //Initialize variables
    Random RandomClass = new Random();
    int RandArrayNum;
    int MaxNumber = 10;
    int LastNumInArray;
    int PickedNumInArray;
    int[] OrderedArray = new int[MaxNumber];      //Ordered Array - set
    int[] ShuffledArray = new int[MaxNumber];     //Shuffled Array - not set
    
    //Populate the Ordered Array
    for (int i = 0; i < MaxNumber; i++)                  
    {
        OrderedArray[i] = i;
        listBox1.Items.Add(OrderedArray[i]);
    }
    
    //Execute the Shuffle                
    for (int i = MaxNumber - 1; i > 0; i--)
    {
        RandArrayNum = RandomClass.Next(i + 1);         //Save random #
        ShuffledArray[i] = OrderedArray[RandArrayNum];  //Populting the array in reverse
        LastNumInArray = OrderedArray[i];               //Save Last Number in Test array
        PickedNumInArray = OrderedArray[RandArrayNum];  //Save Picked Random #
        OrderedArray[i] = PickedNumInArray;             //The number is now moved to the back end
        OrderedArray[RandArrayNum] = LastNumInArray;    //The picked number is moved into position
    }
    
    for (int i = 0; i < MaxNumber; i++)                  
    {
        listBox2.Items.Add(ShuffledArray[i]);
    }
    
  10. 3

    Este método resulta apropiado cuando el límite es de alta y sólo desea generar un par de números aleatorios.

    #!/usr/bin/perl
    
    ($top, $n) = @ARGV; # generate $n integer numbers in [0, $top)
    
    $last = -1;
    for $i (0 .. $n-1) {
        $range = $top - $n + $i - $last;
        $r = 1 - rand(1.0)**(1 /($n - $i));
        $last += int($r * $range + 1);
        print "$last ($r)\n";
    }
    

    Tenga en cuenta que los números se generan en orden ascendente, pero usted puede barajar después.

    • Ya que esto genera combinaciones en lugar de permutaciones, que es más apropiado para stackoverflow.com/questions/2394246/…
    • Las pruebas muestran que esto tiene un sesgo hacia los números más bajos: la medida de las probabilidades de los 2M muestras con (top,n)=(100,10) son : (0.01047705, 0.01044825, 0.01041225, ..., 0.0088324, 0.008723, 0.00863635). He probado en Python, por lo que pequeñas diferencias en matemáticas podría jugar un papel aquí (yo lo hice asegúrese de que todas las operaciones para el cálculo de r son de punto flotante).
    • Sí, para que este método funcione correctamente, el límite superior debe ser mucho más grande que el número de valores para ser extraído.
    • No va a funcionar «correctamente» incluso si «el límite superior [es] mucho más grande que el número de valores». Las probabilidades todavía será desigual, sólo por un menor margen.
  11. 2

    Usted podría utilizar un buen generador de números pseudoaleatorios con 10 bits y tirar 1001 a 1023 salir de 0 a 1000.

    De aquí tenemos el diseño de un 10 bits PRNG..

    • 10 bits, comentarios polinomio x^10 + x^7 + 1 (período 1023)

    • utilizar un Galois LFSR para obtener un código rápido

    • No, eso no va a suceder, porque un 10 bits PRNG basado en un Linear Feedback Shift Register general está hecha de un constructo que asume todos los valores (excepto uno) una vez, antes de regresar a la primera de valor. En otras palabras, sólo recogida 1001 exactamente una vez durante un ciclo.
    • el punto de esta pregunta es para seleccionar cada número sólo una vez. Y luego se quejan de que los 1001 no se dan dos veces en una fila? Un LFSR con una óptima propagación recorrer todos los números en su espacio en un pseudo aleatoria, a continuación, reinicie el ciclo. En otras palabras, no se utiliza como una costumbre función random. Cuando se utiliza como un azar, por lo general sólo utiliza un subconjunto de los bits. Leer un poco sobre ella y pronto va a tener sentido.
    • El único problema es que un LFSR sólo tiene una secuencia, dando así una fuerte correlación entre los números escogidos – en particular, la no generación de cada una de las combinaciones posibles.
  12. 2
    public static int[] randN(int n, int min, int max)
    {
        if (max <= min)
            throw new ArgumentException("Max need to be greater than Min");
        if (max - min < n)
            throw new ArgumentException("Range needs to be longer than N");
    
        var r = new Random();
    
        HashSet<int> set = new HashSet<int>();
    
        while (set.Count < n)
        {
            var i = r.Next(max - min) + min;
            if (!set.Contains(i))
                set.Add(i);
        }
    
        return set.ToArray();
    }
    

    N de No Repetición de números aleatorios será de O(n) complejidad, según sea necesario.

    Nota: al Azar debe ser estático con rosca de seguridad aplicadas.

    • O(n^2), como el número de reintentos es proporcional, en promedio, el número de elementos seleccionados hasta el momento.
    • Piense en ello, si usted selecciona el min=0 max=10000000 y N=5, el número de reintentos de ~=0 no importa cómo muchos de los seleccionados. Pero sí tiene un punto de que si max-min es pequeño, o(N) rompe.
    • Si N<<(max-min), a continuación, todavía es proporcional, es sólo el coeficiente es muy pequeño. Y los coeficientes no importa para una estimación asintótica.
    • Esto no es O(n). Cada vez que el conjunto contiene el valor de este, y de ciclo extra.
  13. 2

    Digamos que usted quiere ir sobre barajan las listas de más y más, sin tener la O(n) retraso cada vez que usted comienza a barajar de nuevo, en ese caso se puede hacer esto:

    1. Crear 2 listas a y B, con 0 a 1000, toma 2n espacio.

    2. Shuffle lista mediante el uso de Fisher-Yates, toma n tiempo.

    3. Cuando el dibujo de un número, hacer 1-paso de Fisher-Yates shuffle en la lista de otros.

    4. Cuando el cursor está en la lista final, cambiar a la otra lista.

    Preprocesar

    cursor = 0
    
    selector = A
    other    = B
    
    shuffle(A)
    

    Dibujar

    temp = selector[cursor]
    
    swap(other[cursor], other[random])
    
    if cursor == N
    then swap(selector, other); cursor = 0
    else cursor = cursor + 1
    
    return temp
    
    • No es necesario tener 2 listas – o de escape de una lista antes de mirar más. Fisher-Yates da uniformemente al azar los resultados de cualquier estado inicial. Consulte stackoverflow.com/a/158742/648265 para la explicación.
    • Sí, es el mismo resultado, pero mi idea aquí es hacer amortizado O(1) por lo que el shuffle parte de la acción de dibujo.
    • Usted no entiende. Que no es necesario restablecer la lista de todos los antes de barajar de nuevo. Arrastrando los pies [1,3,4,5,2] producirá el mismo resultado como arrastrando los pies [1,2,3,4,5].
  14. 2

    Creo que Lineal congruential generador sería la solución más sencilla.

    Únicos (no repetidos) números aleatorios en O(1)?

    y sólo hay 3 restricciones en el un, c y m valores

    1. m y c son relativamente primos,
    2. a-1 es divisible por todos los factores primos de m
    3. a-1 es divisible por 4 si m es divisible por 4

    PS el método se ha mencionado ya, pero el post tiene un suposiciones erróneas acerca de los valores constantes. Las constantes deben funcionar bien para tu caso

    En su caso, usted puede utilizar a = 1002, c = 757, m = 1001

    X = (1002 * X + 757) mod 1001
    
  15. 2

    La pregunta ¿Cómo se puede generar de manera eficiente una lista de los K que no se repitan los números enteros entre 0 y un límite superior N está vinculado como un duplicado – y si usted quiere algo que es O(1) por número aleatorio generado (con no O(n) costo de inicio)) hay un sencillo ajuste de la aceptó respuesta.

    Crear un vacío desordenada mapa (un vacío ordenó mapa se llevará a O(log k) por elemento) de entero a entero, en lugar de utilizar una inicializa la matriz.
    Establecer max 1000 si que es el máximo,

    1. Elegir un número aleatorio r entre 0 y max.
    2. Asegurarse de que tanto los elementos del mapa r y max existen en la desordenada mapa. Si no existen crearlos con un valor igual a su índice.
    3. De intercambio de elementos de r y max
    4. Elemento de retorno max y disminuir max 1 (si max va negativa
      está hecho).
    5. Volver al paso 1.

    La única diferencia en comparación con el uso de un inicializa la matriz es que la inicialización de los elementos se pospone/omitidos – pero va a generar el mismo números de la misma PRNG.

  16. 1

    Otra posibilidad:

    Puede utilizar una matriz de indicadores. Y tome la siguiente a la hora que;s ya elegido.

    Pero, cuidado después de 1000 llamadas, la función no termina nunca debe hacer una salvaguardia.

    • Este uno es O(k^2), lo que con una serie de medidas adicionales proporcional, en promedio, para el número de valores seleccionados hasta el momento.
  17. 1

    Aquí hay algunos ejemplos de código COBOL puede jugar con.

    Puedo enviar RANDGEN.exe archivo de modo que usted puede jugar con él para ver si hace lo que desea.

       IDENTIFICATION DIVISION.
       PROGRAM-ID.  RANDGEN as "ConsoleApplication2.RANDGEN".
       AUTHOR.  Myron D Denson.
       DATE-COMPILED.
      * ************************************************************** 
      *  SUBROUTINE TO GENERATE RANDOM NUMBERS THAT ARE GREATER THAN
      *    ZERO AND LESS OR EQUAL TO THE RANDOM NUMBERS NEEDED WITH NO
      *    DUPLICATIONS.  (CALL "RANDGEN" USING RANDGEN-AREA.)
      *     
      *  CALLING PROGRAM MUST HAVE A COMPARABLE LINKAGE SECTION
      *    AND SET 3 VARIABLES PRIOR TO THE FIRST CALL IN RANDGEN-AREA     
      *
      *    FORMULA CYCLES THROUGH EVERY NUMBER OF 2X2 ONLY ONCE. 
      *    RANDOM-NUMBERS FROM 1 TO RANDOM-NUMBERS-NEEDED ARE CREATED 
      *    AND PASSED BACK TO YOU.
      *
      *  RULES TO USE RANDGEN:
      *
      *    RANDOM-NUMBERS-NEEDED > ZERO 
      *     
      *    COUNT-OF-ACCESSES MUST = ZERO FIRST TIME CALLED.
      *         
      *    RANDOM-NUMBER = ZERO, WILL BUILD A SEED FOR YOU
      *    WHEN COUNT-OF-ACCESSES IS ALSO = 0 
      *     
      *    RANDOM-NUMBER NOT = ZERO, WILL BE NEXT SEED FOR RANDGEN
      *    (RANDOM-NUMBER MUST BE <= RANDOM-NUMBERS-NEEDED)       
      *     
      *    YOU CAN PASS RANDGEN YOUR OWN RANDOM-NUMBER SEED
      *     THE FIRST TIME YOU USE RANDGEN.
      *     
      *    BY PLACING A NUMBER IN RANDOM-NUMBER FIELD
      *      THAT FOLLOWES THESE SIMPLE RULES:
      *        IF COUNT-OF-ACCESSES = ZERO AND 
      *        RANDOM-NUMBER > ZERO AND 
      *        RANDOM-NUMBER <= RANDOM-NUMBERS-NEEDED
      *       
      *    YOU CAN LET RANDGEN BUILD A SEED FOR YOU
      *     
      *      THAT FOLLOWES THESE SIMPLE RULES:
      *        IF COUNT-OF-ACCESSES = ZERO AND 
      *        RANDOM-NUMBER = ZERO AND 
      *        RANDOM-NUMBER-NEEDED > ZERO  
      *         
      *     TO INSURING A DIFFERENT PATTERN OF RANDOM NUMBERS
      *        A LOW-RANGE AND HIGH-RANGE IS USED TO BUILD
      *        RANDOM NUMBERS.
      *        COMPUTE LOW-RANGE =
      *             ((SECONDS * HOURS * MINUTES * MS) /3).         
      *        A HIGH-RANGE = RANDOM-NUMBERS-NEEDED + LOW-RANGE
      *        AFTER RANDOM-NUMBER-BUILT IS CREATED 
      *        AND IS BETWEEN LOW AND HIGH RANGE
      *        RANDUM-NUMBER = RANDOM-NUMBER-BUILT - LOW-RANGE
      *               
      * **************************************************************         
       ENVIRONMENT DIVISION.
       INPUT-OUTPUT SECTION.
       FILE-CONTROL.
       DATA DIVISION.
       FILE SECTION.
       WORKING-STORAGE SECTION.
       01  WORK-AREA.
           05  X2-POWER                     PIC 9      VALUE 2. 
           05  2X2                          PIC 9(12)  VALUE 2 COMP-3.
           05  RANDOM-NUMBER-BUILT          PIC 9(12)  COMP.
           05  FIRST-PART                   PIC 9(12)  COMP.
           05  WORKING-NUMBER               PIC 9(12)  COMP.
           05  LOW-RANGE                    PIC 9(12)  VALUE ZERO.
           05  HIGH-RANGE                   PIC 9(12)  VALUE ZERO.
           05  YOU-PROVIDE-SEED             PIC X      VALUE SPACE.
           05  RUN-AGAIN                    PIC X      VALUE SPACE.
           05  PAUSE-FOR-A-SECOND           PIC X      VALUE SPACE.   
       01  SEED-TIME.
           05  HOURS                        PIC 99.
           05  MINUTES                      PIC 99.
           05  SECONDS                      PIC 99.
           05  MS                           PIC 99. 
      *
      * LINKAGE SECTION.
      *  Not used during testing  
       01  RANDGEN-AREA.
           05  COUNT-OF-ACCESSES            PIC 9(12) VALUE ZERO.
           05  RANDOM-NUMBERS-NEEDED        PIC 9(12) VALUE ZERO.
           05  RANDOM-NUMBER                PIC 9(12) VALUE ZERO.
           05  RANDOM-MSG                   PIC X(60) VALUE SPACE.
      *    
      * PROCEDURE DIVISION USING RANDGEN-AREA.
      * Not used during testing 
      *  
       PROCEDURE DIVISION.
       100-RANDGEN-EDIT-HOUSEKEEPING.
           MOVE SPACE TO RANDOM-MSG. 
           IF RANDOM-NUMBERS-NEEDED = ZERO
             DISPLAY 'RANDOM-NUMBERS-NEEDED ' NO ADVANCING
             ACCEPT RANDOM-NUMBERS-NEEDED.
           IF RANDOM-NUMBERS-NEEDED NOT NUMERIC 
             MOVE 'RANDOM-NUMBERS-NEEDED NOT NUMERIC' TO RANDOM-MSG
               GO TO 900-EXIT-RANDGEN.
           IF RANDOM-NUMBERS-NEEDED = ZERO
             MOVE 'RANDOM-NUMBERS-NEEDED = ZERO' TO RANDOM-MSG
               GO TO 900-EXIT-RANDGEN.
           IF COUNT-OF-ACCESSES NOT NUMERIC
             MOVE 'COUNT-OF-ACCESSES NOT NUMERIC' TO RANDOM-MSG
               GO TO 900-EXIT-RANDGEN.
           IF COUNT-OF-ACCESSES GREATER THAN RANDOM-NUMBERS-NEEDED
             MOVE 'COUNT-OF-ACCESSES > THAT RANDOM-NUMBERS-NEEDED'
               TO RANDOM-MSG
               GO TO 900-EXIT-RANDGEN.
           IF YOU-PROVIDE-SEED = SPACE AND RANDOM-NUMBER = ZERO
             DISPLAY 'DO YOU WANT TO PROVIDE SEED  Y OR N: '
               NO ADVANCING
               ACCEPT YOU-PROVIDE-SEED.  
           IF RANDOM-NUMBER = ZERO AND
              (YOU-PROVIDE-SEED = 'Y' OR 'y')
             DISPLAY 'ENTER SEED ' NO ADVANCING
             ACCEPT RANDOM-NUMBER. 
           IF RANDOM-NUMBER NOT NUMERIC
             MOVE 'RANDOM-NUMBER NOT NUMERIC' TO RANDOM-MSG
             GO TO 900-EXIT-RANDGEN.
       200-RANDGEN-DATA-HOUSEKEEPING.      
           MOVE FUNCTION CURRENT-DATE (9:8) TO SEED-TIME.
           IF COUNT-OF-ACCESSES = ZERO
             COMPUTE LOW-RANGE =
                    ((SECONDS * HOURS * MINUTES * MS) /3).
           COMPUTE RANDOM-NUMBER-BUILT = RANDOM-NUMBER + LOW-RANGE.  
           COMPUTE HIGH-RANGE = RANDOM-NUMBERS-NEEDED + LOW-RANGE.
           MOVE X2-POWER TO 2X2.             
       300-SET-2X2-DIVISOR.
           IF 2X2 < (HIGH-RANGE + 1) 
              COMPUTE 2X2 = 2X2 * X2-POWER
               GO TO 300-SET-2X2-DIVISOR.    
      * *********************************************************         
      *  IF FIRST TIME THROUGH AND YOU WANT TO BUILD A SEED.    *
      * ********************************************************* 
           IF COUNT-OF-ACCESSES = ZERO AND RANDOM-NUMBER = ZERO
              COMPUTE RANDOM-NUMBER-BUILT =
                    ((SECONDS * HOURS * MINUTES * MS) + HIGH-RANGE).
           IF COUNT-OF-ACCESSES = ZERO        
             DISPLAY 'SEED TIME ' SEED-TIME 
                   ' RANDOM-NUMBER-BUILT ' RANDOM-NUMBER-BUILT 
                   ' LOW-RANGE  ' LOW-RANGE.          
      * *********************************************     
      *    END OF BUILDING A SEED IF YOU WANTED TO  * 
      * *********************************************               
      * ***************************************************
      * THIS PROCESS IS WHERE THE RANDOM-NUMBER IS BUILT  *  
      * ***************************************************   
       400-RANDGEN-FORMULA.
           COMPUTE FIRST-PART = (5 * RANDOM-NUMBER-BUILT) + 7.
           DIVIDE FIRST-PART BY 2X2 GIVING WORKING-NUMBER 
             REMAINDER RANDOM-NUMBER-BUILT. 
           IF RANDOM-NUMBER-BUILT > LOW-RANGE AND
              RANDOM-NUMBER-BUILT < (HIGH-RANGE + 1)
             GO TO 600-RANDGEN-CLEANUP.
           GO TO 400-RANDGEN-FORMULA.
      * *********************************************     
      *    GOOD RANDOM NUMBER HAS BEEN BUILT        *               
      * *********************************************
       600-RANDGEN-CLEANUP.
           ADD 1 TO COUNT-OF-ACCESSES.
           COMPUTE RANDOM-NUMBER = 
                RANDOM-NUMBER-BUILT - LOW-RANGE. 
      * *******************************************************
      * THE NEXT 3 LINE OF CODE ARE FOR TESTING  ON CONSOLE   *  
      * *******************************************************
           DISPLAY RANDOM-NUMBER.
           IF COUNT-OF-ACCESSES < RANDOM-NUMBERS-NEEDED
            GO TO 100-RANDGEN-EDIT-HOUSEKEEPING.     
       900-EXIT-RANDGEN.
           IF RANDOM-MSG NOT = SPACE
            DISPLAY 'RANDOM-MSG: ' RANDOM-MSG.
            MOVE ZERO TO COUNT-OF-ACCESSES RANDOM-NUMBERS-NEEDED RANDOM-NUMBER. 
            MOVE SPACE TO YOU-PROVIDE-SEED RUN-AGAIN.
           DISPLAY 'RUN AGAIN Y OR N '
             NO ADVANCING.
           ACCEPT RUN-AGAIN.
           IF (RUN-AGAIN = 'Y' OR 'y')
             GO TO 100-RANDGEN-EDIT-HOUSEKEEPING.
           ACCEPT PAUSE-FOR-A-SECOND.
           GOBACK.
    
    • No tengo idea de si esto realmente puede satisfacer la OPs necesidades, pero la utilería para una COBOL contribución!
  18. 1

    La mayoría de las respuestas aquí no garantizan que no van a devolver el mismo número dos veces. He aquí una solución correcta:

    int nrrand(void) {
      static int s = 1;
      static int start = -1;
      do {
        s = (s * 1103515245 + 12345) & 1023;
      } while (s >= 1001);
      if (start < 0) start = s;
      else if (s == start) abort();
    
      return s;
    }
    

    No estoy seguro de que la restricción está bien especificado. Se supone que después de 1000 otras salidas de un valor se puede repetir, pero que, ingenuamente, permite a 0, inmediatamente después de las 0 siempre que ambos aparecen en el final y el comienzo de los conjuntos de 1000. Por el contrario, si bien es posible mantener una distancia de 1000 otros valores entre repeticiones, haciendo lo que obliga a una situación en la que la secuencia de repeticiones en sí, exactamente de la misma manera todo el tiempo porque no hay otro valor que ha ocurrido fuera de ese límite.

    He aquí un método que garantiza siempre al menos 500 otros valores antes de que un valor puede ser repetido:

    int nrrand(void) {
      static int h[1001];
      static int n = -1;
    
      if (n < 0) {
        int s = 1;
        for (int i = 0; i < 1001; i++) {
          do {
            s = (s * 1103515245 + 12345) & 1023;
          } while (s >= 1001);
          /* If we used `i` rather than `s` then our early results would be poorly distributed. */
          h[i] = s;
        }
        n = 0;
      }
    
      int i = rand(500);
      if (i != 0) {
          i = (n + i) % 1001;
          int t = h[i];
          h[i] = h[n];
          h[n] = t;
      }
      i = h[n];
      n = (n + 1) % 1001;
    
      return i;
    }
    
    • Este es un LCG, como stackoverflow.com/a/196164/648265, no aleatoria de secuencias, así como otros relacionados con torceduras de la misma.
    • el mío es mejor que un LCG, ya que asegura que no va a volver un duplicado en la 1001st llamada.
  19. 1

    Cuando N es mayor que 1000, y usted tiene que dibujar K muestras aleatorias usted podría utilizar un conjunto que contiene las muestras hasta el momento. Para cada sorteo de utilizar el rechazo de muestreo, que será un «casi» O(1) de la operación, por lo que el tiempo total de ejecución es casi O(K) con O(N) de almacenamiento.

    Este algoritmo se ejecuta en colisiones cuando K es «cerca» de N. Esto significa que el tiempo de ejecución va a ser mucho peor que S(K). Una solución sencilla es la inversa de la lógica, de modo que, para K > N/2, a mantener un registro de todas las muestras que no han sido utilizados todavía. Cada sorteo, se extrae una muestra del rechazo conjunto.

    El otro problema evidente con el rechazo de muestreo es que es O(N) de almacenamiento, que es una mala noticia si N está en los miles de millones o más. Sin embargo, existe un algoritmo que resuelve el problema. Este algoritmo se llama Vitter del algoritmo después de su inventor. El algoritmo se describe aquí. La esencia de Vitter del algoritmo es que después de cada sorteo, calcular un azar omitir el uso de una cierta distribución que garantiza la uniformidad de muestreo.

    • Chicos, por favor! El Fisher-Yates método está roto. Selecciona la primera de ellas con una probabilidad 1/N y el segundo con una probabilidad de 1/(N-1) != 1/N. Este es un muestreo sesgado método! Usted realmente necesita el Vittter del algoritmo para resolver el sesgo.
  20. 0

    Fisher Yates

    for i from n−1 downto 1 do
         j ← random integer such that 0 ≤ j ≤ i
         exchange a[j] and a[i]
    

    Realmente es O(n-1) ya que sólo necesita un swap para los dos últimos

    Esto es C#

    public static List<int> FisherYates(int n)
    {
        List<int> list = new List<int>(Enumerable.Range(0, n));
        Random rand = new Random();
        int swap;
        int temp;
        for (int i = n - 1; i > 0; i--)
        {
            swap = rand.Next(i + 1);  //.net rand is not inclusive
            if(swap != i)  //it can stay in place - if you force a move it is not a uniform shuffle
            {
                temp = list[i];
                list[i] = list[swap];
                list[swap] = temp;
            }
        }
        return list;
    }
    
    • Ya hay una respuesta con esto, pero es bastante largo de explicar y no reconoce usted puede parar en 1 (no 0)

Dejar respuesta

Please enter your comment!
Please enter your name here