Autor Beitrag
IhopeonlyReader
ontopic starontopic starontopic starontopic starontopic starontopic starontopic starhalf ontopic star
Beiträge: 600
Erhaltene Danke: 23


Delphi 7 PE
BeitragVerfasst: Mi 22.05.13 16:48 
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))
ausblenden Delphi-Quelltext
1:
2:
3:
4:
5:
6:
7:
8:
9:
10:
//Speicher: TKarte;
//KartenNummer1, KartenNummer2: Byte; //mehr als 255 Karten wären zuviel :D
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")
ausblenden Delphi-Quelltext
1:
2:
3:
4:
5:
6:
7:
8:
9:
10:
11:
12:
13:
14:
15:
16:
//var ZwischenKarten: Array of TKarte;
//i und C sind Counter vom Typ Byte
{for i := 0 to 1000 do //wieder 100 mal "abheben"
begin
Anzahl := Random( High(Karten)-1 ) +2; //mindests 2 Karten abheben
setlength(ZwischenKarten, length(Karten))
 For C := Anzahl+1 to High(Karten) do
  ZwischenKarten[C-Anzahl] := Karten[C];
 For C := 1 to Anzahl do
  ZwischenKarten[C+Anzahl] := Karten[C];

For C:= 1 to High(Karten) do
 Karten[C] := ZwischenKarten[C];

setlength(ZwischenKarten, 0);
end;}
 //FALSCH ! nach der Beschreibung korrekt, aber bitte siehe Edit !


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...

ausblenden Delphi-Quelltext
1:
2:
3:
4:
5:
6:
7:
8:
9:
10:
11:
12:
13:
14:
15:
16:
17:
18:
19:
20:
//var neuerHaufen: Array of TKarten;
//g: Byte; //von Oben genommen (g = genommen)
//n: Byte; //zu nehmenden karten (von oben auf neuen stapel);
//c, Anzahl: Byte // Counter für For-Schleife
For Anzahl := 1 to 1000 do //1000 mal haufen durchmischen
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);

//wieder in "andere Hand" legen
For C:=1 to High(Karten) do
 Karten[C] := neuerHaufen[C];
setlength(neuerHaufen, 0);
end;

_________________
Sucht "neueres" Delphi :D
Wer nicht brauch was er hat, brauch auch nicht was er nicht hat!


Zuletzt bearbeitet von IhopeonlyReader am Mi 22.05.13 21:39, insgesamt 4-mal bearbeitet
Xion
ontopic starontopic starontopic starontopic starontopic starontopic starontopic starhalf ontopic star
EE-Maler
Beiträge: 1952
Erhaltene Danke: 128

Windows XP
Delphi (2005, SmartInspect), SQL, Lua, Java (Eclipse), C++ (Visual Studio 2010, Qt Creator), Python (Blender), Prolog (SWIProlog), Haskell (ghci)
BeitragVerfasst: Mi 22.05.13 17:39 
Fisher-Yates-Shuffle

"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:

_________________
a broken heart is like a broken window - it'll never heal
In einem gut regierten Land ist Armut eine Schande, in einem schlecht regierten Reichtum. (Konfuzius)
IhopeonlyReader Threadstarter
ontopic starontopic starontopic starontopic starontopic starontopic starontopic starhalf ontopic star
Beiträge: 600
Erhaltene Danke: 23


Delphi 7 PE
BeitragVerfasst: 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?

_________________
Sucht "neueres" Delphi :D
Wer nicht brauch was er hat, brauch auch nicht was er nicht hat!
Mathematiker
ontopic starontopic starontopic starontopic starontopic starontopic starhalf ontopic starofftopic star
Beiträge: 2622
Erhaltene Danke: 1448

Win 7, 8.1, 10
Delphi 5, 7, 10.1
BeitragVerfasst: Mi 22.05.13 21:06 
Hallo,
user profile iconIhopeonlyReader hat folgendes geschrieben Zum zitierten Posting springen:
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)
ausblenden 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

_________________
Töten im Krieg ist nach meiner Auffassung um nichts besser als gewöhnlicher Mord. Albert Einstein
IhopeonlyReader Threadstarter
ontopic starontopic starontopic starontopic starontopic starontopic starontopic starhalf ontopic star
Beiträge: 600
Erhaltene Danke: 23


Delphi 7 PE
BeitragVerfasst: 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?

_________________
Sucht "neueres" Delphi :D
Wer nicht brauch was er hat, brauch auch nicht was er nicht hat!
Mathematiker
ontopic starontopic starontopic starontopic starontopic starontopic starhalf ontopic starofftopic star
Beiträge: 2622
Erhaltene Danke: 1448

Win 7, 8.1, 10
Delphi 5, 7, 10.1
BeitragVerfasst: Mi 22.05.13 21:14 
Hallo,
user profile iconIhopeonlyReader hat folgendes geschrieben Zum zitierten Posting springen:
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

