C++ Kaarten schudden

[Landro]

Ik heb een stuk code geschreven om een deck kaarten te schudden, maar ik twijfel of dit wel eerlijk geschud is. (De willekeurigheid van rand() laat ik voor alsnog buiten beschouwing.)

De code maakt gebruik van een array kaarten van het type 'card' waarmee de eigenschappen van een kaart opgezocht kunnen worden. Vervolgens heb een 1 or meer lijsten om het geschudde deck of handen in op te slaan. Deze lijsten bevatten een nummer van 0 tot en met 51 welke gebruikt kan worden als array index.

Ik twijfel aan de willekeurigheid omdat de eerste kaart (Cardlist[0]) als eerste de kans krijgt of de waarde 0 van de RNG mee te krijgen waardoor deze een hogere kans zou hebben om de eerste plek of de lijst the krijgen. (Overige kaarten krijgen een nieuw nummber als het eerste al gebruikt is) Is deze twijfel terecht?

Code: Selecteer alles

class Card{

// snip

};

class Deck{

Card CardList[52];

void Shuffle();

// snip

};

void Deck::Shuffle(){

map<int, int> m;	 // Create map to hold card numbers.

 	   // Numbers will be sorted based on the random value assigned to them.

int r = 0;

srand(time(NULL));

while(m.size() < 52){	// Create new entry while not all 52 cards have a random value

r = rand();

m.insert (pair<int, int>(r, m.size()));  // Store Card number (0 - 51). This just happens to be the size of the map before the number is added

}

// verplaats de inhoud van map m naar een deck.

// snip

}

[EvilBro]

Als je een regel verandert, twijfel ik niet aan de eerlijkheid:

Code: Selecteer alles

r = rand() % 52

De kans dat kaart 0 dan op positie nul uitkomt is

\(\frac{1}{52}\)

.

De kans dat kaart 1 dan op positie nul uitkomt is

\(\frac{51}{52} \cdot \frac{1}{51} = \frac{1}{52}\)

.

enz.

Misschien is het huidige algoritme ook al eerlijk, maar dat durf ik niet met zekerheid te zeggen (ik verwacht het overigens wel).

Ik heb echter wel een probleem met dit algoritme. Het is theoretisch mogelijk dat dit algoritme nooit stopt (Stel bijvoorbeeld dat je al 51 kaarten een key hebt toegewezen en je vervolgens alleen nog maar keys genereert die je al hebt). Dat is in mijn ogen een constructiefout.

[Xenion]

Code: Selecteer alles

	while(m.size() < 52){	// Create new entry while not all 52 cards have a random value

		r = rand();

		m.insert (pair<int, int>(r, m.size()));  // Store Card number (0 - 51). This just happens to be the size of the map before the number is added

	}

Je moet zoals EvilBro zegt de range van r nog fixen. Los daarvan: kan je nu niet 2x dezelfde kaart in je deck steken?

Je bouwt nu een map met paren: bv <6,0>, <23,1>, <41,2>, .... wat als r nu opnieuw 6 zou zijn?

[EvilBro]

insert doet niks als je een eerder gebruikte key probeert te gebruiken.

[Landro]

Ik heb bewust geen gebruik gemaakt van de remainder operatie (%) omdat ik dan zeker weet dat er een bias op de lage getallen komt. Bijvoorbeeld als rand() een getal tussen de 0 en 100 zou geven, dan zie je dat je minder vaak een rest waarde van 51 krijgt met 52 als deler.

Ik heb bewust gebruik gemaakt van een map container omdat de sleutel dan uniek moet zijn en gesorteerd wordt. Als je een duplikaat sleutel probeert toe te voegen zal er niets gebeuren en zal er een nieuwe iteratie van de lus plaats vinden.

Het is inderdaad theoretish mogelijk dat de routine oneindig door blijft gaan als keer op keer een sleutel wordt gegenereerd die al voorkomt. Maar als je 52 waardes uit een set van 0 tot 65536 gebruikt, maak ik me niet zo heel veel zorgen over die kans.

[Xenion]

Oké dan voor de map, dan zie ik ook waarom EvilBro zegt dat het oneindig zou kunnen loopen.

Voor rand():

Notice though that this modulo operation does not generate a truly uniformly distributed random number in the span (since in most cases lower numbers are slightly more likely), but it is generally a good approximation for short spans.

