Generar numeros aleatorios sin que se repitan

Iniciado por Mecanma, 17 Octubre 2019, 05:44 AM

0 Miembros y 1 Visitante están viendo este tema.

Mecanma


Así se pueden generar numeros sin repetirlos.

Explicación:

se genera un numero aleatorio en aux
se recorre el arreglo buscando un numero igual
si se encuentra se genera otro y se inicializa la variable j(la del for interior) para asegurarse de que no haya un repetido.

Recuerda que el limite de la generación no sea menor al tamaño del arreglo eso podría conllevazr a un error.



const int Max = 100, Limite = 101;
typedef int tArray[Max]


tArray array;
int aux = 0, num = -1;

   

    for(int i = 0;i<Max;i++){

int aux = 1 + rand()%(Limite - 1);

for(int j = 0;j < i;j++){

if(aux == array[j]){

aux = 1 + rand()%(Limite - 1);
j=0;
}

}

array[i]= aux;

}

Serapis

#1
No.

Cuando buscas la presencia de un número y luego generas otro, incurres en dos fallos:
1º - Quién te dice que sea el único igual a ese?. Esto puede soslayarse, si previamente la lista está vacía, en cambio la siguiente objección es el cuello de botella.
2º - Quién te asegura que el nuevo número, no conste ya (o previamente a la posición), buscar que no se repite supone volver a buscar desde el principio, y acabas en un bucle tanto más largo cuanto más grande sea el array... no infinito, si no está mal programado.
'Tu solución' en el mejor de los casos está en un tiempo (n²/2)-1, en el peor cuasi infinito.

La solución es mucho, mucho, mucho más sencilla... además aunque no te lo parezca a diario, incluso los niños pequeños la ponen en práctica de una forma abstracta, no reparan en ello. La mayor parte de los algoritmos, no son más que llevar al terreno de la informática el quehacer diario, que nos pasa desapercibido.

Sea un array de 100 elementos... del 0 al 99...
Paso 1: Llenar el array. Meter todos los que interesan/participan en el saco.

Max = 100
bucle para i desde 0 a max -1
  tArray(i) = i
siguiente

Ya hemos hecho la mitad del trabajo... qué te parece?. Y más fácil imposible...

Paso 2: Barajarlos, para desordenarlos... Esto es, agita el saco con todas las papeletas dentro.
Se recurre a la generación de números aleatorios, pero en este caso no importa (en absoluto) que se repitan....

index = -1
bucle para i desde Max-1 hasta 1 retrocediendo
    aux = aleatorio(entre 1 'e' i)   //obtener al azar un índice entre 1 el más alto no buscado aún
    // intercambiar valores entre el que está en última posición (actualmente, es decir 'i') y el que está en el índicde obtenido al azar
    num = tArray(aux)
    tArray(aux) = tArray(i)
    tArray(i) = num
siguiente


Listo....
El primer bucle (paso 1) sería una función GenerarListaRandom(int Max) que antes de salir, invoca el paso 2
El segundo bucle (paso 2) sería una función BarajarLista // se le podría indicar cuantas veces barajar, seguidas en la misma función, basta una o dos veces...

Paso 3: Es usarlos.. cuando haga falta. Esto es, sacar una papeleta del saco (ya no se puede usar, esta fuera).
Paso 4: No quedan números por usar. Cuando se sacaron todos del saco, volver a meterlos e ir al paso 2. (dentro de la propia función).

int = funcion GetValorDeListaRandom
    // paso 4:
     si (index = (max-1))  // Max = 100 en tu ejemplo
         // index = -1  // Meterlos de nuevo en el saco. ubicar esta línea al inicio de la función barajar, así se resetea cuando se genera una nueva lista.
         llamar a BarajarLista   // ir al paso 2.     
     fin si

     index +=1
    devolver tArray(index)
fin funcion


En negrita, el prosaico texto de los pasos, como lo explicarías a un niño.

Lo mejor de todo, aparte de la  enorme simplicidad y que ya lo conocías (lo habrás usado decenas de veces en tu vida, sin darte cuenta) es que el tiempo es sólo 2n;  2*100 = 200, siempre. No hay caso peor ni mejor. En tu ejemplo era en el mejor de los casos: (n²/2)-1; 100*100/2 = 4.999

En resumen... los números se generan una sola vez al principio, y luego se usan sin repetición asegurada, hasta acabar con el último del array. Luego se vuelven a barajar y vuelta a poder usarlos sin repetir durante todo ese tiempo.

Es fácil modificar el algoritmo, para permitir que algunos se repitan x veces, cosa que en determinadas situaciones es lo adecuado. Por ejemplo en juegos el nivel de dificultad de algun evento se basa a menudo en la frecuencia con que aparecen unos respecto de otros...