Foro de elhacker.net

Hola, tengo el siguiente fragmento de programa:

No entiendo porqué se pasa wMazo[][13], es decir, porque se deja el primer corchete sin datos, ¿no debería ser wMazo[4][13] ?

Gracias.

Esa funcion da problemas, es muy probable que el mazo generado tenga 2 cartas identicas.

Lo ideal esque generes el mazo ordenado y luego hagas intercambios aleatorios.

En cuanto a la pregunta, el primer corchete es opcional. Puedes ponerlo o no, el segundo corchete es necesario para que el compilador traduzca los dos [][] en uno solo.

Como dice amchacon, tu código genera cartas repetidas ( por mera cuestión de estadística es más probable el caso en el que mazo tiene cartas repetidas que el caso en el que todas la cartas son distintas ).

La solución a ese problema pasaría por crear primero un mazo ordenado, lo cual es fácil de generar, y después mezclarlo mediante una serie de permutaciones ( generar un par X, Y e intercambiar sus cartas ). El número de permutaciones necesarias para asegurar una mezcla adecuada variará en función del algoritmo que elijas.

Puedes declararla así pero no tendrá efecto ya que en C cuando un argumento es de tipo array lo que recibe la función es la dirección en memoria de (un puntero a) su primer elemento. Si el array es de tipo "T [N]" la función recibe un puntero de tipo "T *".

Utilizando tu caso como ejemplo la función la puedes declarar en cualquiera de las dos formas:

void baraja( int wMazo[4][13] );
 
/* O tambien */
void baraja( int wMazo[][13] );

Pero no importa ya que la función se procesa como si su declaración fuera (y es):

void baraja(int (*wMazo)[13]);

En buen plan: lo reviso con cuidado y no veo como se pueda duplicar una carta. ¿Se me escapa algo?

Un saludo

Cierto. Vi los random y me cegué jejejeje.

El problema es que llegar a tardar un tiempo infinito en mezclar el mazo.... si una de las combinaciones (fila, columna) no se da hasta pasadas miles de iteraciones... pues ahí que te quedas esperando.

Tienes razón Rir, que fallo más tonto :-X

De todas formas, no me gusta ese modo de barajar como ya dije. Me parece mas natural de este modo:

1º Te generas el mazo ordenado.
2º Coges dos elementos al azar y los intercambias
3º Repites el paso 2 tantas veces como creas necesario. Para un mazo tienes de sobra con 1000 iteraciones.

De hecho en C++ (que no C) puedes hacer los dos ultimos pasos en un sola función:
http://www.cplusplus.com/reference/algorithm/random_shuffle/

Para barajar, yo lo que hago es ir cogiendo elementos, e ir colocándolos en un array en posiciones aleatorias.

O lo que es lo mismo, ir cogiendo elementos aleatorios, e ir introduciéndolos en el array.
Así para barajar en un tiempo finito.

Pero estás duplicando el array así... Para eso intercambias y ya esta.

Por supuesto, pero siempre se busca la máxima eficiencia.

Suponte un servidor de poker con millones de usuarios, dado que tienes que hacer millones de mezclas conviene perder el menor tiempo posible.

Y confiar en el "azar" no suele ser muy buena práctica. Es una buena costumbre garantizar que el algoritmo termine en tiempo finito incluso en el peor caso posible, nos ayudará a evitarnos algunos errores "oscuros".

Como curiosidad de algoritmos basados en el azar, tenemos un algoritmo de ordenación que usa una técnica similar: El bogosort (o stupidsort). Que viene a ser el siguiente:

Dado un conjunto de números desordenados:
     1º Comprobar que esten ordenados, si lo estan termina.
     2º Mezclar los numeros aleatoriamente.

Y aquí una implementación de este algoritmo en C++:

#include <iostream>
#include <algorithm>
#include <ctime>
#include <iterator>
using namespace std;
 
void bogo_sort(vector<int>&);
 
int main()
{
    vector<int> Numeros;
    srand(time(NULL));
    int N;
 
    cout<<"Introduzca numero de elementos a ordenar: ";
    cin>>N;
 
    Numeros.resize(N);
 
    for (int i = 0; i < 10;i++) // 10 intentos
    {
        generate(Numeros.begin(),Numeros.end(),rand); // relleno el vector de numeros aleatorios
 
          // Muestra los numeros generados por pantalla:
//        copy(Numeros.begin(),Numeros.end(), ostream_iterator<int>(cout, " ")); 
 
        time_t inicio = clock();
 
        bogo_sort(Numeros);
 
        time_t fin = clock();
 
        cout<<(double)(fin-inicio)/(CLOCKS_PER_SEC)<<"s en ordenar "<<N<<" elementos"<<endl;
 
        // muestra los numeros ordenados por pantalla
//        copy(Numeros.begin(),Numeros.end(), ostream_iterator<int>(cout, " "));
 
       // cout<<endl;
    }
    return 0;
}
 
bool enOrden(vector<int> &x) {return adjacent_find(x.begin(), x.end(), greater<int>()) == x.end();}
 
