suma - numeros aleatorios c++

Crear secuencia de números aleatorios sin repeticiones

Question

Duplicar:

¿Números aleatorios únicos en O (1)?

Quiero un generador de números pseudoaleatorios que pueda generar números sin repeticiones en orden aleatorio.

Por ejemplo:

al azar (10)

podría devolver 5, 9, 1, 4, 2, 8, 3, 7, 6, 10

¿Hay una forma mejor de hacerlo que no sea hacer el rango de números y mezclarlos, o verificar la lista generada para las repeticiones?

Editar:

También quiero que sea eficiente en la generación de grandes números sin todo el rango.

Editar:

Veo a todos sugiriendo algoritmos aleatorios. Pero si quiero generar un número aleatorio grande (1024 byte +), ese método tomaría mucha más memoria que si acabara de usar un RNG regular y lo insertara en un Set hasta que tuviera una longitud específica, ¿no? No hay mejor algoritmo matemático para esto.

Answer 1

¿Qué pasa con el uso de generador GUID (como en el de .NET). De acuerdo, no se garantiza que no haya duplicados, sin embargo, la oportunidad de obtener uno es bastante baja.

Answer 2

A medida que genera sus números, use un filtro Bloom para detectar duplicados. Esto usaría una cantidad mínima de memoria. No habría necesidad de almacenar números anteriores en la serie.

La compensación es que su lista no puede ser exhaustiva en su rango. Si sus números son realmente del orden de 256 ^ 1024, eso no significa nada.

(Por supuesto, si son realmente aleatorios en esa escala, incluso molestarse en detectar duplicados es una pérdida de tiempo. Si cada computadora en la tierra generó un billón de números aleatorios de ese tamaño cada billón de años, la posibilidad de una colisión sigue siendo absoluta despreciable.)

Answer 3

Apoyo la respuesta de gbarry sobre el uso de un LFSR . Son muy eficientes y simples de implementar incluso en software y se garantiza que no se repetirán en (2 ^ N - 1) usos para un LFSR con un registro de desplazamiento de N bits.

Sin embargo, hay algunos inconvenientes: al observar un pequeño número de resultados del RNG, uno puede reconstruir el LFSR y predecir todos los valores que generará, lo que los hace no utilizables para la criptografía y en cualquier lugar donde se necesite un buen RNG. El segundo problema es que la palabra all zero o all one (en términos de bits) no es válida según la implementación de LFSR. El tercer problema que es relevante para su pregunta es que la cantidad máxima generada por el LFSR es siempre una potencia de 2 - 1 (o potencia de 2 - 2).

El primer inconveniente podría no ser un problema dependiendo de su aplicación. Según el ejemplo que dio, parece que no espera que el cero esté entre las respuestas; entonces, el segundo problema no parece relevante para su caso. El problema del valor máximo (y por lo tanto del rango) puede resolverse reutilizando el LFSR hasta que obtenga un número dentro de su rango. Aquí hay un ejemplo:

Digamos que quiere tener números entre 1 y 10 (como en su ejemplo). Utilizaría un LFSR de 4 bits que tiene un rango [1, 15] inclusive. Aquí hay un pseudo código sobre cómo obtener el número en el rango [1,10]:

x = LFSR.getRandomNumber();
while (x > 10) {
   x = LFSR.getRandomNumber();
}

Debe incrustar el código anterior en su RNG; para que la persona que llama no se preocupe por la implementación. Tenga en cuenta que esto ralentizaría su RNG si usa un gran registro de desplazamiento y el número máximo que desea no es una potencia de 2 - 1.

Answer 4

Aquí hay un camino al azar sin repetir los resultados. También funciona para cadenas. Está en C # pero el logig debería funcionar en muchos lugares. Coloque los resultados aleatorios en una lista y verifique si el nuevo elemento aleatorio está en esa lista. Si no es así, tienes un nuevo elemento aleatorio. Si está en esa lista, repite el azar hasta que obtengas un elemento que no está en esa lista.

List<string> Erledigte = new List<string>();
private void Form1_Load(object sender, EventArgs e)
{
    label1.Text = "";
    listBox1.Items.Add("a");
    listBox1.Items.Add("b");
    listBox1.Items.Add("c");
    listBox1.Items.Add("d");
    listBox1.Items.Add("e");
}