_________________
Töten im Krieg ist nach meiner Auffassung um nichts besser als gewöhnlicher Mord. Albert Einstein
IhopeonlyReader Threadstarter
ontopic starontopic starontopic starontopic starontopic starontopic starontopic starhalf ontopic star
Beiträge: 600
Erhaltene Danke: 23


Delphi 7 PE
BeitragVerfasst: 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
ausblenden Delphi-Quelltext
1:
while Kartenummer2=Kartenummer1 do randomAgain;					

wobei hierdurch das ganze nicht mehr stochastisch korrekt wäre

_________________
Sucht "neueres" Delphi :D
Wer nicht brauch was er hat, brauch auch nicht was er nicht hat!
bole
ontopic starontopic starontopic starontopic starontopic starontopic starontopic starhalf ontopic star
Beiträge: 107
Erhaltene Danke: 15

win 10

BeitragVerfasst: Mi 22.05.13 21:27 
user profile iconNarses hat dazu einen schönen Eintrag mit Beispielprogramm geschrieben...

www.entwickler-ecke....ht=yates&view=dl

Gruss

Bole

_________________
ein programm macht nicht das was du willst sondern was du schreibst!
IhopeonlyReader Threadstarter
ontopic starontopic starontopic starontopic starontopic starontopic starontopic starhalf ontopic star
Beiträge: 600
Erhaltene Danke: 23


Delphi 7 PE
BeitragVerfasst: Mi 22.05.13 21:35 
eine while schleife führt natürlich zu einer "unbekannten" Laufzeit..
dann könnte man besser
ausblenden Delphi-Quelltext
1:
2:
3:
4:
Kartennummer2 := Random(High(Karten-1)+1//-1 muss ergänzt werden, da sonst die Kartennummer2 über der Range des
//Arrays liegen kann !, falls man die range dann wieder abziehen würde wäre die Wahrscheinlichkeit für das 1ste Element doppelt so groß wie die auf die anderen!
//damit es also stochastisch korrekt bleibt: 
if Kartennummer2>=Kartennummer1 then inc(Kartenummer2)


Moderiert von user profile iconNarses: Beiträge zusammengefasst

ich habe Fisher-Yates-Shuffle mal auf meine "verkette Liste" übertragen
ausblenden 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;
    //if c>1 then
    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)

_________________
Sucht "neueres" Delphi :D
Wer nicht brauch was er hat, brauch auch nicht was er nicht hat!
bole
ontopic starontopic starontopic starontopic starontopic starontopic starontopic starhalf ontopic star
Beiträge: 107
Erhaltene Danke: 15

win 10

BeitragVerfasst: 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

_________________
ein programm macht nicht das was du willst sondern was du schreibst!
IhopeonlyReader Threadstarter
ontopic starontopic starontopic starontopic starontopic starontopic starontopic starhalf ontopic star
Beiträge: 600
Erhaltene Danke: 23


Delphi 7 PE
BeitragVerfasst: Mi 22.05.13 22:15 
user profile iconbole hat folgendes geschrieben Zum zitierten Posting springen:
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 ;)!

_________________
Sucht "neueres" Delphi :D
Wer nicht brauch was er hat, brauch auch nicht was er nicht hat!
Horst_H
ontopic starontopic starontopic starontopic starontopic starontopic starontopic starofftopic star
Beiträge: 1654
Erhaltene Danke: 244

WIN10,PuppyLinux
FreePascal,Lazarus
BeitragVerfasst: 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 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
ontopic starontopic starontopic starontopic starontopic starontopic starofftopic starofftopic star
Beiträge: 918
Erhaltene Danke: 158

Win 10
VS 2013, VS2015
BeitragVerfasst: Do 23.05.13 11:09 
user profile iconIhopeonlyReader hat folgendes geschrieben Zum zitierten Posting springen:
Beides ist stochastisch korrekt!

Nö, dein Karten-vertauschen ist es nicht.
Hier:
ausblenden 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: www.codinghorror.com...nger-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.

Für diesen Beitrag haben gedankt: Marc.
Blup
ontopic starontopic starontopic starontopic starontopic starontopic starontopic starhalf ontopic star
Beiträge: 174
Erhaltene Danke: 43



BeitragVerfasst: Do 23.05.13 15:56 
Einfaches Problem (n Karten mischen), einfache Lösung (n-1 mal tauschen):
ausblenden 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 Threadstarter
ontopic starontopic starontopic starontopic starontopic starontopic starontopic starhalf ontopic star
Beiträge: 600
Erhaltene Danke: 23


Delphi 7 PE
BeitragVerfasst: Do 23.05.13 19:38 
user profile iconjfheins hat folgendes geschrieben Zum zitierten Posting springen:
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
ausblenden Delphi-Quelltext
1:
2:
3:
For n := Count-1 downto 0 do
//oder
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:
ausblenden Delphi-Quelltext
1:
2:
3:
Random(Count) //bei index-begin = 0
//oder
Random(Count) +1 //bei index-begin = 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 ...

_________________
Sucht "neueres" Delphi :D
Wer nicht brauch was er hat, brauch auch nicht was er nicht hat!