void bogo_sort(vector<int> &Numeros)
{
    while (!enOrden(Numeros))
    {
        random_shuffle(Numeros.begin(),Numeros.end());
    }
}
 

Dile que genere 10 elementos. A mí los tiempos me salen muy dispares (desde 0,063 hasta 5 segundos). Eso en rangos pequeños, cuanto mayor sea el rango, mayor será la dispersión.

En resumen, trabajar basado en la suerte nos da unos programas muy impredecibles y inestables. A mí personalmente no me gusta nada ;D

Creo que es obvio que se hace en un array temporal >.>

¿Y después lo vuelves a copiar en el array original? :huh:

El caso, es que cada vez que coges un elemento, se reduce el próximo número máximo del rand() en 1. Si un elemento que escoges, ya ha sido cogido, se va al siguiente, así hasta que no haya sido cogido...

¿Comor?

¿Y si cojo un elemento del principio? ¿No puede adceder a los finales?

Quiero ver una implementación ^^

¿Si coges un elemento del principio? Ese proceso se repite N veces, siendo N el tamaño del array.

EDITO:

template<class T>void barajar(vector<T> &v){
    vector<T> t;
    int r=0;
    while(v.size()>0){
        t.push_back(v[r=rand()%v.size()]);
        v.erase(v.begin()+r);
    }
    v = t;
}

Por ejemplo, manejando vectores.

Yo también lo quiero ver.

En el método que propuse, desordenar un cierto número de veces, 10 000 en el caso que propongo, con lo que controlamos las iteraciones, una implementación simple, nada rebuscada, arroja valores por debajo de 0.02s, más cercanos al 0.015s:

#include<stdio.h>
#include<stdlib.h>
#include<time.h>
#define MAX_DESORDEN 10000
 
 
int main (void){
  int mazo[4][13] = {0};
  srand((unsigned) time(NULL));
  int i,j,k=0,x1,y1,x2,y2,temp;
  ///puts("Mazo ordenado:\n");
  for (i=0;i< 4; i++){
    ///puts("\n");
    for (j=0;j<13 ;j++,k++ ){
      mazo[i][j]=k;
      ///printf("%d  ",mazo[i][j]);
    }
   }
 
  for (i=0;i<MAX_DESORDEN;i++){
    x1=rand () %4;
    y1=rand () %13;
    x2=rand () %4;
    y2=rand () %13;
    temp=mazo[x1][y1];
    mazo[x1][y1]=mazo[x2][y2];
    mazo[x2][y2]=temp;
  }
  /** activame para ver el mazo desordenado **/
  /*puts("\n\nMazo desordenado:\n");
  for (i=0;i< 4; i++){
    puts("\n");
    for (j=0;j<13 ;j++,k++ )
      printf("%d  ",mazo[i][j]);
   }*/
   return EXIT_SUCCESS;
}

Salu2!.

Al parecer ya ha editado su post con la implementación... Pero la propuesta de Ivan no es una solución eficiente (intenta mezclar 10 millones de elementos, a mí me tardó 4 minutos...).

Por cierto Leo, haciendo pruebas me he dado cuenta que hay una forma un poco más sencilla de mezclar. No es necesario definirte una constante con el numero de iteraciones:

for (int i = 0;i < v.size(); i++)
    swap(v[i],v[rand()%A.size()]);

Dicho de otra forma, recorro el array y cada posición la intercambio con otra aleatoria. De esa forma tengo la garantía de tener el array desordenado y no tengo que definir una constante "a ojo".

La función swap no es más que:

void swap(int &a,int &b)
{
    int c = a;
    a = b;
    b = c;
}

Buena observación amchacon, muy buena  ;-) ;-) ;-)

...Pero me sentiría más tranquilo barajando un par de veces más para evitar las posibles coincidencias de i con el valor obtenido del rand y que existan cartas que acaben quedándose en las mismas posiciones :laugh:

Ya sólo nos queda ponerlo en práctica echándonos unas partiditas de póker ;)

Hay que ver la soluciones, cada vez más optimizadas, que nos salen cuando nos dejan......

Mi adaptación al C de tu idea:

#include<stdio.h>
#include<stdlib.h>
#include<time.h>
 
int main (void){
  int mazo[52] = {0};
  srand((unsigned) time(NULL));
  int j,x,temp;
  ///puts("Mazo ordenado:\n");
    for (j=0;j<52 ;j++)
      mazo[j]=j;
    for (j=0;j<52 ;j++){
    x=rand () % 52;
    temp=mazo[j];
    mazo[j]=mazo[x];
    mazo[x]=temp;
  }
  puts("\n\nMazo desordenado:");
    for (j=0;j<52 ;j++ ){
      if (j%13==0)
        puts("\n");
      printf("%d  ",mazo[j]);
    }
   putchar ('\n');
   return EXIT_SUCCESS;
}

 

Acabo ahi despues de que le hicieran la tarea y borrara toda huella para poder presentarla tranquilo  :rolleyes: