Números aleatorios únicos en una matriz de enteros en el lenguaje de progtwigción C

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

¿Cómo llené una matriz de enteros con valores únicos (sin duplicados) en C?

int vektor[10]; for (i = 0; i < 10; i++) { vektor[i] = rand() % 100 + 1; } //No uniqueness here 

Hay varias formas de resolver su problema, cada una tiene sus propias ventajas y desventajas.

Primero, me gustaría señalar que ya obtuvo bastantes respuestas que hacen lo siguiente: generan un número aleatorio, luego verifican si ya se utilizó en la matriz y si ya se utilizó, simplemente generan otra número hasta que encuentren uno sin usar. Este es un enfoque ingenuo y, a decir verdad, seriamente defectuoso. El problema es con la naturaleza cíclica de prueba y error de la generación de números (“si ya se ha utilizado, inténtelo de nuevo”). Si el rango numérico (por ejemplo, [1..N]) está cerca de la longitud de la matriz deseada (por ejemplo, M), entonces, hacia el final, el algoritmo puede pasar una gran cantidad de tiempo tratando de encontrar el siguiente número. Si el generador de números aleatorios está incluso un poco roto (digamos, nunca genera un número, o lo hace muy raramente), entonces con N == M se garantiza que el algoritmo se repetirá para siempre (o durante mucho tiempo). En general, este enfoque de prueba y error es inútil, o defectuoso en el mejor de los casos.

Otro enfoque que ya se presenta aquí es generar una permutación aleatoria en una matriz de tamaño N. La idea de la permutación aleatoria es prometedora, pero al hacerlo en una matriz de tamaño N (cuando M < < N) sin duda generará más calor que luz hablando en sentido figurado

Se pueden encontrar buenas soluciones a este problema, por ejemplo, en “Programming Pearls” de Bentley (y algunas de ellas están tomadas de Knuth).


  • El algoritmo Knuth. Este es un algoritmo muy simple con una complejidad de O (N) (es decir, el rango numérico), lo que significa que es más útil cuando M está cerca de N. Sin embargo, este algoritmo no requiere ninguna memoria adicional además de su vektor array, a diferencia de la variante ya ofrecida con permutaciones (lo que significa que toma O (M) memoria, no O (N) como otros algoritmos basados ​​en permutación sugeridos aquí). Este último lo convierte en un algoritmo viable incluso para M < < N casos.

El algoritmo funciona de la siguiente manera: itera a través de todos los números de 1 a N y selecciona el número actual con probabilidad rm / rn , donde rm es la cantidad de números que aún necesitamos encontrar, y rn es la cantidad de números que aún necesitamos para iterar. Aquí hay una posible implementación para su caso

 #define M 10 #define N 100 int in, im; im = 0; for (in = 0; in < N && im < M; ++in) { int rn = N - in; int rm = M - im; if (rand() % rn < rm) /* Take it */ vektor[im++] = in + 1; /* +1 since your range begins from 1 */ } assert(im == M); 

Después de este ciclo obtenemos un vector de vektor lleno de números elegidos al azar en orden ascendente . El bit de "orden ascendente" es lo que no necesitamos aquí. Entonces, para "arreglar" que solo hacemos una permutación aleatoria de elementos de vektor y terminamos. Tenga en cuenta que esto es una permutación O (M) que no requiere memoria extra. (Dejo fuera la implementación del algoritmo de permutación. Ya se han proporcionado muchos enlaces).

Si miras detenidamente los algoritmos basados ​​en permutación propuestos aquí que operan en una matriz de longitud N, verás que la mayoría de ellos son más o menos el mismo algoritmo Knuth, pero reformulados para M == N En ese caso, el ciclo de selección anterior elegirá todos y cada uno de los números en el rango [1..N] con probabilidad 1, convirtiéndose efectivamente en la inicialización de una matriz N con los números 1 a N. Teniendo esto en cuenta, creo que se vuelve más bien es obvio que ejecutar este algoritmo para M == N y luego truncar el resultado (posiblemente descartando la mayor parte) tiene mucho menos sentido que simplemente ejecutar este algoritmo en su forma original para el valor original de M y obtener el resultado de inmediato, sin ningún truncamiento.


  • El algoritmo Floyd (ver aquí ). Este enfoque tiene una complejidad de aproximadamente O (M) (depende de la estructura de búsqueda utilizada), por lo que es más adecuado cuando M < < N. Este enfoque realiza un seguimiento de los números aleatorios ya generados, por lo que requiere memoria extra. Sin embargo, la belleza de esto es que no hace ninguna de esas iteraciones abominables de prueba y error, tratando de encontrar un número aleatorio no utilizado. Se garantiza que este algoritmo generará un número aleatorio único después de cada llamada al generador de números aleatorios.