private void button1_Click(object sender, EventArgs e)
{
    Random rand = new Random();
    int index=rand.Next(0, listBox1.Items.Count);
    string rndString = listBox1.Items[index].ToString();

    if (listBox1.Items.Count <= Erledigte.Count)
    {
        return;
    }
    else
    {
        if (Erledigte.Contains(rndString))
        {
            //MessageBox.Show("vorhanden");
            while (Erledigte.Contains(rndString))
            {
                index = rand.Next(0, listBox1.Items.Count);
                rndString = listBox1.Items[index].ToString();
            }
        }

        Erledigte.Add(rndString);
        label1.Text += rndString;
    }
}

Answer 5

El problema es seleccionar una secuencia "aleatoria" de N números únicos del rango 1..M donde no hay restricción en la relación entre N y M (M podría ser mucho más grande, más o menos igual que N; pueden no ser relativamente primos).

Ampliando la respuesta del registro de desplazamiento de retroalimentación lineal: para un M dado, construya un LFSR máximo para la potencia más pequeña de dos que sea más grande que M. Entonces solo tome los números del LFSR arrojando números mayores que M. En promedio, lo hará arroje como máximo la mitad de los números generados (ya que por construcción más de la mitad del rango del LFSR es menor que M), entonces el tiempo de ejecución esperado para obtener un número es O (1). No está almacenando números generados previamente, por lo que el consumo de espacio también es O (1). Si realiza un ciclo antes de obtener N números, entonces M será menor que N (o el LFSR se construirá incorrectamente).

Puede encontrar los parámetros para LFSR de longitud máxima de hasta 168 bits aquí (de wikipedia): http://www.xilinx.com/support/documentation/application_notes/xapp052.pdf

Aquí hay algunos códigos de Java:

/ ** * Genera una secuencia de números únicos "aleatorios" en [0, M) * @author dkoes * * /

clase pública UniqueRandom {long lfsr; máscara larga; largo máximo;

private static long seed = 1;
//indexed by number of bits
private static int [][] taps = {
        null, // 0
        null, // 1
        null, // 2
        {3,2}, //3
        {4,3},
        {5,3},
        {6,5},
        {7,6},
        {8,6,5,4},
        {9,5},
        {10,7},
        {11,9},
        {12,6,4,1},
        {13,4,3,1},
        {14,5,3,1},
        {15,14},
        {16,15,13,4},
        {17,14},
        {18,11},
        {19,6,2,1},
        {20,17},
        {21,19},
        {22,21},
        {23,18},
        {24,23,22,17},
        {25,22},
        {26,6,2,1},
        {27,5,2,1},
        {28,25},
        {29,27},
        {30,6,4,1},
        {31,28},
        {32,22,2,1},
        {33,20},
        {34,27,2,1},
        {35,33},
        {36,25},
        {37,5,4,3,2,1},
        {38,6,5,1},
        {39,35},
        {40,38,21,19},
        {41,38},
        {42,41,20,19},
        {43,42,38,37},
        {44,43,18,17},
        {45,44,42,41},
        {46,45,26,25},
        {47,42},
        {48,47,21,20},
        {49,40},
        {50,49,24,23},
        {51,50,36,35},
        {52,49},
        {53,52,38,37},
        {54,53,18,17},
        {55,31},
        {56,55,35,34},
        {57,50},
        {58,39},
        {59,58,38,37},
        {60,59},
        {61,60,46,45},
        {62,61,6,5},
        {63,62},
};

//m is upperbound; things break if it isn''t positive
UniqueRandom(long m)
{
    max = m;
    lfsr = seed; //could easily pass a starting point instead
    //figure out number of bits
    int bits = 0;
    long b = m;
    while((b >>>= 1) != 0)
    {
        bits++;
    }
    bits++;

    if(bits < 3)
        bits = 3; 

    mask = 0;
    for(int i = 0; i < taps[bits].length; i++)
    {
        mask |= (1L << (taps[bits][i]-1));
    }

}

//return -1 if we''ve cycled
long next()
{
    long ret = -1;
    if(lfsr == 0)
        return -1;
    do {
        ret = lfsr;
        //update lfsr - from wikipedia
        long lsb = lfsr & 1;
        lfsr >>>= 1;
        if(lsb == 1)
            lfsr ^= mask;

        if(lfsr == seed)            
            lfsr = 0; //cycled, stick

        ret--; //zero is stuck state, never generated so sub 1 to get it
    } while(ret >= max);

    return ret;
}

}

