Foros del Web » Programación para mayores de 30 ;) » C/C++ »

[SOLUCIONADO] Problema extraño al intentar randomizar una cola

Estas en el tema de Problema extraño al intentar randomizar una cola en el foro de C/C++ en Foros del Web. Hola amigos: Llevo años programando pero vengo de otros lenguajes y aqui tengo algun problemita que ya me tiene aburrido Basicamente es conceptual..... intento mezclar ...
  #1 (permalink)  
Antiguo 17/06/2014, 17:55
Avatar de Italico76  
Fecha de Ingreso: abril-2007
Mensajes: 3.303
Antigüedad: 17 años, 3 meses
Puntos: 292
Problema extraño al intentar randomizar una cola

Hola amigos:

Llevo años programando pero vengo de otros lenguajes y aqui tengo algun problemita que ya me tiene aburrido

Basicamente es conceptual..... intento mezclar una "cola" que tiene cartas con una idea que tuve de crear otra (doble) e insertar en esta segunda arriba o abajo segun tiro un dado.

La cuestion es que no mezcla nada!!!

Se que la mas facil es crear un vector y aplicarle un shuffle() pero quisiera saber si fuera posible QUE estoy haciendo mal......

Como creo voy a actualizar el codigo que tengo publicado en otro hilo....... lo dejo como referencia del codigo global pero el metodo mezclar() actual (que no funciona) lo coloco aqui:

Código C++:
Ver original
  1. void mezclar()
  2.     {
  3.  
  4.         Baraja carta;
  5.         int up_down;
  6.         std::deque<Baraja> nuevo_mazo;         
  7.        
  8.         // copio el mazo
  9.         for (int i=0;i<54;i++)
  10.         {
  11.             carta = cartas.front();
  12.             cartas.pop();
  13.             nuevo_mazo.push_front(carta);          
  14.         }  
  15.  
  16.         for (int i=0;i<1000;i++)
  17.         {
  18.             // decido si coloco la carta arriba o abajo (cada vez)
  19.             up_down = rand() % 2;
  20.  
  21.             // saco siempre del mismo lado
  22.             carta = nuevo_mazo.front();
  23.             nuevo_mazo.pop_front();
  24.  
  25.             if (up_down==0){
  26.                 nuevo_mazo.push_front(carta);
  27.                 //cout << "arriba\n";
  28.             }
  29.             else{
  30.                 nuevo_mazo.push_back(carta);
  31.                 //cout << "abajo\n";
  32.             }
  33.         }
  34.        
  35.         // lo copio al mazo original
  36.         for (int i=0;i<54;i++)
  37.         {
  38.             carta = nuevo_mazo.front();
  39.             nuevo_mazo.pop_front();
  40.             cartas.push(carta);
  41.         }          
  42.     };

OBVIAMENTE... como sigue SI funciona...... aunque quisiera ENTENDER porque de la primera forma no

Código C++:
Ver original
  1. // SI funciona bien usando vectores
  2. void mezclar()
  3.     {
  4.  
  5.         Baraja carta;
  6.         vector<Baraja> nuevo_mazo (54);        
  7.         int up_down;               
  8.        
  9.         // copio el mazo
  10.         for (int i=0;i<54;i++)
  11.         {
  12.             carta = cartas.front();
  13.             cartas.pop();
  14.             nuevo_mazo.at(i) = carta;          
  15.         }  
  16.  
  17.         random_shuffle (nuevo_mazo.begin(), nuevo_mazo.end());
  18.        
  19.         // lo copio al mazo original
  20.         for (int i=0;i<54;i++)
  21.         {
  22.             carta = nuevo_mazo.at(i);          
  23.             cartas.push(carta);
  24.         }          
  25.     };

Dejo entonces referencia al resto del codigo del otro hilo
GRACIAS!
__________________
Salu2!

Última edición por Italico76; 17/06/2014 a las 18:13
  #2 (permalink)  
Antiguo 17/06/2014, 18:47
 
Fecha de Ingreso: junio-2008
Ubicación: Seattle, USA
Mensajes: 733
Antigüedad: 16 años
Puntos: 61
Respuesta: Problema extraño al intentar randomizar una cola

No puedo responder con argumentos solidos y matematicos, pero para mi en la primera solución le estas dando mucha importancia a los primeros elementos en desmedro de los ultimos. Si en la primera vez la posibilidad de que el elemento se quede en donde mismo es 1/2 y la posibilidad de irse al final es tambien 1/2, lo malo que veo, es que en la 2da vuelta, el primer elemento puede volver a ser el primero con la misma probabilidad y por tanto, en el fondo vuelve a ser probable que se quede alli.

Si el elemento que está al ultimo tuviera voz, seguro reclamaría que el no tiene casi ninguna posiblidad de ser removido de su lugar, mientras que el primero siempre tiene varias alternativas de serlo. Lo que no sabe este ultimo es que el primero también esta sufriendo del mismo problema, vale decir, tiene mucha probabilidad de quedarse donde mismo.

No sé si es esto lo que ocurre finalmente, o sea, pocos movimientos, pero eso intuyo que pasa. ¿Pasa esto?

Finalmente, no es exactamente lo que haces, pero al menos tiene relación: randomizar "mal" es un clásico problema y Knuth presenta la manera adecuada de hacerlo: intercambiar el elemento i-esimo con el mismo o con cualquiera de los que les sigue.
Ver mas en este link: http://goo.gl/IXln1l.
__________________
Visita mi perfil en LinkedIn

Última edición por CalgaryCorpus; 17/06/2014 a las 19:12
  #3 (permalink)  
Antiguo 17/06/2014, 19:12
Avatar de Italico76  
Fecha de Ingreso: abril-2007
Mensajes: 3.303
Antigüedad: 17 años, 3 meses
Puntos: 292
Respuesta: Problema extraño al intentar randomizar una cola

Cita:
Iniciado por CalgaryCorpus Ver Mensaje
No puedo responder con argumentos solidos y matematicos, ...

No sé si es esto lo que ocurre finalmente, o sea, pocos movimientos, pero eso intuyo que pasa. ¿Pasa esto?
SOS UN GENIO

Es EXACTO lo que pasa..... empieza randomizando y luego aunque itere 100.000 o 1.000.000 de veces no hay cambio con los elementos que estan mas alla de los extremos de la cola.


Gracias por tu aporte a mi entendimiento
__________________
Salu2!
  #4 (permalink)  
Antiguo 17/06/2014, 19:15
 
Fecha de Ingreso: junio-2008
Ubicación: Seattle, USA
Mensajes: 733
Antigüedad: 16 años
Puntos: 61
Respuesta: Problema extraño al intentar randomizar una cola

Edité tardiamente mi post. Puse unos links que pueden ser de interés (ver más arriba)
__________________
Visita mi perfil en LinkedIn

Etiquetas: cola, extraño, funcion, int, programa
Atención: Estás leyendo un tema que no tiene actividad desde hace más de 6 MESES, te recomendamos abrir un Nuevo tema en lugar de responder al actual.
Respuesta




La zona horaria es GMT -6. Ahora son las 07:23.