[Algoritmo]Mescolare mazzo

[Xadoom]

Algoritmo per mescolare le carte di un mazzo Francese (52carte), la prima idea che mi è venuta è stata:

 
for(int cont=0; cont<52; cont++){
       Carta temp = mazzo[cont];
       int ran = (rand()%52);
       mazzo[cont] = mazzo[ran];
       mazzo[ran] = mazzo[cont];
    }

In pratica scorre tutto il mazzo (un Array di oggetti Carta) e per ogni carta scambia la posizione con una carta a caso nell'array.
Però non sono sicuro della validità di questo metodo....sbizzarritevi con altre soluzioni.

[scancode]

Devi avere 2 array uno per la carta e uno per il seme.

Poi devi fare un ciclo e ditribuire le carte in modo random e una routine che controlli se la carta e il seme sono già state distribuite.

[Xadoom]

No, ho già il mazzo che è un array di oggetti Carta (all'interno di ogni Carta sono poi definiti seme,valore,...)l'unica mia perplessità è su come mescolare in modo 'più casuale possibile' l'array.
ciao

[iguana13]

Io ho fatto adesso questo programma di esempio:

enum e_seme {
	picche = 0,
	fiori = 1,
	cuori = 2,
	quadri = 3
};

class carta
{
public:
	e_seme seme;
	unsigned int valore;
};

void mescola(carta mazzo[], int numero, int sicurezza = 500);
void mostra(carta mazzo[], int numero);

void main()
{
	carta mazzo[52];
	int i,j;

	// Inizializza i valori
	for(i=0; i<4; i++)
	{
		for(j=0; j<13; j++)
		{
			mazzo[i * 13 + j].seme = (e_seme) i;
			mazzo[i * 13 + j].valore = j + 1;
		}
	}

	mostra(mazzo,52);
	mescola(mazzo,52);

	cout << "\n\n\n\n\nMescolamento:\n\n\n\n\n\n\n";
	mostra(mazzo,52);
}

void mostra(carta mazzo[], int numero)
{
	int i;
	int p=0,f=0,c=0,q=0;
	for(i=0; i<numero; i++)
	{
		cout << "Carta numero " << mazzo[i].valore << " di seme ";

		switch(mazzo[i].seme)
		{
		case 0:
			cout << "picche";
			p++;
			break;
		case 1:
			cout << "fiori";
			f++;
			break;
		case 2:
			cout << "cuori";
			c++;
			break;
		case 3:
			cout << "quadri";
			q++;
			break;
		}

		cout << ".\n";
	}
	cout << "Totale: " << p << " picche, " << f << " fiori, " << c  << " cuori e " << q << "quadri.\n";

}

void mescola(carta mazzo[], int numero, int sicurezza)
{
	srand(numero * mazzo[0].valore * sicurezza % 30000);
	
	int i, pos1, pos2;
	carta initval;
	
	// Trovo la carta iniziale a caso
	pos1 = rand() % numero + 1;
	// Memorizzo il suo valore
	initval = mazzo[pos1];

	for(i=0; i < sicurezza; i++)
	{
		// Trovo un' altra carta a caso
		do {
			pos2 = rand() % numero + 1;
		// Diversa da quella di prima
		} while(pos2 == pos1);
		
		// Metto il valore dei questa carta nella carta di prima
		mazzo[pos1] = mazzo[pos2];
		// Ora questa è la carta 'vecchia'
		pos1 = pos2;
	}

	// Metto nell'ultima carta il valore della prima
	mazzo[pos1] = initval;
	
}

[Xadoom]

In fondo è quello che ho fatto io per mescolare il mazzo solo che tu il procedimento lo fai 500 volte e per carte a caso, e io lo faccio una sola volta per ogni carta (tot 52 spostamenti); ora poichè si vuole ottimizzare la cosa, la mia domanda è: Quanti spostamenti minimi ci vogliono per ottenere un mazzo ben mescolato?

[iguana13]

Considerando che il C++ è molto veloce...
e considerando che devi inizializzzare in modo sicuro il generatore di numeri casuali...

direi che 400/500 volte è sufficentemente sicuro

La differenza con il mio algoritmo è che il mio opera in modo continuo!
Funziona così:

1 - Prendi una carta da dove cominciare e memorizzane il valore
2 - Prendi una carta casuale e metti il valore in quella presa precedentemente
3 - Torna al punto 2 per n volte
4 - Metti nell' ultima carta considerate il valore della prima, che altrimenti andrebbe perso
5 -  :ciauz:

[Xadoom]

In effetti il tuo lavora in modo continuo operando lo spostamento di una carta per volta e poi ripristinando la prima carta.In 500 iterazioni ci sono stati quindi 500 spostamenti di carte; invece nell'altro modo ad ogni ciclo si muovono 2 carte, occorre quindi la metà di cicli per avere lo stesso "grado di mescolamento", equivale a dire:

1)Genera 2 numeri casuali differenti
2)Inverti le posizioni di quei due elementi
3)Ripeti n-volte

In questo modo mi pare che si compiano la metà dei cicli che dici tu! Che poi sia meglio o peggio bah...non so...comunque grazie dell'idea....altre soluzioni?

[LeleFT]

Tempo fa avevo postato un algoritmo semplicissimo, ma efficace (espresso a parole) per generare un array con tutti elementi compresi fra 1 e n in ordine casuale. Vediamo se riesco a riesprimerlo, adattato al tuo caso:

1) Pongo x=52, y=0, z=1 e creo un array di 52 elementi (li considero numerati da 1 a 52) contenente tutti i numeri da 1 a 52 ordinati; chiamiamolo array1 e un secondo array di 52 elementi vuoto, che chiamo array2

2) Estraggo un numero casuale fra 1 e x e lo assegno a y

3) Scrivo array[y] in posizione z in array2

4) Shifto tutti gli elementi dopo di array[y] a sinistra di 1

5) Decremento x di uno, incremento z di uno

6) Se x = 1 vado al punto 8

7) Torno al punto 2

8) Scrivo l'elemento array(1) in posizione array2[52]

Lo puoi usare per creare un array di 52 elementi non ordinato (mescolato) e contenente esattamente tutti i numeri da 1 a 52. Ora puoi usare questo array per indicizzare quello delle carte.


Ciao.

[Xadoom]

O mamma che cervellotico...mi civorrà una giornata per capirlo appieno
Vabbè...grazie!

[Xadoom]

Anzi no...capito!
Ora mi chiedo una cosa: conviene fare una cosa del genere?
Comunque molto carino come metodo.
Ciao