Answer 6

En realidad, hay un punto menor que hacer aquí; un generador de números aleatorios que no se permite repetir no es aleatorio.

Answer 7

Entiendo que no desee una mezcla para grandes rangos, ya que tendría que almacenar toda la lista para hacerlo.

En su lugar, use un hash pseudoaleatorio reversible. Luego ingrese los valores 0 1 2 3 4 5 6, etc. a su vez.

Hay infinitos números de hashes como este. No son demasiado difíciles de generar si están restringidos a una potencia de 2, pero se puede usar cualquier base.

Aquí hay uno que funcionaría, por ejemplo, si quisiera ver todos los valores de 2 ^ 32 32 bit. Es más fácil escribir porque el mod implícito 2 ^ 32 de la matemática entera funciona a su favor en este caso.

unsigned int reversableHash(unsigned int x)
{
   x*=0xDEADBEEF;
   x=x^(x>>17);
   x*=0x01234567;
   x+=0x88776655;
   x=x^(x>>4);
   x=x^(x>>9);
   x*=0x91827363;
   x=x^(x>>7);
   x=x^(x>>11);
   x=x^(x>>20);
   x*=0x77773333;
   return x;
}

Answer 8

Esta respuesta sugiere algunas estrategias para obtener lo que desea y asegurarse de que estén en orden aleatorio utilizando algunos algoritmos ya conocidos.

Existe una versión interna del algoritmo aleatorio Fisher-Yates, llamado la versión Durstenfeld, que distribuye aleatoriamente elementos adquiridos secuencialmente en matrices y colecciones al cargar la matriz o colección.

Una cosa para recordar es que la mezcla aleatoria de Fisher-Yates (AKA Knuth) o la versión de Durstenfeld utilizada en el momento de carga es altamente eficiente con arreglos de objetos porque solo se mueve el puntero de referencia al objeto y el objeto en sí no tiene que ser examinado o comparado con cualquier otro objeto como parte del algoritmo.

Daré ambos algoritmos más adelante.

Si quieres números aleatorios realmente grandes, del orden de 1024 bytes o más, bastará un generador aleatorio realmente bueno que pueda generar bytes o palabras sin signo a la vez. Genere al azar tantos bytes o palabras como necesite para construir el número, conviértalo en un objeto con un puntero de referencia y, listo, tiene un entero aleatorio realmente enorme. Si necesita un rango específico realmente grande, puede agregar un valor base de cero bytes al final de orden bajo de la secuencia de bytes para subir el valor. Esta puede ser tu mejor opción.

Si necesita eliminar duplicados de números aleatorios realmente grandes, entonces eso es más complicado. Incluso con números aleatorios realmente grandes, eliminar duplicados también los hace significativamente sesgados y no aleatorios en absoluto. Si tiene un conjunto realmente grande de números aleatorios muy grandes no duplicados y selecciona al azar entre los que aún no se han seleccionado, entonces el sesgo es solo el sesgo en la creación de los valores enormes para el enorme conjunto de números entre los que puede elegir. Una versión inversa de la versión de Yates-Fisher de Durstenfeld podría usarse para elegir aleatoriamente los valores de un conjunto realmente grande de ellos, eliminarlos de los valores restantes para elegir e insertarlos en una nueva matriz que es un subconjunto y podría hacer esto solo con las matrices de origen y destino in situ. Esto sería muy eficiente.

Esta puede ser una buena estrategia para obtener un pequeño número de números aleatorios con valores enormes de un conjunto realmente grande en el que no están duplicados. Simplemente elija una ubicación aleatoria en el conjunto de origen, obtenga su valor, cambie su valor con el elemento superior en el conjunto de origen, reduzca el tamaño de la fuente en uno y repita con el conjunto de origen de tamaño reducido hasta que haya elegido suficientes valores. Esto es esencialmente la versión Durstenfeld de Fisher-Yates en reversa. A continuación, puede usar la versión de Dursenfeld del algoritmo de Fisher-Yates para insertar los valores adquiridos en el conjunto de destino. Sin embargo, eso es excesivo, ya que deben elegirse al azar y ordenarse aleatoriamente como se indica aquí.

