Generar x numeros aleatorios sin repeticion en c++

Archivado
Buenas quiero generar un cierto número de números aleatorios, que vayan desde el 0 hasta el el hasta el tamaño. He hecho este código y no se me repiten;

void Tablero::Aleatorio(){
   /*int tam=filas*columnas,c=0;
   Matriz m_aux(filas,columnas);
   m=m_aux;
   //int col=m.Columnas();
   for(unsigned int i=0;i<filas;i++){
      for(unsigned int j=0;j<columnas;++j){
         m.Set(i,j,c);
         c++;
      }
   }*/
   int tam=filas*columnas,fil=0,col=0,x;
   bool band;
   Matriz m_aux(filas,columnas);
   m=m_aux;
   int *v=new int[tam];
   for(int i=0;i<tam;++i){
      x=rand()%tam;
      if(i>0){
         while(band){
            if(EstaElemento(v,i,x))
               x=rand()%tam;
            else
               band=false;
         }
      }
      band=true;
      v[i]=x;
      m.Set(fil,col,x);
      if(col==columnas){
         col=0;
         ++fil;
      }
      else
         ++col;
   }


Con la funcion EstaElemento():

bool Tablero::EstaElemento(int *v,unsigned int tam, int x){
   
   bool band=false;
   for(unsigned int i=0;i<tam && !band;i++){
      if(v[i]==x)
         band=true;
   }
   
   return band;
}

Se me repiten números y no se porque. También guardo los números aleatorios generados en una matriz de tamaño filas*columnas.

Un saludo
¿A qué te refieres con que se repiten?

No me he enterado de nada...
Veo que para generar los números usas la función rand(). La verdad es que esa función no es demasiado buena ya que suele generar siempre los mismos números (a mí me pasaba cuando implementé "el juego de la vida" en c). Prueba a generarlos de otra forma, jugando con el tiempo del sistema, por ejemplo.
Es que la función rand es una función pseudo-aleatoria, por lo que no llega a ser aleatoria del todo. Lo que se puede hacer para aumentar la aleatoriedad es utilizar la función srand() que lo cambia es la semilla del rand().

La semilla le puedes inicializar con el tiempo del sistema por ejemplo:

unsigned seed = (unsigned)time(NULL);


Para maximizar esta pseudoaleatoriedad lo más pobile puedes cambiar la semilla en cada iteración, simplemente aumentando semilla en uno, llamas a srand, y finalmente a rand:

seed++;
srand(seed);
x = rand() % tam;



Incluso puedes meter el seed++ dentro del for:

for(int i = 0; i < tam; i++, srand(seed++))
{
   x = rand() % tam;
   .
   .
   .
}
Creo que a lo que se refiere él es que no se genere otra vez el mismo número aleatorio, por ejemplo, entre 4 números, que le salga por ejemplo "0 3 1 2", pero nunca "0 3 1 3".

El código tiene un bug que creo que causa un problema, compruevas "band" sin asignarlo antes.
bool band;

while(band){


La solución que creo más fácil es llenar un vector (o con un array como el del codigo que has puesto tambíen se puede hacer) con números y generar índices para sacar los números aleatorios y luego borrarlos del vector/array.

#include <cstdlib>
#include <ctime>
#include <iostream>
#include <vector>

using namespace std;

// Genera "a_generar" números aleatorios entre 0 y "maximo"
void GenerarNumerosAleatoriosSinRepetir(int maximo, int a_generar)
{
    vector<int> numeros;

    // Llenar el vector con los numeros del minimo al máximo
    for (int i = 0; i < maximo; i++)
    {
        numeros.push_back(i);
    }

    // Generar numeros
    for (int i = 0; i < a_generar; i++)
    {
        if (numeros.size() > 0)
        {
            /* Generar una posición en el vector de números
             * y coger el número de aquella posicion y borrarlo
             * para que no vuelva a aparecer más.
             */
            int indice = rand() % numeros.size();

            cout << "Numero aleatorio: " << numeros[indice] << endl;
            numeros.erase(numeros.begin() + indice);
        }
        else
        {
            cout << "No se pueden generar mas numeros." << endl;
        }
    }
}

int main()
{
    srand(time(NULL));
    GenerarNumerosAleatoriosSinRepetir(10, 5);
    return 0;
}


PD: El código no funcionará correctamente con más de 0x7FFF = 32767 (valor mínimo de RAND_MAX) en algunos compiladores. Para solucionar esto supongo que solo hace falta "juntar" los valores de varios rand().
Ahhhhhhhhhhhh je.

Claro, si no cambias la semilla la secuencia siempre es la misma (lógico). Lo mejor es cambiarla al inicio del programa. NO la cambies en cada iteración, NO aumentas la aleatoreidad, la disminuyes.

Saludos.
Quiza me he hecho un lio explicandolo, voy a poner un ejemplo. Tengo un array de tamaño 10,pues bien quiero generar una secuencia de numeros aleatorios del 0-9 sin que se repitan, así el array podría ser: 6,7,2,9,3,8,0,1,5,4.

GameZelda, es una alternativa que tambien pense, pero al fin y al cabo tendria el mismo problema, puesto que debo de generar números que no se repitan para sacar el vector. Y en lo referente al bug, creo que el problema que dices no es tal, porque en la primera iteracion del bucle no se comprueba el band, ya que la i no es mayor que 0, por lo que no entra en el if y hace la asignación antes de comprobar la bandera.

PD:Por el srand(time(0)), que es como lo tengo puesto en el programa principal no es. Se me olvido comentar que tenia esa función puesta.
Lo que tu quieres no son números aleatorios... tu lo que quieres es desordenar una secuencia de números. Lo cual es MUY distinto.

Genera un vector con el rango que quieras y usa std::random_shuffle.

- ferdy
makelele24 está baneado por "troll multinicks"
Si lo que necesitas es hacerlo tú mismo, una idea muy sencilla que se mantiene lineal en promedio para vectores pequeños es generar posiciones aleatorias y meter números fijos, en vez de generar números aleatorios y meterlos en posiciones fijas.
Yo para hacer eso ponía todos los números ordenados en un array, y luego lo "barajaba" [+risas] partiéndolo por una posición aleatoria y tomando un numero de cada uno de los sub-arrays con un rand%2. Me iba muy bien con vectores muy grandes.

Dicho esto, he visto la el método que dice ferdy y hace justo lo que quieres y sin complicarte más la vida, asi que ya sabes:
http://www.dreamincode.net/code/snippet596.htm
makelele24 escribió:Si lo que necesitas es hacerlo tú mismo, una idea muy sencilla que se mantiene lineal en promedio para vectores pequeños es generar posiciones aleatorias y meter números fijos, en vez de generar números aleatorios y meterlos en posiciones fijas.


Excepto que eso no hace que las distintas distribuciones sean equiprobables. Es un error muy común.

Habría que hacer algo similar a lo que hace el algoritmo Fisher-Yates (o Knuth Shuffling).

Saludos.
makelele24 está baneado por "troll multinicks"
Ferdy escribió:
makelele24 escribió:Si lo que necesitas es hacerlo tú mismo, una idea muy sencilla que se mantiene lineal en promedio para vectores pequeños es generar posiciones aleatorias y meter números fijos, en vez de generar números aleatorios y meterlos en posiciones fijas.


Excepto que eso no hace que las distintas distribuciones sean equiprobables. Es un error muy común.


No me había parado a pensar si lo era o no (simplemente era una idea muy sencilla que puede intentar implementarla el OP), pero ahora que lo dices, no veo el porqué la permutación resultante no es aleatoria.

De hecho veo que dicho algoritmo lo propuso también Knuth antes que el Fisher-Yates y no está sesgado.

http://en.wikipedia.org/wiki/Shuffle#Sh ... algorithms
http://en.wikipedia.org/wiki/Knuth_shuffle
makelele24 escribió:No me había parado a pensar si lo era o no (simplemente era una idea muy sencilla que puede intentar implementarla el OP), pero ahora que lo dices, no veo el porqué la permutación resultante no es aleatoria.

De hecho veo que dicho algoritmo lo propuso también Knuth antes que el Fisher-Yates y no está sesgado.

http://en.wikipedia.org/wiki/Shuffle#Sh ... algorithms
http://en.wikipedia.org/wiki/Knuth_shuffle


Knuth no tenía ni un año cuando Fisher y Yates lo publicaron......

Lo que tu has descrito NO es el algoritmo que esta gente propone. Por lo menos de la descripción no se infiere que tengas cuidado de no repetir posiciones ni cómo se hace.

- ferdy
makelele24 está baneado por "troll multinicks"
Ferdy escribió:
makelele24 escribió:No me había parado a pensar si lo era o no (simplemente era una idea muy sencilla que puede intentar implementarla el OP), pero ahora que lo dices, no veo el porqué la permutación resultante no es aleatoria.

De hecho veo que dicho algoritmo lo propuso también Knuth antes que el Fisher-Yates y no está sesgado.

http://en.wikipedia.org/wiki/Shuffle#Sh ... algorithms
http://en.wikipedia.org/wiki/Knuth_shuffle


Knuth no tenía ni un año cuando Fisher y Yates lo publicaron......


Me refería a que aquí:

http://en.wikipedia.org/wiki/Shuffle#Sh ... algorithms

parece indicar que el primer algoritmo popularizado por Knuth era ése (o simplemente se le llama "primer algoritmo").

Lo que tu has descrito NO es el algoritmo que esta gente propone. Por lo menos de la descripción no se infiere que tengas cuidado de no repetir posiciones ni cómo se hace.


Duh. Es obvio que hay que evitar repeticiones, no me tomes por noob. De hecho, por eso he dicho que es lineal en promedio para vectores pequeños (si simplemente vuelves a generar un número aleatorio hasta que no repites, que es la idea que le intentaba dar al OP).

En caso contrario hubiera dicho que el algoritmo es exactamente lineal (tanto mejor, promedio como peor caso) y para cualquier tamaño.

Por tanto, sí que se infiere de la descripción que hay que tener cuidado de no repetir posiciones.
13 respuestas
Archivado
Volver a Software libre