Aquí hay una posible implementación para su caso. (Hay diferentes maneras de hacer un seguimiento de los números ya utilizados. Usaré una serie de banderas, suponiendo que N no sea prohibitivamente grande)

 #define M 10 #define N 100 unsigned char is_used[N] = { 0 }; /* flags */ int in, im; im = 0; for (in = N - M; in < N && im < M; ++in) { int r = rand() % (in + 1); /* generate a random number 'r' */ if (is_used[r]) /* we already have 'r' */ r = in; /* use 'in' instead of the generated number */ assert(!is_used[r]); vektor[im++] = r + 1; /* +1 since your range begins from 1 */ is_used[r] = 1; } assert(im == M); 

Por qué lo anterior funciona no es inmediatamente obvio. Pero funciona. Los números M exactos del rango [1..N] se seleccionarán con una distribución uniforme.

Tenga en cuenta que, para N grandes, puede utilizar una estructura basada en búsquedas para almacenar números "ya usados", obteniendo así un buen algoritmo O (M log M) con un requisito de memoria O (M).

(Sin embargo, hay una cosa acerca de este algoritmo: aunque la matriz resultante no se ordenará, una cierta "influencia" del orden original 1..N seguirá presente en el resultado. Por ejemplo, es obvio que el número N, si seleccionado, solo puede ser el último miembro de la matriz resultante. Si esta "contaminación" del resultado por el orden involuntario no es aceptable, la matriz vektor resultante se puede barajar aleatoriamente, al igual que en el algoritmo Khuth).


Tenga en cuenta el punto muy crítico observado en el diseño de estos dos algoritmos: nunca bucle , tratando de encontrar un nuevo número aleatorio no utilizado. Cualquier algoritmo que realice iteraciones de prueba y error con números aleatorios es defectuoso desde el punto de vista práctico. Además, el consumo de memoria de estos algoritmos está vinculado a M, no a N

Al OP recomendaría el algoritmo de Floyd, ya que en su aplicación M parece ser considerablemente menor que N y que no requiere (o puede no) un pase adicional para la permutación. Sin embargo, para valores tan pequeños de N la diferencia puede ser insignificante.

En su ejemplo (elija 10 números aleatorios únicos entre 1 y 100), puede crear una lista con los números del 1 al 100, usar el generador de números aleatorios para mezclar la lista y luego tomar los primeros 10 valores de la lista.

 int list[100], vektor[10]; for (i = 0; i < 100; i++) { list[i] = i; } for (i = 0; i < 100; i++) { int j = i + rand() % (100 - i); int temp = list[i]; list[i] = list[j]; list[j] = temp; } for (i = 0; i < 10; i++) { vektor[i] = list[i]; } 

Según el comentario de cobbal a continuación, es incluso mejor decir:

 for (i = 0; i < 10; i++) { int j = i + rand() % (100 - i); int temp = list[i]; list[i] = list[j]; list[j] = temp; vektor[i] = list[i]; } 

Ahora es O (N) para configurar la lista pero O (M) para elegir los elementos aleatorios.

Simplemente generar números aleatorios y ver si están bien es una manera pobre de resolver este problema en general. Este enfoque toma todos los valores posibles, los mezcla y luego toma los diez primeros. Esto es directamente análogo a barajar una baraja de cartas y tratar con la parte superior.

 #include  #include  #include 

Para obtener más información, consulte comp.lang.c la lista de preguntas frecuentes pregunta 13.19 para barajar y la pregunta 13.16 sobre la generación de números aleatorios.

Creo que esto lo hará (no he intentado construirlo, por lo que los errores de syntax se deben corregir como ejercicio para el lector). Puede haber formas más elegantes, pero esta es la solución de fuerza bruta:

 int vektor[10];  int random; int uniqueflag; int i, j for(i = 0; i < 10; i++) { do { /* Assume things are unique... we'll reset this flag if not. */ uniqueflag = 1; random = rand() % 100+ 1; /* This loop checks for uniqueness */ for (j = 0; j < i && uniqueflag == 1; j++) { if (vektor[j] == random) { uniqueflag = 0; } } } while (uniqueflag != 1); vektor[i] = random; } 

Una forma sería verificar si la matriz ya contiene el nuevo número aleatorio, y si lo hace, crear uno nuevo y volver a intentarlo.

Esto se abre para la posibilidad (aleatoria;)) de que nunca obtendrías un número que no está en la matriz. Por lo tanto, debe contar cuántas veces verifica si el número ya está en la matriz, y si el conteo excede MAX_DUPLICATE_COUNT, eche una excepción más o menos 🙂 (EDIT, vio que está en C. Olvidémonos de la excepción 🙂 Devuelva un error código en su lugar: P)