Ambos algoritmos suponen que tiene algún método de instancia de número aleatorio, nextInt (int setSize), que genera un entero aleatorio de cero a setSize, lo que significa que hay valores posibles de setSize. En este caso, será el tamaño de la matriz, ya que el último índice de la matriz es tamaño-1.

El primer algoritmo es la versión de Durstenfeld del algoritmo aleatorio Fisher-Yates (también conocido como Knuth) aplicado a una matriz de longitud arbitraria, una que simplemente coloca aleatoriamente enteros desde 0 hasta la longitud de la matriz en la matriz. La matriz no necesita ser una matriz de enteros, sino que puede ser una matriz de cualquier objeto que se adquiere de forma secuencial, lo que, efectivamente, la convierte en una matriz de punteros de referencia. Es simple, corto y muy efectivo

int size = someNumber;
int[] int array = new int[size]; // here is the array to load
int location; // this will get assigned a value before used
// i will also conveniently be the value to load, but any sequentially acquired
// object will work
for (int i = 0; i <= size; i++) { // conveniently, i is also the value to load
      // you can instance or acquire any object at this place in the algorithm to load
      // by reference, into the array and use a pointer to it in place of j
      int j = i; // in this example, j is trivially i
    if (i == 0) { // first integer goes into first location
        array[i] = j; // this may get swapped from here later
    } else { // subsequent integers go into random locations
            // the next random location will be somewhere in the locations
            // already used or a new one at the end
            // here we get the next random location
            // to preserve true randomness without a significant bias
            // it is REALLY IMPORTANT that the newest value could be
            // stored in the newest location, that is, 
            // location has to be able to randomly have the value i
            int location = nextInt(i + 1); // a random value between 0 and i
            // move the random location''s value to the new location
            array[i] = array[location];
            array[location] = j; // put the new value into the random location
    } // end if...else
} // end for

Voila, ahora tienes una matriz ya aleatorizada.

Si quiere barajar al azar una matriz que ya tiene, aquí está el algoritmo estándar de Fisher-Yates.

type[] array = new type[size];

// some code that loads array...

// randomly pick an item anywhere in the current array segment, 
// swap it with the top element in the current array segment,
// then shorten the array segment by 1
// just as with the Durstenfeld version above,
// it is REALLY IMPORTANT that an element could get
// swapped with itself to avoid any bias in the randomization
type temp; // this will get assigned a value before used
int location; // this will get assigned a value before used
for (int i = arrayLength -1 ; i > 0; i--) {
    int location = nextInt(i + 1);
    temp = array[i];
    array[i] = array[location];
    array[location] = temp;
} // end for

Para colecciones y conjuntos secuenciados, es decir, algún tipo de objeto de lista, puede usar complementos o inserciones con un valor de índice que le permite insertar elementos en cualquier lugar, pero debe permitir agregarlos o agregarlos después del último elemento actual para evitar crear sesgos. en la aleatorización.

Answer 9

Esto se ha preguntado antes - ver mi respuesta a la pregunta anterior . En pocas palabras: puede usar un cifrado de bloques para generar una permutación segura (aleatoria) en cualquier rango que desee, sin tener que almacenar toda la permutación en ningún punto.

Answer 10

Hice una pregunta similar antes, pero la mía fue para todo el rango de una int. Buscar una función hash / Ordered Int / to / Shuffled Int /

Answer 11

Mezclar N elementos no ocupa demasiada memoria ... piénselo. Solo intercambia un elemento a la vez, por lo que la memoria máxima utilizada es la de N + 1 elementos.

Answer 12

Para asegurarse de que la lista no se repita, debería mantener una lista de números previamente devueltos. Como, por lo tanto, tiene que generar toda la lista al final del algoritmo, esto es equivalente en requisitos de almacenamiento para generar la lista ordenada y luego mezclar.

Más acerca de la mezcla aleatoria aquí: creación de una lista ordenada al azar de una lista ordenada

