algorithm - repeticion - Números aleatorios únicos(no repetitivos) en O(1)?

numeros aleatorios en excel

Question

Me gustaría generar números aleatorios únicos entre 0 y 1000 que nunca se repitan (es decir, 6 no aparecen dos veces), pero eso no recurre a algo así como una búsqueda O (N) de valores previos para hacerlo. es posible?

Answer 1

Aquí hay un código que escribí que usa la lógica de la primera solución. Sé que esto es "independiente del idioma", pero solo quería presentar esto como un ejemplo en C # en caso de que alguien esté buscando una solución práctica rápida.

// 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]);
}

Answer 2

Aquí hay un ejemplo de código COBOL con el que puedes jugar.
Puedo enviarle el archivo RANDGEN.exe para que pueda jugar con él y ver si desea que lo desee.

 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.

Answer 3

Creo que el generador congruente lineal sería la solución más simple.

y solo hay 3 restricciones en los valores a, c y m

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

PD: el método ya se mencionó pero la publicación tiene suposiciones erróneas sobre los valores constantes. Las constantes a continuación deberían funcionar bien para su caso

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

X = (1002 * X + 757) mod 1001

Answer 4

Este método resulta apropiado cuando el límite es alto y solo desea generar algunos 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 luego puede mezclarlos.

Answer 5

Inicialice una matriz de 1001 enteros con los valores 0-1000 y establezca una variable, max, en el índice máximo actual de la matriz (comenzando por 1000). Elija un número aleatorio, r, entre 0 y max, intercambie el número en la posición r con el número en la posición max y regrese el número ahora en la posición max. Disminuir max por 1 y continuar. Cuando max es 0, ajuste max al tamaño de la matriz - 1 y comience nuevamente sin la necesidad de reiniciar la matriz.

Actualización: Aunque se me ocurrió este método por mi cuenta cuando respondí la pregunta, después de algunas investigaciones me di cuenta de que esta es una versión modificada de Fisher-Yates conocida como Durstenfeld-Fisher-Yates o Knuth-Fisher-Yates. Dado que la descripción puede ser un poco difícil de seguir, he proporcionado un ejemplo a continuación (usando 11 elementos en lugar de 1001):

Array comienza con 11 elementos inicializados en array [n] = n, max comienza en 10:

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

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

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 de 11 iteraciones, se han seleccionado todos los números en la matriz, máximo == 0, y los elementos de la matriz se barajan:

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

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

Answer 6

La mayoría de las respuestas aquí no garantizan que no devolverán el mismo número dos veces. Aquí hay 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;
}

I''m not sure that the constraint is well specified. One assumes that after 1000 other outputs a value is allowed to repeat, but that naively allows 0 to follow immediately after 0 so long as they both appear at the end and start of sets of 1000. Conversely, while it''s possible to keep a distance of 1000 other values between repetitions, doing so forces a situation where the sequence replays itself in exactly the same way every time because there''s no other value that has occurred outside of that limit.

Here''s a method that always guarantees at least 500 other values before a value can be repeated:

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

Answer 7

Ni siquiera necesitas una matriz para resolver este.

Necesitas una máscara de bits y un contador.

Inicialice el contador a cero e increméntelo en llamadas sucesivas. XOR el contador con la máscara de bits (seleccionada al azar al inicio, o fija) para generar un número psuedorandom. Si no puede tener números que excedan 1000, no use una máscara de bits de más de 9 bits. (En otras palabras, la máscara de bits es un número entero no superior a 511).

Asegúrese de que cuando el contador pase 1000, lo restablezca a cero. En este momento puede seleccionar otra máscara de bits aleatoria, si lo desea, para producir el mismo conjunto de números en un orden diferente.

Answer 8

Otra posibilidad:

Puede usar una matriz de banderas. Y toma el siguiente cuando ya esté elegido.

Pero ten cuidado después de 1000 llamadas, la función nunca terminará, así que debes hacer una salvaguarda.

Answer 9

Para números bajos como 0 ... 1000, crear una lista que contenga todos los números y mezclarlos es sencillo. Pero si el conjunto de números para dibujar es muy grande, hay otra manera elegante: puede construir una permutación pseudoaleatoria utilizando una clave y una función de cifrado hash. Vea el siguiente pseudo código de C ++ - ish:

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í, el hash es solo una función pseudoaleatoria arbitraria que asigna una cadena de caracteres a un entero enormemente sin signo. La función randperm es una permutación de todos los números dentro de 0 ... pow (2, bits) -1 asumiendo una clave fija. Esto se sigue de la construcción porque cada paso que cambia el index la variable es reversible. Esto está inspirado en un cifrado de Feistel .

Answer 10

Podría usar un generador congruente lineal . Donde m (el módulo) sería el primer más cercano más grande que 1000. Cuando obtienes un número fuera del rango, simplemente obtén el siguiente. La secuencia solo se repetirá una vez que se hayan producido todos los elementos, y usted no tiene que usar una tabla. Sin embargo, tenga en cuenta las desventajas de este generador (incluida la falta de aleatoriedad).

Answer 11

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. Por ejemplo, en el ejemplo de esta pregunta: radix 10, ancho 3.

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 crear un cifrado de menor ancho, de cualquier radix y ancho que desee, con un algoritmo que sigue siendo 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ó.

Esta técnica no necesita memoria para almacenar una matriz mezclada, etc., que puede ser una ventaja en sistemas con memoria limitada.

