Generar permutaciones aleatorias

[anadelaisla]

Hola, tengo que hacer un programa que me genere 10000000 permutaciones aleatorias de los 6 primeros numeros naturales y que imprima cuantas de ellas estan ordenadas:

Lo he implementado así, tengo qutilizar random_shuffle:

#include <iostream>
#include <algorithm>
#include <vector>
#include <cmath>

using namespace std;


void permutaciones (vector<int>& v)
{

const size_t n = sizeof v / sizeof *v;
random_shuffle(v, v + n);
int cont;
if (prueba_ordena(v))
cont++;

}
bool prueba_ordena(const vector<int>& v)
{
int i=0;
for(int k=1; k< v.size(); ++k){
if(v[k]<v)
return false;
i=k;
}
return true;
}
int main()
{
vector<int>v(6);
for(int i=0; i<6; ++i)
v[i]=i;
for (long i=0; i<10000000; ++i)
permutaciones(v);
}

Pero me da error en las lineas de random_shuffle, será que no lo ultilizo bien?? si alguien me ayuda...
Gracias de antemano.

[yalmar]

Hola Ana,

Disculpame, pero tu programa simplemente no pasa ni como pseudocódigo, tu lo hiciste? en fin.
Tratare de ayudarte, puedes usar la funcion next_permutation de la STL

Código: Seleccionar todo

#include <algorithm>
#include <iostream>
#include <vector>

using namespace std;

int main() {
  vector<int> v_int; 
  int N = 6; // n first natural numbers

  for (int i = 1; i<=N; i++)
    v_int.push_back(i);

  /* Use a do/while loop instead of the normal while loop becuase
     the first entry will be skipped if you call next_permutation
     first */
  int cnt = 0;
  do {
    // There should be n! (4*3*2*1) entries.

    cout << ++cnt << ": ";

    // Print out the vector.

    for(unsigned int x = 0; x < v_int.size(); x++)
      cout << v_int[x];

    cout << endl;
  } while(next_permutation(v_int.begin(), v_int.end()));


  return 0;
}


y la función random_shuffle simplemente redistribuye los elementos de un array randomicamente y su forma de uso con vector es:

Código: Seleccionar todo

random_shuffle(v.begin(), v.end());


si quieres utilizarlo de la forma que pones

Código: Seleccionar todo

random_shuffle(v, v + n);


en ese caso v debería ser un iterador.

Ahora, 10000000 de permutaciones no puedes conseguir con 6 digitos, verifica el enunciado de tu problema.

Espero haberte ayudado.

Salu2

[anadelaisla]

Ok, ya lo tengo claro, y lo del enunciado del problema aunque sea raro porque no puede ser, es así como viene dado.
Muchas gracias.
Un saludo.

[anadelaisla]

Hola, mira al final lo he hecho así que creo q esta bien, no? al menos no me da ningún error y se me ejecuta correctamente, de lo que no estoy segura es de si, es normal q sean 14080 permutaciones las q estan ordenadas, eso puede ser?? o es extraño?

#include <iostream>
#include <algorithm>
#include <vector>

using namespace std;


bool prueba_ordena(const vector<int>& v);
long permutaciones (vector<int>& v);

long permutaciones (vector<int>& v)
{

random_shuffle(v.begin(), v.end());
if (prueba_ordena(v)==1)
return 1;
else
return 0;
}


bool prueba_ordena(const vector<int>& v)
{
int i=0;

for(int k=1; k<6; ++k){
if(v[k]<v[i])
return false;
i=k;
}
return true;
}


int main()
{
vector<int>v(6);
int cont=0;

for (int k=0; k< v.size(); ++k)
v.push_back(k);
for (long i=0; i<10000000; ++i)
cont += permutaciones(v);
cout << cont << endl;
}

Gracias de antemano.