PROGRAMMERING: Hur blanda en kortlek?

[mte]

Vet inte riktigt var det här ska läggas så räknar med QoS triggerfingrar snart

 

Är det någon som har några ideer, eller känner till en färdig funktion/klass, för att blanda en kortlek så att den anses vara slumpmässig?

 

Jag fundera på om det räcker med att köra det vanligaste, dvs ta ut 2st slumpmässiga kort ur arrayen och sen byta plats på dem och upprepar detta ett gäng gånger.

Tankar och förslag emottages tacksamt.

 

* Lite ändring i rubriken - QoS *

[QoS]

random.org is your friend!

 

- QoS

[mte]

I och för sig intressant, och kanske kan användas för slumpningen då

 

Men vad tror du om själva blandningen av en kortlek då? Skulle det fungera med att plocka 2 kort slumpmässigt och byta plats på dem, och i så fall, hur många iterationer är det optimala? ;D

[aztaroth]

Byta plats på två kort i taget låter som en väldigt ineffektiv blandning. Jag skulle nog leka med en priority queue och slumpa priority.

[QoS]

Varför ska du byta plats öht?

 

Är det inte bara intitera en 52 vektor och minska den med varje dragen position?

 

Dragningen sker genom en fin slumpgenerator (t ex random.org).

 

- QoS

[telle]

Här är en svinsimpel implementation i java:

    
void shuffle() {
   for ( int i = 51; i >= 0; i-- ) {
       int rand = (int)(Math.random()*(i+1));
       Card temp = deck[i];
       deck[i] = deck[rand];
       deck[rand] = temp;
   }
}

vet inte hur "slumpigt" det blir men jag gjorde ett patiensprogram en gång i tiden med den här metoden för att blanda.

 

//Telle

[gdaily]

Det finns en lång tråd om detta på http://www.bridgefederation.se / anslagstavlan för några månader sedan, och det är tydligen jävligt svårt!

 

Ett tips är att ta kontakt med Pi här på forumet.

 

/Ola

[mte]

Byta plats på två kort i taget låter som en väldigt ineffektiv blandning. Jag skulle nog leka med en priority queue och slumpa priority.

 

Ineffektiv som i risig slump, eller ineffektiv rent exekveringsmässigt?

 

Varför ska du byta plats öht?

 

Är det inte bara intitera en 52 vektor och minska den med varje dragen position?

 

Jo, det är ett alternativ, men som upplägget just nu är så ska en befintlig lek bestående av 52 kort bara blandas, dvs inga kort ges osv. Kommer nog inte att använda det här framöver så för tillfället blir det till att slumpa runt korten lite som får duga

[Perli]

Att ta två slumpade kort och byta plats på dom är inte särskillt effektivt nej, du måste köra denna typ av blandning ganska många gånger för att se till att varje kort byter plats minst en gång.

 

Mitt tips är istället att vandra igenom leken och byta kortet på den aktuella platsen med ett annat kort, på detta vis har varje kort garanterat bytt plats minst en gång under ett varv och det finns chans att det kommer tillbaks till utgångspunkten oxå vilket bara är bra, givetvis går det att upprepa denna blandning ett antal gånger men ett varv borde räcka ganska långt iaf.

[telle]

Mitt tips är istället att vandra igenom leken och byta kortet på den aktuella platsen med ett annat kort, på detta vis har varje kort garanterat bytt plats minst en gång under ett varv och det finns chans att det kommer tillbaks till utgångspunkten oxå vilket bara är bra, givetvis går det att upprepa denna blandning ett antal gånger men ett varv borde räcka ganska långt iaf.

 

precis som i mitt inlägg ovan mao... 8)

 

/telle

[Perli]

Mitt tips är istället att vandra igenom leken och byta kortet på den aktuella platsen med ett annat kort, på detta vis har varje kort garanterat bytt plats minst en gång under ett varv och det finns chans att det kommer tillbaks till utgångspunkten oxå vilket bara är bra, givetvis går det att upprepa denna blandning ett antal gånger men ett varv borde räcka ganska långt iaf.

 

precis som i mitt inlägg ovan mao... 8)

 

/telle

 

jepp

[Svinto]

Vad är det som inte blir bra om man utgår från en lista med 52 kort, väljer ett kort slumpmässigt ur denna och placerar detta kort i en ny lista, därefter väljer ett nytt kort ur listan som nu innehåller 51 kort och placerar detta sist i resultatlistan osv?

[aztaroth]

Mitt tips är istället att vandra igenom leken och byta kortet på den aktuella platsen med ett annat kort, på detta vis har varje kort garanterat bytt plats minst en gång under ett varv och det finns chans att det kommer tillbaks till utgångspunkten oxå vilket bara är bra, givetvis går det att upprepa denna blandning ett antal gånger men ett varv borde räcka ganska långt iaf.

 

Hyfsat bra, men vissa resultat blir marginellt vanligare än andra. Om man räknar alla kort före den "aktuella platsen" som färdigblandade och låter bli att röra dem igen, samt tillåter kortet på den aktuella platsen att "byta plats" med sig själv så fungerar det bättre (alla resultat lika vanliga om man har en bra slumptalsgenerator). Effektivt om man lagrar leken i en array/vector/whatever.

 

Vad är det som inte blir bra om man utgår från en lista med 52 kort, väljer ett kort slumpmässigt ur denna och placerar detta kort i en ny lista, därefter väljer ett nytt kort ur listan som nu innehåller 51 kort och placerar detta sist i resultatlistan osv?

 

Ineffektivt att hitta rätt kort mitt i en lista. Spelar iofs ingen större roll med 52 kort, men... det är fel!