AES-FFX es un método estándar propuesto para lograr esto. He experimentado con un código básico de Python que se basa en la idea de AES-FFX, aunque no totalmente conforme. Consulte aquí el código de Python . Por ejemplo, puede encriptar un contador a un número decimal de 7 dígitos de aspecto aleatorio o un número de 16 bits. Aquí hay un ejemplo de radix 10, ancho 3 (para dar un número entre 0 y 999 inclusive) como la pregunta establecida:

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 secuencias pseudoaleatorias no repetitivas, cambie la clave de cifrado. Cada clave de cifrado produce una secuencia pseudoaleatoria diferente no repetitiva.

Answer 12

Puede usar mi algoritmo de Xincrol que se describe aquí:

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

Este es un método algorítmico puro para generar números aleatorios pero únicos sin matrices, listas, permutaciones o una gran carga de CPU.

La última versión también permite establecer el rango de números, por ejemplo, si quiero números aleatorios únicos en el rango de 0-1073741821.

Prácticamente lo he usado para

• Reproductor de MP3 que reproduce todas las canciones al azar, pero solo una vez por álbum / directorio
• Pixel wise video frames que disuelve el efecto (rápido y suave)
• Creación de una niebla secreta de "ruido" sobre la imagen para firmas y marcadores (esteganografía)
• ID de objetos de datos para la serialización de gran cantidad de objetos Java a través de bases de datos
• Protección de bits de memoria Triple Mayoría
• Encriptación de dirección + valor (cada byte no solo está encriptado, sino que también se mueve a una nueva ubicación encriptada en el búfer). Esto realmente hizo enojar a los tipos del criptoanálisis :-)
• Texto simple a simple como Crypt. Cifrado de texto para SMS, correos electrónicos, etc.
• Mi calculadora de poker Texas Hold`em (THC)
• Varios de mis juegos para simulaciones, "barajar", clasificación
• Más

Está abierto, gratis. Darle una oportunidad...

Answer 13

Puede usar un buen generador de números pseudoaleatorios con 10 bits y descartar 1001 a 1023 dejando 0 a 1000.

A partir de aquí obtenemos el diseño de un PRNG de 10 bits.

• 10 bits, polinomio de retroalimentación x ^ 10 + x ^ 7 + 1 (período 1023)

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

Answer 14

Puedes hacerlo:

1. Crea una lista, 0..1000.
2. Baraja la lista. (Consulte la mezcla de Fisher-Yates para ver una buena forma de hacerlo).
3. Devuelva los números en orden desde la lista mezclada.

Por lo tanto, esto no requiere una búsqueda de valores antiguos cada vez, pero aún requiere O (N) para la mezcla inicial. Pero como señaló Nils en los comentarios, esto se amortiza O (1).

Answer 15

Supongamos que desea revisar listas mezcladas una y otra vez, sin tener que O(n) demorar cada vez que empiece de nuevo para mezclar de nuevo, en ese caso podemos hacer esto:

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

2. La lista aleatoria A usando Fisher-Yates, toma n tiempo.

3. Al dibujar un número, haga una mezcla de Fisher-Yates de 1 paso en la otra lista.

4. Cuando el cursor está al final de la lista, cambie a la otra lista.

Preproceso

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

Answer 16

Use un Registro de desplazamiento de realimentación lineal máxima .

Es implementable en unas pocas líneas de C y en tiempo de ejecución hace poco más que un par de pruebas / ramas, una pequeña adición y cambio de bit. No es aleatorio, pero engaña a la mayoría de las personas.

Answer 17

Fisher Yates

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

It is actually O(n-1) as you only need one swap for the last two
This is 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;
}

Answer 18

Please see my answer at https://.com/a/46807110/8794687

Es uno de los algoritmos más simples que tienen una complejidad de tiempo promedio O ( s log s ), s que denota el tamaño de muestra. También hay algunos enlaces a algoritmos de tablas hash cuya complejidad se afirma que es O ( s ).

Answer 19

The question How do you efficiently generate a list of K non-repeating integers between 0 and an upper bound N is linked as a duplicate - and if you want something that is O(1) per generated random number (with no O(n) startup cost)) there is a simple tweak of the accepted answer.

Create an empty unordered map (an empty ordered map will take O(log k) per element) from integer to integer - instead of using an initialized array. Set max to 1000 if that is the maximum,

1. Pick a random number, r, between 0 and max.
2. Ensure that both map elements r and max exist in the unordered map. If they don''t exist create them with a value equal to their index.
3. Swap elements r and max
4. Return element max and decrement max by 1 (if max goes negative you are done).
5. Back to step 1.

The only difference compared with using an initialized array is that the initialization of elements is postponed/skipped - but it will generate the exact same numbers from the same PRNG.

Answer 20

When N is greater than 1000 and you need to draw K random samples you could use a set that contains the samples so far. For each draw you use rejection sampling , which will be an "almost" O(1) operation, so the total running time is nearly O(K) with O(N) storage.

This algorithm runs into collisions when K is "near" N. This means that running time will be a lot worse than O(K). A simple fix is to reverse the logic so that, for K > N/2, you keep a record of all the samples that have not been drawn yet. Each draw removes a sample from the rejection set.

The other obvious problem with rejection sampling is that it is O(N) storage, which is bad news if N is in the billions or more. However, there is an algorithm that solves that problem. This algorithm is called Vitter''s algorithm after it''s inventor. The algorithm is described here . The gist of Vitter''s algorithm is that after each draw, you compute a random skip using a certain distribution which guarantees uniform sampling.

Answer 21

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 Los números aleatorios no repetitivos serán de complejidad O (n), según sea necesario.
Nota: Aleatorio debe ser estático con seguridad de hilo aplicada.