Sin embargo, si el rango de los números aleatorios es muy grande pero la cantidad de números requeridos es pequeña (ha insinuado que este es el requisito real en un comentario), genere una lista completa y mezclarla es un desperdicio. Una reproducción aleatoria en una gran matriz implica acceder a páginas de memoria virtual de una manera que (por definición) vencerá al sistema de paginación del sistema operativo (en una escala más pequeña, el mismo problema ocurriría con la memoria caché de la CPU).

En este caso, buscar en la lista hasta ahora será mucho más eficiente. Entonces, lo ideal sería usar heurística (determinada por experimento) para elegir la implementación correcta para los argumentos dados. (Disculpas por dar ejemplos en C # en lugar de C ++, pero ASFAC++B Me estoy entrenando para pensar en C #).

IEnumerable<int> GenerateRandomNumbers(int range, int quantity)
{
    int[] a = new int[quantity];

    if (range < Threshold)
    {
        for (int n = 0; n < range; n++)
            a[n] = n;

        Shuffle(a);
    }
    else
    {
        HashSet<int> used = new HashSet<int>();

        for (int n = 0; n < quantity; n++)
        {
            int r = Random(range);

             while (!used.Add(r))
                 r = Random(range);

             a[n] = r;
        }
    }

    return a;
}

El costo de hacer la verificación de números repetidos, el bucle mientras hay colisiones, etc. será costoso, pero es probable que exista algún valor de Threshold donde sea más rápido que la asignación para todo el rango.

Para requisitos de cantidad suficientemente pequeños, puede ser más rápido usar una matriz para búsquedas used y lineales en ella, debido a la localidad más grande, a una sobrecarga más baja, a la baratura de la comparación ...

También para grandes cantidades Y grandes rangos, puede ser preferible devolver un objeto que produce los números en la secuencia a petición, en lugar de asignar la matriz para los resultados por adelantado. Esto es muy fácil de implementar en C # gracias a la palabra clave yield return :

IEnumerable<int> ForLargeQuantityAndRange(int quantity, int range)
{
    for (int n = 0; n < quantity; n++)
    {
        int r = Random(range);

        while (!used.Add(r))
            r = Random(range);

        yield return r;
    }
}

Answer 13

Para que una secuencia sea aleatoria, no debe haber ninguna autocorrelación. La restricción de que los números no se repitan significa que el siguiente número debería depender de todos los números anteriores, lo que significa que ya no es aleatorio ....

Answer 14

Por favor revise las respuestas en

Generar secuencia de enteros en orden aleatorio sin construir toda la lista por adelantado

y también mi respuesta se encuentra allí como

 very simple random is 1+((power(r,x)-1) mod p) will be from 1 to p for values of x from 1 to p and will be random where r and p are prime numbers and r <> p.

Answer 15

Puede estar interesado en un registro de desplazamiento de retroalimentación lineal. Solíamos construirlos con hardware, pero también los hice en software. Utiliza un registro de desplazamiento con algunos de los bits xor''ed y retroalimentados a la entrada, y si selecciona los "toques" correctos puede obtener una secuencia que es tan larga como el tamaño del registro. Es decir, un lfsr de 16 bits puede producir una secuencia de 65535 de largo sin repeticiones. Es estadísticamente aleatorio pero por supuesto eminentemente repetible. Además, si se hace mal, puedes obtener algunas secuencias vergonzosamente cortas. Si busca el lfsr, encontrará ejemplos de cómo construirlos correctamente (es decir, "longitud máxima").

Answer 16

Si desea crear números aleatorios grandes (digamos, 64 bits o más) sin repeticiones, simplemente créelos. Si está utilizando un buen generador de números aleatorios, que en realidad tiene suficiente entropía, entonces las probabilidades de generar repeticiones son tan minúsculas que no vale la pena preocuparse.

Por ejemplo, al generar claves criptográficas, nadie realmente se molesta en verificar si ya han generado la misma clave antes; ya que confía en su generador de números aleatorios para que un atacante dedicado no pueda obtener la misma clave, ¿por qué esperaría que apareciera accidentalmente la misma clave?

Por supuesto, si tiene un generador de números aleatorios incorrecto (como la vulnerabilidad del generador de números aleatorios SSL de Debian ) o está generando números lo suficientemente pequeños como para que la paradoja de cumpleaños le brinde una alta probabilidad de colisión, entonces deberá hacer algo para asegurarse no obtienes repeticiones Pero para grandes números aleatorios con un buen generador, solo confíe en la probabilidad de no darle ninguna repetición.

Answer 17

Si no se refiere a las propiedades estadísticas pobres de la secuencia generada, hay un método:

Digamos que quieres generar N números, cada uno de 1024 bits cada uno. Puede sacrificar algunos bits del número generado para ser "contador".

Entonces usted genera cada número aleatorio, pero en algunos bits que usted elige pone contador binario codificado (de la variable, aumenta cada vez que se genera el siguiente número aleatorio).

Puede dividir ese número en bits individuales y colocarlo en algunos de los bits generados menos significativos.

De esta forma, está seguro de obtener un número único cada vez.

Quiero decir, por ejemplo, cada número generado tiene el siguiente aspecto: xxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxyyxxxxyxyyyyxxyxx donde x se toma directamente del generador, y y se toman de la variable del contador.

Answer 18

Si no te molestan las propiedades de aleatoriedad mediocres y si la cantidad de elementos lo permite, entonces podrías usar un generador de números aleatorios congruenciales lineales .

Answer 19

Si puede generar números aleatorios ''pequeños'', puede generar números aleatorios ''grandes'' integrándolos: agregue un pequeño incremento aleatorio a cada ''anterior''.

const size_t amount = 100; // a limited amount of random numbers
vector<long int> numbers; 
numbers.reserve( amount );
const short int spread = 250; // about 250 between each random number
numbers.push_back( myrandom( spread ) );
for( int n = 0; n != amount; ++n ) {
    const short int increment = myrandom( spread );
    numbers.push_back( numbers.back() + increment );
}

myshuffle( numbers );

Las funciones de myrandom y myshuffle esta medio generosamente delegar a otros :)

