Club Desarrolladores

El problema:

Se necesita una función que retorne un vector (array de una dimensión) de N elementos, cada uno de ellos siendo un entero que no puede estar repetido en dicho array. A su vez, estos elementos no deben estar ordenados de tal manera que al recorrer secuencialmente el array nos encontremos con una secuencia aleatoria de números.

Por ejemplo, para un vector de 5 elementos, el vector retornado por la función debería ser similar a este:

La solución:

Crearemos una función para cumplir con lo requerido. La función, que llamaremos generarVectorAleatorio, solicitará un entero (positivo) que representará la cantidad de elementos del vector que retornara la función.
En cuanto al algoritmo, lo primero por hacer es crear un vector de N elementos e inicializar el mismo de tal manera que al indice i le corresponda el valor i. Con ello ya conseguimos tener un vector de N elementos únicos o dicho de otra manera: no repetidos. Para conseguir esto hacemos uno de la STL, más precisamente de la clase Vector. Ahora simplemente hace falta "desordenarlos".
Es asi que valiendonos de este objeto lo que hacemos es obtener un indice aleatorio, y por lo tanto un valor, que vamos a asignar al vector en posiciones secuenciales para asi luego de hacer esto, eliminar del vector ordenado el indice antes utilizado.
De esta manera lo que estariamos haciendo es "sacar" aleatoriamente un elemento del vector ordenado y "ponerlo" uno detras del otro en el vector a retornar, cumpliendo de esta manera con lo requerido.

#include <iostream>
#include <vector>

using namespace std;
int* generarVectorAleatorio(int n);

int main(int argc, char *argv[]){
	cout << "Procesando..." << endl;
	int n = 100000;
	clock_t t0;
	double t;
	t0 = clock();
	int* v = generarVectorAleatorio(n);
	t = double(clock() - t0)/(double)CLK_TCK;
	//Opcional: mostrar listado de numeros unicos
	/*
	for(int i = 0; i < n; i++)
		cout << v[i] << endl;
	*/
	delete v;
	cout << endl << "Cantidad de numeros unicos: " << n << endl;
	cout << "Tiempo de procesamiento: " << t << " seg"<< endl;
	return 0;
}

int* generarVectorAleatorio(int n){
	srand((unsigned)time(0));
	int i, j, *v = new int[n];
	vector<int> vec(n);
	for(i = 0; i < n; i++) vec[i] = i;
	for(i = 0; i < n; i++){
		j = static_cast<int> ((double)rand()*(double)(vec.size()) / ((double)RAND_MAX+1.0));
		v[i] = vec[j];
		vec.erase(vec.begin()+j);
	}
	return v;
}

Resultados:

El algoritmo no es de lo más optimo, sin embargo no es excesivo el tiempo necesario para crear el vector. Aqui coloco unos resultados para vectores grandes (100000 elementos) ejecutados en una Pentium IV.


Espero que les sirva. Saludos.

Página 01 de 01 | Versión completa