Als je toch een betere uniforme verdeling wil kan je het volgende doen:

Als je het random nummer dat je krijgt deelt door RAND_MAX, dan heb je een uniforme distributie in het interval [0,1]. Door optelling en vermenigvuldiging kan je dat interval aanpassen naar wat jij nodig hebt.

Ik zou zelf vertrekken van een vector van kaarten en daar telkens willekeurig 1 uithalen (ook verwijderen) en die dan in een nieuwe vector steken (random nr van 1 tot aantal dat nog overblijft). Als je dat herhaalt tot de eerste vector leeg is, dan heb je in de tweede een geshuffelde deck.

[EvilBro]

Het is inderdaad theoretish mogelijk dat de routine oneindig door blijft gaan als keer op keer een sleutel wordt gegenereerd die al voorkomt. Maar als je 52 waardes uit een set van 0 tot 65536 gebruikt, maak ik me niet zo heel veel zorgen over die kans.

De kans zal niet groot zijn. Echter het is beter om de situatie gewoon te voorkomen. Waarom zou je code schrijven waar je van te voren al weet dat er een situatie is waarin die code niet werkt?

[Landro]

Oké dan voor de map, dan zie ik ook waarom EvilBro zegt dat het oneindig zou kunnen loopen.

Voor rand():

Als je toch een betere uniforme verdeling wil kan je het volgende doen:

Als je het random nummer dat je krijgt deelt door RAND_MAX, dan heb je een uniforme distributie in het interval [0,1]. Door optelling en vermenigvuldiging kan je dat interval aanpassen naar wat jij nodig hebt.

Ik zou zelf vertrekken van een vector van kaarten en daar telkens willekeurig 1 uithalen (ook verwijderen) en die dan in een nieuwe vector steken (random nr van 1 tot aantal dat nog overblijft). Als je dat herhaalt tot de eerste vector leeg is, dan heb je in de tweede een geshuffelde deck.

Ook bij deze methode krijg je geen uniforme verdeling omdat je ook in deze situatie te maken hebt met een set aan waarden die geen veelvoud is van het aantal dat ik nodig heb (52). Door deze methode zal de bias mogelijk verschuiven naar andere waardes maar hij blijft bestaan. Dit is precies waarom ik voor de oplossing met een map koos omdat het 'veelvoud van' principe dan verdwijnt.

@Evilbro, Ik zou inderdaad beter een teller kunnen laten mee lopen die de lus na een bepaald aantal (bijv 100) iteraties afbreekt.

[Xenion]

Ook bij deze methode krijg je geen uniforme verdeling omdat je ook in deze situatie te maken hebt met een set aan waarden die geen veelvoud is van het aantal dat ik nodig heb (52). Door deze methode zal de bias mogelijk verschuiven naar andere waardes maar hij blijft bestaan. Dit is precies waarom ik voor de oplossing met een map koos omdat het 'veelvoud van' principe dan verdwijnt.

Hoezo?

rand() geeft een random getal r uit een uniforme verdeling tussen 0 en RAND_MAX

als je r deelt door RAND_MAX dan blijf je uniform verdeeld, maar in een interval tussen 0 en 1

via optellen en vermenigvuldigen kan je dat interval toch aanpassen naar wat je wil?

Genereer anders eens een histogram voor een paar miljoen waarden om de verdeling te visualiseren.

[EvilBro]

Ik zou inderdaad beter een teller kunnen laten mee lopen die de lus na een bepaald aantal (bijv 100) iteraties afbreekt.

Wat schiet je daarmee op? Je voorkomt een oneindige lus, maar je algoritme doet het nog steeds niet in 100% van de gevallen...

\(P = floor(\frac{rand()}{RAND\_MAX+1} \cdot N)\)

Dit geeft een getal in [0,1,2,...,(N-1)]. Genereer voor N=52 een P, begin aan de start van je stapel en skip P vrije posities. Insert de kaart in de dan huidige positie. Genereer voor N=51, begin aan de start van je stapel en skip P vrije posities. Insert de kaart in de dan huidige positie. rinse and repeat. Hierdoor weet je zeker dat je na 52 loops een nieuwe stapel hebt.

Ben je bang dat dit niet uniform verdeeld genoeg is? Dan roep je de schudroutine toch nog een keer aan... en nog een keer... enz.