Answer 20

Si se garantiza que un número aleatorio nunca se repetirá, ya no es aleatorio y la cantidad de aleatoriedad disminuye a medida que se generan los números (después de nueve números random(10) es bastante predecible e incluso después de solo ocho, tiene una probabilidad de 50-50).

Answer 21

Supongamos que quiere generar una serie de 256 números aleatorios sin repeticiones.

1. Cree un bloque de memoria de 256 bits (32 bytes) inicializado con ceros, llamémoslo b
2. Su variable de bucle será n , la cantidad de números que aún no se ha generado
3. Loop de n = 256 a n = 1
4. Genera un número aleatorio r en el rango [0, n)
5. Encuentre el r -ésimo bit cero en su bloque de memoria b , llamémoslo p
6. Pon p en tu lista de resultados, una matriz llamada q
7. Voltee la p -ésima bit en el bloque de memoria b a 1
8. Después del n = 1 pase, ha terminado de generar su lista de números

Aquí hay un breve ejemplo de lo que estoy hablando, usando inicialmente n = 4:

**Setup**
b = 0000
q = []

**First loop pass, where n = 4**
r = 2
p = 2
b = 0010
q = [2]

**Second loop pass, where n = 3**
r = 2
p = 3
b = 0011
q = [2, 3]

**Third loop pass, where n = 2**
r = 0
p = 0
b = 1011
q = [2, 3, 0]

** Fourth and final loop pass, where n = 1**
r = 0
p = 1
b = 1111
q = [2, 3, 0, 1]

Answer 22

