Entwickler-Ecke
Sonstiges (Delphi) - Karten mischen
IhopeonlyReader - Mi 22.05.13 16:48
Titel: Karten mischen
Guten Tag,
ich habe mir ein paar Möglichkeiten überlegt, wie man am besten Karten mischt...
Als ich mal überlegte welche die beste sei, stieß ich auf wiederrum andere Methoden...
Deshalb hier mal ein paar Beispiele:
1. Zwei Karten rausnehmen und vertauschen (und das x mal (im Bsp. 1000 mal))
Delphi-Quelltext
1: 2: 3: 4: 5: 6: 7: 8: 9: 10:
| for i := 0 to 1000 do begin KartenNummer1:= Random( High(Karten) ) +1; KartenNummer2:= Random( High(Karten) ) +1; Speicher := Karten[ KartenNummer1 ]; Karten[ KartenNummer1 ] := Karten[ KartenNummer2 ]; Karten[ KartenNummer2 ] := Speicher; end; |
2. Normale Reallife Methode :D
(Bestimme Menge an Karten von oben nach unten "packen")
Delphi-Quelltext
1: 2: 3: 4: 5: 6: 7: 8: 9: 10: 11: 12: 13: 14: 15: 16:
| |
3. Alle durcheinander würfeln
(irgendeine Karte aus dem Stapel ziehen und auf "neuen" Stapel legen...)
Habe gerade leider keine Zeit den auch noch hier zu coden, aber ich denke jeder weiß was gemeint ist ;)
freue mich auf DIE beste (bestgemscihte in schnellster Zeit) Methode
Edit 22.05.13: Methode 2. ist falsch !, beim normalen mischen nimmt man nicht karten von oben und legt sie drunter, sondern nimmt karten von oben auf neuen stapel, und wiederholt diesen vorgang bis keine karten mehr auf dem "ersten" stapel sind. dann werden die karten vom "neuen" stapel auf den alten gelegt...
Delphi-Quelltext
1: 2: 3: 4: 5: 6: 7: 8: 9: 10: 11: 12: 13: 14: 15: 16: 17: 18: 19: 20:
| For Anzahl := 1 to 1000 do begin setlength(neuerHaufen, Length(Karten)); g := 0; repeat n := Random( High(Karten) - g) +1; For C:=1 to n do neuerHaufen[ High(neuerHaufen) - C +1] := Karten[C]; g := n; until g>=(HighKarten-1);
For C:=1 to High(Karten) do Karten[C] := neuerHaufen[C]; setlength(neuerHaufen, 0); end; |
Xion - Mi 22.05.13 17:39
Fisher-Yates-Shuffle [
http://en.wikipedia.org/wiki/Fisher%E2%80%93Yates_shuffle#Comparison_with_other_shuffling_algorithms]
"The Fisher–Yates shuffle is quite efficient; indeed, its asymptotic time and space complexity are optimal. Combined with a high-quality unbiased random number source, it is also guaranteed to produce unbiased results. Compared to some other solutions, it also has the advantage that, if only part of the resulting permutation is needed, it can be stopped halfway through, or even stopped and restarted repeatedly, generating the permutation incrementally as needed."
Was will man mehr? :mrgreen:
IhopeonlyReader - Mi 22.05.13 20:56
Naja eine Permutation arbeitet aber immer gleich..
Beispiel:
mische ich und nehme die 13 Permutation so ist es immer die selbe Reihenfolge ! dann müsste ich also
die x-te Permutation nehmen und x ist gerandomed.. wobei x = range von High(Karten)! oder?
Mathematiker - Mi 22.05.13 21:06
Hallo,
IhopeonlyReader hat folgendes geschrieben : |
mische ich und nehme die 13 Permutation so ist es immer die selbe Reihenfolge ! dann müsste ich also die x-te Permutation nehmen und x ist gerandomed.. wobei x = range von High(Karten)! oder? |
Nicht ganz. Wenn Du denn genannten Artikel liest, siehst Du das für das Feld a (Indizees 0 bis n-1)
Delphi-Quelltext
1: 2: 3: 4: 5: 6: 7:
| for i:=n-1 downto 0 do begin j:=random(n); h:=a[i]; a[i]:=a[j]; a[j]:=h; end; |
gemeint ist. Einen schnelleren und effizienteren Algorithmus zum Mischen wirst Du kaum finden.
Beste Grüße
Mathematiker
IhopeonlyReader - Mi 22.05.13 21:11
dies ist FAST derselbe Algorithmus wie mein "Karten- vertauschen"
nur dass bei dir i mit random(n) = j vertauscht wird und bei mir beide gerandomed werden
P.S: ok, aus meiner For-to-Schleife kann ich natürlich auch noch eine For-downto-Schleife machen, wie ich gehört/gelesen habe soll diese ja schneller sein..
h.O.T (halbwegs Off Topic): Allgemein habe ich gehört, Subtrahieren sei schneller! als Addieren.. stimmt das?
Mathematiker - Mi 22.05.13 21:14
Hallo,
IhopeonlyReader hat folgendes geschrieben : |
dies ist FAST derselbe Algorithmus wie mein "Karten- vertauschen" |
Aber nur fast.
Durch das Herunterzählen von n-1 zu 0 wird garantiert, dass jedes Element sicher einmal in den Tauschprozess einbezogen ist. Bei zwei zufälligen Indizees ist das nicht sicher.
Aus dem Grund musst Du auch viel häufiger tauschen. Der von Durstenfeld verbesserte Fisher-Yates-Algorithmus ist von der Komplexität O(n), also superschnell.
Beste Grüße
Mathematiker
IhopeonlyReader - Mi 22.05.13 21:20
Beides ist stochastisch korrekt!
Allerdings muss bei dir nat. nur 1x gerandomed werden -> schneller...
theoretisch muss bei mir nicht "öfter" durchgeführt werden, als deine.. beide tauschen n-Karten...
bei dir kann j = i sein und somit ebenfalls die karte sozusagen "nicht in den tausch einbezogen sein" genau wie bei mir
Kartennummer1 = Kartennummer2 sein kann.. wobei ich das durch die Zeile
Delphi-Quelltext
1:
| while Kartenummer2=Kartenummer1 do randomAgain; |
wobei hierdurch das ganze nicht mehr stochastisch korrekt wäre
IhopeonlyReader - Mi 22.05.13 21:35
eine while schleife führt natürlich zu einer "unbekannten" Laufzeit..
dann könnte man besser
Delphi-Quelltext
1: 2: 3: 4:
| Kartennummer2 := Random(High(Karten-1)+1; if Kartennummer2>=Kartennummer1 then inc(Kartenummer2) |
Moderiert von
Narses: Beiträge zusammengefasstich habe Fisher-Yates-Shuffle mal auf meine "verkette Liste" übertragen
Delphi-Quelltext
1: 2: 3: 4: 5: 6: 7: 8: 9: 10: 11: 12: 13: 14: 15: 16: 17: 18: 19: 20: 21: 22: 23:
| procedure TStapel.Mischen; var c, j, n: Byte; Karte1, Karte2: TKarte; gF: TFarbe; gW: TWert; begin Karte2 := Erste; for c:=Anzahl downto 1 do begin j := random(Anzahl)+1; Karte1 := Erste; For n:=j downto 2 do Karte1 := Karte1.darunter; gF := Karte2.Farbe; gW := Karte2.Wert; Karte2.Farbe := Karte1.Farbe; Karte2.Wert := Karte1.Wert; Karte1.Farbe := gF; Karte1.Wert := gW; Karte2 := Karte2.darunter; end; end; |
seht ihr Fehler?
ich denke die Variablen sind selbsterklärend ;) ich habe in meiner Verketten Liste nicht next sondern darunter, entsprechen auf ein Kartenspiel eben übertragen..
die Klasse allgemein heißt TStapel;
Erste ist halt die Erste Karte (oberste)
bole - Mi 22.05.13 22:12
Ich frage mich eher ob eine verkettet Liste für dieses Problem Sinnvoll ist.
Meines Wissens wurde eine Verkettet Liste vor allem benötigt als es noch keine dynamischen Arrays gab wenn man zur Compilationszeit nicht wusste wie viele Daten diese beinhalten soll. Da man bei einem Kartenspiel in der Regel zur Compilationszeit weis wie viele Karten das Spiel hat macht ein normales Array mehr Sinn da man direkt auf jede Karte zugreifen kann ohne vorher den ganzen Stapel zu verarbeiten.
Meines Erachtens hat zur heutigen Zeit mit Dyn. Arrays eine Verkette Liste keinen Sinn mehr. Allerdings lasse ich mich da gerne eines besseren belehren.
Gruss
Bole
IhopeonlyReader - Mi 22.05.13 22:15
bole hat folgendes geschrieben : |
Da man bei einem Kartenspiel in der Regel zur Compilationszeit weis wie viele Karten das Spiel hat macht ein normales Array mehr Sinn |
Nein die Größe kennt man nicht !
Am Anfang sind auf dem Deck zwar 52 oder 32 Karten, aber es werden immer weniger und diese Karten verteilen sich dann auf die Stapel (Hände) der Spieler und auf den abgelegten Stapel !
P.S: Ich habe Erfahrungen gemacht, dass eine verkette Liste teilweise schneller als ein dyn Array ist ;)
bei dyn. Arrays muss man immer erst die Länge ändern (setlength)
einzelne Elemente "vertauschen" finde ich bei verketten Listen ebenfalls leichter ;)!
Horst_H - Mi 22.05.13 23:41
Hallo,
man könnte auch Tlist nutzen, statt sich durch die Liste immer bis zum passenden Platz durch zu hangeln, kann man dort direkt mit exchange arbeiten:
Siehe
http://www.delphibasics.co.uk/RTL.asp?Name=TList mit Beispiel.
Man kann dort zu Beginn auch die voraussichtlich maximale Größe in capacity angeben, wobei aber nur count momentan genutzt werden.
Also zu Beginn auf z.B. capacity = 52 setzen und nach und nach die Karten verteilen/ablegen , wobei count sinkt.
Gruß Horst
jfheins - Do 23.05.13 11:09
IhopeonlyReader hat folgendes geschrieben : |
Beides ist stochastisch korrekt! |
Nö, dein Karten-vertauschen ist es nicht.
Hier:
Delphi-Quelltext
1: 2: 3: 4: 5: 6: 7:
| begin KartenNummer1:= Random( High(Karten) ) +1; KartenNummer2:= Random( High(Karten) ) +1; Speicher := Karten[ KartenNummer1 ]; Karten[ KartenNummer1 ] := Karten[ KartenNummer2 ]; Karten[ KartenNummer2 ] := Speicher; end; |
erzeugt du für ein Deck mit drei Karten zwar ganz viele verschiedene Möglichkeiten (geschätzt 4^1000) aber sie entstehen nicht alle gleich wahrscheinlich. Da es überhaupt nur 6 Möglichkeiten gibt und 4^1000 nicht glatt durch 6 teilbar ist,
müssen gewisse Muster bevorzugt werden!
Der Fisher-Yates umgeht dieses Problem und macht es direkt richtig. Siehe auch hier:
http://www.codinghorror.com/blog/2007/12/the-danger-of-naivete.html
Zitat: |
P.S: ok, aus meiner For-to-Schleife kann ich natürlich auch noch eine For-downto-Schleife machen, wie ich gehört/gelesen habe soll diese ja schneller sein..
h.O.T (halbwegs Off Topic): Allgemein habe ich gehört, Subtrahieren sei schneller! als Addieren.. stimmt das? |
Ist beides völlig egal. Die Compileroptimierung macht das schon ;-)
Zitat: |
Ich habe Erfahrungen gemacht, dass eine verkette Liste teilweise schneller als ein dyn Array ist |
Tja, das kommt ganz drauf an. Bei einer verketteten Liste dauert das Einfügen an einer beliebigen Position O(n), ganz vorne ist es mit O(1) zu machen. Löschen ist immer O(1), Zugriff auf einen Index O(n).
Das (naive) dynamische Array hingegeben besitzt die Laufzeiten O(n) für's Rinfügen (egal wo), O(1) für einen zugriff und O(n) für's Löschen. Außerdem sind die Daten nach beieinander, was modernen CPUs entgegenkommt. (CPU-Cache)
Für dieses Problem würde ich an deiner Stelle auf jeden Fall dyn. Arrays hernehmen. Die maximale Größe ist bekannt und wahlfreier Zugriff ist schon gut.
Ich benutze immer Listen, das ist eine etwas ausgefeiltere Variante eines dynamischen Arrays, das die Länge immer gleich verdoppelt oder so.
Blup - Do 23.05.13 15:56
Einfaches Problem (n Karten mischen), einfache Lösung (n-1 mal tauschen):
Delphi-Quelltext
1: 2: 3: 4: 5: 6: 7: 8: 9: 10: 11: 12: 13: 14: 15: 16: 17: 18: 19: 20: 21: 22: 23: 24: 25: 26: 27: 28: 29:
| type TKartenStapel = class(TObjectList) protected procedure Swap(a, b: Integer); public procedure Mischen; end;
implementation
procedure TKartenStapel.Swap(a, b: Integer); var t: TObject; begin if a <> b then begin t := Items[a]; Items[a] := Items[b]; Items[b] := t; end; end;
procedure TKartenStapel.Mischen; var n: Integer; begin for n := Count - 1 downto 1 do Swap(n, Random(n + 1)); end; |
Edit:
Wurde ja weiter Oben im Prinzip schon gepostet, hab ich übersehen.
Random(n + 1) damit die Karte auch die selbe Chance auf den bisherigen Platz hat, wie auf jeden anderen Platz.
IhopeonlyReader - Do 23.05.13 19:38
jfheins hat folgendes geschrieben : |
erzeugt du für ein Deck mit drei Karten zwar ganz viele verschiedene Möglichkeiten (geschätzt 4^1000) aber sie entstehen nicht alle gleich wahrscheinlich. Da es überhaupt nur 6 Möglichkeiten gibt und 4^1000 nicht glatt durch 6 teilbar ist, müssen gewisse Muster bevorzugt werden!
|
4^1000 ? wie kommst du darauf? bei einem Deck mit 3 Karten (ArrayIndex 1, 2, 3) ist High(Karten) = 3
random(3)+1 liefert also eine der Zahlen, die als Index infragekommen...
das ganze wird 2x gemacht, somit können auch dieselbe KArte vertauscht werden (unverändert)
das kann bei Fisher-Yates eben so passieren.. und zwar falls n = random(n+1)
wobei hier random(n+1) FALSCH ist !
es müsste heißen random(n)+1, (vorrausgesetzt es beginnt bei der 1sten karte und nicht bei der 0ten)
n ist die Anzahl der Elemente, also bei 3 Karten (0, 1,2 bei Indexbegin 0) random(n) also random(3) liefert doch dann schon das korrekte Ergebnis !
random(n+1) dagegen nicht mehr..
//Edit: Ah: n ist die Schleifenvariable, und da BeginIndex = 0 wird in der Schleife -1, deshalb bei random wieder +1..
//aber warum wird mit der Schleifenvariable gerandomed und nicht mit der Anzahl der Karten? (siehe weiter unten, bei blub ist mir dasselbe aufgefallen
//Edit-ende
@Blub
wieso machst du Swap(n Random(n+1) ?
warum die schleife bei Count -1 beginnt ist klar, dein index beginnt bei 0, aber deine schleife geht nur bis 1? Also das ist falsch,
entweder
Delphi-Quelltext
1: 2: 3:
| For n := Count-1 downto 0 do For n := Count downto 1 do |
aber deine Variante ist nicht korrekt...
dein Random(n+1) verstehe ich auch nicht.. wenn n gegen den anfang läuft (n->1) dann wird random Automatisch 0 1 oder 2, alle anderen "Karten" fallen weg.. wieso?
müsste es nicht heißen:
Delphi-Quelltext
1: 2: 3:
| Random(Count) Random(Count) +1 |
Nachtrag: Tut mir leid, dass ich alles "kritisiere" aber entweder verstehe ich gerade die Stochastik nicht mehr, oder ich finde den Punkt nicht :D auf jeden Fall erschließt es mir noch nicht ganz...
Ich hoffe ihr nehmt es nicht persönlich, aber für mich sieht das oben genannte halt falsch aus ...
Entwickler-Ecke.de based on phpBB
Copyright 2002 - 2011 by Tino Teuber, Copyright 2011 - 2025 by Christian Stelzmann Alle Rechte vorbehalten.
Alle Beiträge stammen von dritten Personen und dürfen geltendes Recht nicht verletzen.
Entwickler-Ecke und die zugehörigen Webseiten distanzieren sich ausdrücklich von Fremdinhalten jeglicher Art!