[Fairlane]

Ineffektivt att hitta rätt kort mitt i en lista. Spelar iofs ingen större roll med 52 kort, men... det är fel!

 

Que? ineffektivt?

 

Jag tolkade förslaget ungefär så här:

 

kort oblandad_lek[52];

kort blandad_lek[52];

 

for( int i = 52; i>0 --i )

{

int x = random(i); // i = maxvärde på random

blandad_lek[i-1] = oblandad_lek[x];

swap ( oblandad_lek[x], oblandad_lek[i-1] );

}

 

Ungefär så. Om det ger en bra blandad kortlek eller ej vågar jag inte säga, även om det rent spontant ser ok ut. Effektivt borde det väl ändå vara? O(n) eller är något av de andra föslagen O(log n)?

[Svinto]

Japp, Fairlanes kod motsvarar vad jag tänkte mig. Och jag förstår fortfarande inte vad som är fel med det förslaget. Det är inte ineffektivt att hitta rätt kort hur man än resonerar. Det handlar om att slumpa fram ett värde mellan 0 och 51 och att använda detta som index. Så mycket effektivare kan det inte gärna bli. Formellt bevis lämnas som övning åt den intresserade läsaren

[aztaroth]

Det där är inte listor.

[Svinto]

Huh? Vektorer är listor. Huruvida man väljer att lösa problemet med c-vektorer, javas Vector-klass eller listor i t.ex. Python är ju helt ointressant så länge problemet är teoretiskt.

 

Jag antar att du tolkade mitt förslag som att man skulle använda LÄNKADE listor utan direktindexering. Det ska man självklart inte. Det hade varit helt idiotiskt.

[aztaroth]

Okej, okej, jag är dum. Tänkte naturligtvis "länkad lista" när jag läste lista och hakade upp mig på det. Borde nog sova mer.

 

Anyway, O(n) bör väl vara rätt optimalt. Hyfsat onödigt att ha en "extra" lek, dock.

 

kort lek[52];

for(int i = 0; i < 52; ++i) {
   swap(lek[i], lek[rnd(52 - i) + i]);
}

 

(där 0 <= rnd(x) < x och swap... swappar)

[QoS]

Amatörer! Men min metod kommer ni ner i en komplexitet som är O(1/n), slå det ni!

 

Inte ens i Matlab så kommer man ner i såna fantasiska reslutat.

 

Ja, jag är jäkligt trött nu. Håller på att avsluta min jäkla rapport om 2G/3G och WLAN integration.

 

- QoS

[Svinto]

Anyway, O(n) bör väl vara rätt optimalt. Hyfsat onödigt att ha en "extra" lek, dock.

 

Ja, det går lika bra med en lek även om det inte kommer att påverka komplexiteten ett endaste dugg. Och jag håller med om att det verkar orimligt att man skulle kunna få bättre komplexitet än O(n).

[Henkeman]

Varför blanda kortleken?

 

Borde väl gå bra att bara slumpa ut vilket kort som delas ut? (Och kolla då så att det inte redan är utdelat förstås)

 

Funderar själv på vad jag ska göra för något... riktigt sugen på att fräscha upp mina programmeringsskills samtidigt som det vore kul att göra något program som kan beräkna sannolikheter eller nåt sånt (sen är det nog väldigt nyttigt att bara göra programmet, får man nog rätt bra insikt i sannolikheter och sånt)

[cisco]

http://www.paradisepoker.com/shuffling.html

 

Frågor på det?

[Permit]

På partynätverket blandas kortleken före given. Vet inte om ni sagt det, ville bara svara på tråden som låstes där frågan ställdes.

[nisse hult]

På partynätverket blandas kortleken före given. Vet inte om ni sagt det, ville bara svara på tråden som låstes där frågan ställdes.

 

Tackar för svaret!

[nucleus]

dunkar in min fråga här eftersom min tråd blev låst.

 

efter att ha skumläst den här tråden tänke jag bara lägga till lite...

 

Dyker upp endel förslag på kod som fixar biffen men gärna lite mer förklaring vad som händer om nån har tid och lust....

 

---------------------------------

Hur fungerar egentligen slupgeneratorerna som sidorna kör?

 

Jag kan i stort sett ingenting om programmering, har väl visserligen någon kurs i C++ men där var man mest närvarande på frånvarolistan för att citera timbuken. Men jag är säker på att många på detta forum är betydligt mer bevandrade i detta språk som kallas programmering.

 

Några funderingar bara, ni får väl säga till om det är helt jävla galet. Till att börja med måste man väl ha nån slags variabel annars funkar det väl inte?! Tiden är väl ett enkelt sätt för hobbyprogrammerare, och då använder man sig av flyttal som är tillräckligt stora (antal bit?!?) för att det ska skilja mellan säg 1.02s och 1.021s??

 

Om man nu skulle ha tiden som variabel, slumpas hela handen på en gång så att det är bestämt vilka kort som kommer upp oavsett hur spelarna agerar eller kan det ha att göra med just när spelarna gör ett aktivt val som något nytt slumpas fram. Det ställer ju lite mer filosofiska frågor om det skulle vara så. Undra om jag kan dra ut med min färg på river, inte nu och inte nu...eller nu...men NU och så stänker man dit en nötfärg. Skulle det inte slumpas precis när man gör valet borde det väl innebära en säkerhetsrisk efterom information redan ligger ute om handen är förutbestämd.

 

Hursomhelst, vore riktigt kul att få lite bra svar på denna. Har som sagt inte den minsta aning om hur det fungerar men jag tror att nån av er säkert har en rätt bra uppfattning.