Suponiendo que tiene un generador de números aleatorio o pseudoaleatorio, incluso si no se garantiza que devuelva valores únicos, puede implementar uno que devuelva valores únicos cada vez que utilice este código, suponiendo que el límite superior permanezca constante (es decir, siempre lo llame con random(10) , y no lo llames random(10); random(11) .

El código no verifica si hay errores. Puede agregarlo usted mismo si lo desea.
También requiere mucha memoria si desea una gran variedad de números.

/* the function returns a random number between 0 and max -1
 * not necessarily unique
 * I assume it''s written
 */
int random(int max);

/* the function returns a unique random number between 0 and max - 1 */
int unique_random(int max)
{

    static int *list = NULL;    /* contains a list of numbers we haven''t returned */
    static int in_progress = 0; /* 0 --> we haven''t started randomizing numbers
                                 * 1 --> we have started randomizing numbers
                                 */

    static int count;
    static prev_max = 0;

    // initialize the list
    if (!in_progress || (prev_max != max)) {
        if (list != NULL) {
            free(list);
        }
        list = malloc(sizeof(int) * max);
        prev_max = max;
        in_progress = 1;
        count = max - 1;

        int i;
        for (i = max - 1; i >= 0; --i) {
            list[i] = i;
        }
    }

    /* now choose one from the list */
    int index = random(count);
    int retval = list[index];

    /* now we throw away the returned value.
     * we do this by shortening the list by 1
     * and replacing the element we returned with
     * the highest remaining number
     */
    swap(&list[index], &list[count]);

    /* when the count reaches 0 we start over */
    if (count == 0) {
        in_progress = 0;
        free(list);
        list = 0;
    } else { /* reduce the counter by 1 */
        count--;
    }
}

/* swap two numbers */
void swap(int *x, int *y)
{
    int temp = *x;
    *x = *y;
    *y = temp;
}

Answer 23

Twister Mersenne

Descripción de lo que se puede encontrar aquí en Wikipedia: Twister Mersenne

Mire la parte inferior de la página para ver las implementaciones en varios idiomas.

Answer 24

Un shuffle es lo mejor que puedes hacer para números aleatorios en un rango específico sin repeticiones. La razón por la cual el método que describes (generar números aleatoriamente y ponerlos en un conjunto hasta que alcances una longitud específica) es menos eficiente debido a los duplicados. Teóricamente, ese algoritmo podría nunca terminar. En el mejor de los casos, terminará en un período de tiempo indeterminable, en comparación con una reproducción aleatoria, que siempre se ejecutará en un período de tiempo altamente predecible.

Respuesta a ediciones y comentarios:

Si, como lo indica en los comentarios, el rango de números es muy grande y desea seleccionar relativamente pocos al azar sin repeticiones, entonces la probabilidad de repeticiones disminuye rápidamente. Cuanto mayor sea la diferencia de tamaño entre el rango y el número de selecciones, menor será la probabilidad de repetir selecciones, y mejor será el rendimiento para el algoritmo de selección y verificación que describe en la pregunta.

Answer 25

Una reproducción aleatoria es una forma perfectamente buena de hacerlo (siempre que no introduzca un sesgo utilizando el algoritmo ingenuo). Ver mezcla de Fisher-Yates .

Answer 26

ahora tenemos una matriz con diferentes números!

int main() {
    int b[(the number
    if them)];
    for (int i = 0; i < (the number of them); i++) {
    int a = rand() % (the number of them + 1) + 1;
    int j = 0;
    while (j < i) {
        if (a == b[j]) {
        a = rand() % (the number of them + 1) + 1;
        j = -1;
        }
        j++;
    }
    b[i] = a;
    }
}

Answer 27

tener números aleatorios no repetidos y evitar el tiempo de espera con la verificación de números de dobles y obtener números nuevos una y otra vez, utilice el siguiente método que asegurará el uso mínimo de Rand: por ejemplo, si quiere obtener 100 números aleatorios no repetidos: 1. llene una matriz con números del 1 al 100 2. obtenga un número aleatorio usando la función Rand en el rango de (1-100) 3. use el número aleatorio genarted como un índice para obtener el valor de la matriz (Números [IndexGeneratedFromRandFunction] 4 cambie el número en la matriz después de ese índice a la izquierda 5. repita desde el paso 2, pero ahora el sondeo debería ser (1-99) y continúe

Answer 28

static std::unordered_set<long> s;
long l = 0;
for(; !l && (s.end() != s.find(l)); l = generator());
v.insert(l);

generador () es su generador de números aleatorios. Tira números siempre que la entrada no esté en su conjunto, luego agrega lo que encuentre en ella. Entiendes la idea.

Lo hice con long para el ejemplo, pero debes hacer una plantilla si tu PRNG está templado.

Alternativa es usar un PRNG criptográficamente seguro que tendrá una probabilidad muy baja de generar el doble del mismo número.