Autor Tema: Re: 12/02/03 - Bajo/Medio - Vectores - Permutaciones (Leído 2038 veces)

gothmog · « **en:** Miércoles 12 de Febrero de 2003, 15:28 »

Teniendo un vector unidimensional de n elementos, los cuales queremos permutar aleatoriamente (uso de random).

Ejemplo:

V=[1,2,3,4,5,6] ---> V'=[4,2,3,1,6,5]

Si os parece muy facil, podriamos extenderlo a una matriz de MxN dimensiones, que aunque es mas de lo mismo, creo que plantea mayor dificultad:)

adocrates

Vamos, y cual es la complejidad ?

gothmog

Citar

Originalmente publicado por adocrates
Vamos, y cual es la complejidad ?

???

Si es un vector es baja/media, quiza media. Lo de la matriz lo digo por si os parece mu facil, q no se q nivel tendreis.

O te refieres a la complejidad algoritmica?

gothmog

Bueno, 1 mes despues os traigo la respuesta (si es que alguien la lee y le interesa, pq este foro esta poco mas que muerto:()

void permuta(int B[], int N){ // N = longitud del vector.
int x,i,j, cota;
int *Aux = new int[N]; // Vector auxiliar

srand(time(NULL)); // Valor semilla para rand() Requiere el archivo time.h

for(i=0; i<N; i++){ // Copia el vector B en Aux
Aux = B;
}

for (i=0; i<N-1; i++){
x = rand()%(N-i);
cota = (N-1)-i-x;
B = Aux
;

for (j=0; j<cota; j++){
Aux
= Aux[x+1];

x++;
}
}
B[N-1] = Aux[0];
delete []Aux;
}

Y un codigo de ejemplo para probarlo:

#pragma hdrstop
#include <iostream.h>
#include <conio.h>
#include <time.h>

#pragma argsused
int main(int argc, char* argv[])
{
int c;
const n=1000;
int *array = new int[n];

for(c=0; c<n; c++){
array[c] = c+1;
cout << array[c] << " ";
}
cout << endl;

permuta(array,n);

for(c=0; c<n; c++){
cout << array[c] << " ";
}
cout << endl;

while (!kbhit());
delete []array;
return 0;
}