Una solución rápida es crear una matriz de máscaras de todos los números posibles inicializados en ceros, y establecer una entrada si ese número se genera

 int rand_array[100] = {0}; int vektor[10]; int i=0, rnd; while(i<10) { rnd = rand() % 100+ 1; if ( rand_array[rnd-1] == 0 ) { vektor[i++] = rnd; rand_array[rnd-1] = 1; } } 

Aquí hay un método O (M) de tiempo promedio.

Método: Si M < = N / 2, use el procedimiento S (M, N) (abajo) para generar la matriz de resultados R, y devuelva R. Si M> N / 2, use el procedimiento S (NM, N) para generar R, luego calcule X = {1..M}\R [el complemento de R en {1..M}], mezcle X con Fisher-Yates shuffle [en el tiempo O (M)], y devuelva X.

En el caso M> N / 2, donde O (M) == O (N), hay varias formas rápidas de calcular el complemento. En el código que se muestra a continuación, para abreviar solo he incluido un ejemplo del procedimiento S (M, N) codificado en línea en main (). La combinación aleatoria de Fisher-Yates es O (M) y se ilustra en la respuesta principal a la pregunta relacionada n . ° 196017 . Otras preguntas relacionadas anteriores: # 158716 y # 54059 .

La razón por la que S (M, N) toma O (M) tiempo en lugar de O (N) tiempo cuando M H_k, de la cual E (t_ {k / 2}) = k (H_k – H_ {k / 2}) o sobre k * (ln (k) -ln (k / 2) + O (1)) = k * (ln (k / (k / 2)) + O (1)) = k * (ln (2) + O (1)) = O (k).

Procedimiento S (k, N): [El cuerpo de este procedimiento es la docena de líneas después del comentario “Gen M números aleatorios distintos” en el código a continuación.] Asigne e inicialice tres matrices de enteros M + 1 elementos H, L y V a todos -1 valores. Para i = 0 a M-1: Ponga un valor aleatorio v en V [i] y en el nodo centinela V [-1]. Obtenga uno de los encabezados de M lista de H [v% M] y siga esa lista hasta encontrar una coincidencia con v. Si la coincidencia está en V [-1], v es un valor nuevo; entonces actualice la cabecera de la lista H [v% M] y enumere el enlace L [i]. Si la coincidencia no está en V [-1], obtenga y pruebe otra v, etc.

Cada paso “seguir la lista” tiene un costo esperado O (1) porque en cada paso excepto el último, la longitud promedio de la lista es menor que 1. (Al final del procesamiento, las listas M contienen M elementos, por lo que la longitud promedio aumenta gradualmente a 1.)

  // randomMofN - jiw 8 Nov 2011 // Re: https://stackoverflow.com/questions/1608181/ #include  #include  int main(int argc, char *argv[]) { int h, i, j, tM, M, N, par=0, *H, *L, *V, cxc=0; // Get M and N values ++par; M = 42; if (argc > par) M = atoi(argv[par]); ++par; N = 137; if (argc > par) N = atoi(argv[par]); tM = 3*M+3; H = malloc(tM*sizeof(int)); printf ("M = %d, N = %d %s\n", M, N, H?"":"\nmem error"); if (!H) exit(13); for (i=0; i=0); L[i] = H[h]; H[h] = i; } // Print results for (j=i=0; i66) j = printf ("\n"); } printf ("\ncxc %d\n", cxc); return 0; } 

me gusta el algoritmo Floyd.

pero podemos tomar todo el número aleatorio de 0 a M (no a):

 #define M 10 #define N 100 unsigned char is_used[N] = { 0 }; /* flags */ int in, im; im = 0; for (in = N - M; in < N && im < M; ++in) { int r = rand() % (N + 1); /* generate a random number 'r' */ while (is_used[r]) { /* we already have 'r' */ r = rand() % (N + 1); } vektor[im++] = r + 1; /* +1 since your range begins from 1 */ is_used[r] = 1; } assert(im == M); 

Genera el primer y segundo dígito por separado. Mezcle más tarde si es necesario. (syntax de la memoria)

 int vektor[10]; int i = 0; while(i < 10) { int j = rand() % 10; if (vektor[j] == 0) { vektor[j] = rand() % 10 + j * 10; i ++;} } 

Sin embargo, los números estarán casi separados por n, 0

O bien, debe mantener los números ordenados ( O(n log n) ), de modo que se pueda verificar rápidamente la presencia de nuevos generados ( O(log n) ).