Unsortiertheit einer Zahlenreihe bestimmen
-
Ich habe schon viele Mischmethoden durch und frage mich was die beste ist.
Und warum nimmst du nicht bewaehrte Algorithmen dafuer?
-
Ethon_ schrieb:
Gibt es da schon fertige Überlegungen?
Kenne keine.
Ich würde schauen, was am meisten nervt: Beim Skat liegen beim schlechten Mischer (SM) die Bauern nach dem Mischen noch aufeinander und ein Spieler kriegt drei davon auf einen Schlag. Beim MauMau liegen die vier Siebenen aufeiandender, weil sie im Vorigen Spiel auferinandergelegt wurden. Beim Pokern ist es auch doof, wenn man ständig Päärchen Karten nachzieht. Wobei nur dichte Nähe spürbar nervig ist.
Es gibt auch schlechte Mischer, bei denen die zuletzt gelegte Karte komischerweise beim Austeilen immer der erste kriegt.Ich würde nicht schauen, was ich gut oder schnell programmieren kann, sondern wie nervig welche Mischfehler sind.
WIe zufällig eine Zahlenfolge ist, denke bei der "die hard"-suite wirste viele Ideen finden.
-
Weiß nicht, ob's schon erwähnt wurde, aber für mich ist ein gutes Mischen, wenn ein Blattes zum nächsten Blatt eine Ähnlichkeit von 50% besitzt, wie auch immer man Ähnlichkeit definiert.
Natürlich muss man dann viele Mischdurchläufe machen, um einen guten Mittelwert zu ermitteln. Aber wenn dann herauskommt, dass die mittlere Ähnlichkeit 50% ist, ist das doch gut. Wenn sie 0% ist, dann sorgt das Mischen immer zu einem gegenteiligen Blatt (schlecht) und wenn sie 100% ist, sorgt das Mischen einfach für keinen Unterschied.
Die einzige Frage ist, was für ein Ähnlichkeitsmaß man nutzt, aber da gibt es sicherlich Ansätze.
-
Eisflamme schrieb:
Weiß nicht, ob's schon erwähnt wurde, aber für mich ist ein gutes Mischen, wenn ein Blattes zum nächsten Blatt eine Ähnlichkeit von 50% besitzt, wie auch immer man Ähnlichkeit definiert.
Also wäre für dich
0 5 1 6 2 7 3 8 4 9
ideal?
-
Spricht was dagegen? Wenn alle Ähnlichkeiten gleichermaßen vertreten sind, ist das doch maximal zufällig.
-
Hui, so viele Antworten, danke schon mal.
Viel gute Ideen dabei, ich experimentiere mal.Aber Volkard hat wohl einen Volltreffer gelandet - es hängt sehr vom Spiel ab was gut gemischt überhaupt bedeutet.
Beispielsweise habe ich letztens beim Keller ausmisten meine 10 Jahre alten Magic Karten gefunden und direkt mal damit gespielt. Ich habe ein komplett sortiertes Deck gemischt - erst ab dem dritten Spiel war es wirklich gut spielbar - also alle Länder, Kreaturen, Zauber waren dann gleichmäßig verteilt. Bis dahin haben immer bestimmte Kartenklassen dominiert.
-
Ja, aber wenn es Spielabhängig ist, dann hilft dir ein allgemeins Kriterium nicht so weiter.
Beispiel Magic: wenn am Anfang 5 Runden lang kein land kommt (und du nicht viele Länder auf der Hand hast) dann wird das Spiel normalerwise als schlecht gemischt bezeichnet - auch wenn die Reihenfolge wirklich nur eine zufällige schlechte permutation ist.
Beim Magic strebt man deswegen eine lokal-gute sortierung an (das heißt jede sequenz von x Karten kann als gut gemischt betrachtet werden). Normalerweise wird dort wie folgt gemischt:
Zuerst sortiert man die Karten in 2-3 Bins. Land/Nichtland oder Land/Zauber/Kreatur. Dann werden die Bins jeweils gut gemischt und danach gleichmäßig gestapelt (das heißt 1 Land +1 Nichtland abwechelnd) und zuletzt wird der gesammte Stapel noch wenige male gemischt.
Alternativ: Nach Erzeugung der Bins wird nicht gemischt sondern die Karten gleichmäßig auf 5-7 kleine stapel verteilt und diese dann zufällig aufeinandergelegt. Schlussendlich wird nochmal gemischt.
Diese Mischmethoden sind zwar nicht "komplett zufällig" aber sie sind gut genug um a) zu verhindern dass jemand betrügt und b) ein spannendes Spiel für beide Teilnehmer zu ermöglichen. Die zweite Methode wird auch bevorzugt, weil sie die Anzahl der Mischvorgänge minimiert und damit die Karten schont.
Beim Skat findet man ähnliches. Da wird dann der Bubenstich gesucht und die Buben gleichmäßig auf das Blatt verteilt.
-
Die einfachste und übliche Mischmethode besteht darin, einfach alle Karten zu durchlaufen und jede Karte mit einer zufällig anderen auszutauschen:
// Pseudocode for x = 0 to N-1 swap(x, random(0, N-1))Dies ist ein einfacher O(n)-Algorithmus. Dadurch, daß einzelne Karten dann sogar mehrfach umsortiert werden können, sollte also die "Unsortiertheit" recht hoch sein (d.h. umgekehrt die Wahrscheinlichkeit für sortierte Teilfolgen recht niedrig - aber eben nicht 0, sonst wäre es ja auch wieder schlecht ;-).
-
Th69 schrieb:
Die einfachste und übliche Mischmethode besteht darin, einfach alle Karten zu durchlaufen und jede Karte mit einer zufällig anderen auszutauschen:
// Pseudocode for x = 0 to N-1 swap(x, random(0, N-1))Dies ist ein einfacher O(n)-Algorithmus. Dadurch, daß einzelne Karten dann sogar mehrfach umsortiert werden können, sollte also die "Unsortiertheit" recht hoch sein (d.h. umgekehrt die Wahrscheinlichkeit für sortierte Teilfolgen recht niedrig - aber eben nicht 0, sonst wäre es ja auch wieder schlecht ;-).
-
Th69 schrieb:
// Pseudocode for x = 0 to N-1 swap(x, random(0, N-1))random(0,N-1) sieht für mich fürchterlich schief aus.
Th69 schrieb:
Dadurch, daß einzelne Karten dann sogar mehrfach umsortiert werden können, sollte also die "Unsortiertheit" recht hoch sein
Guten Pseudozufall holt man aus einbem guten Generator. Man verbessert ihn nicht durch durch Wiederholung, damit macht man ihn oft kaputt.
Wie ich den Fragesteller verstanden habe, spielt er Karten. Per Hand! Und möchte nur mit dem Computer verschiedene Mischvarianten ausmessen, z.B. die Folge 1xAbheben, 2xRiffeln, 3xÜberhand, 1x Abheben.
-
@otze: Danke!
Th69 schrieb:
Die einfachste und übliche Mischmethode besteht darin, einfach alle Karten zu durchlaufen und jede Karte mit einer zufällig anderen auszutauschen:
// Pseudocode for x = 0 to N-1 swap(x, random(0, N-1))Dies ist ein einfacher O(n)-Algorithmus. Dadurch, daß einzelne Karten dann sogar mehrfach umsortiert werden können, sollte also die "Unsortiertheit" recht hoch sein (d.h. umgekehrt die Wahrscheinlichkeit für sortierte Teilfolgen recht niedrig - aber eben nicht 0, sonst wäre es ja auch wieder schlecht ;-).
Sieht für mich nach einer schlechteren Version des Fisher-Yates-Shuffle aus.
http://en.wikipedia.org/wiki/Fisher–Yates_shuffle
volkard schrieb:
Th69 schrieb:
Dadurch, daß einzelne Karten dann sogar mehrfach umsortiert werden können, sollte also die "Unsortiertheit" recht hoch sein
Guten Pseudozufall holt man aus einbem guten Generator. Man verbessert ihn nicht durch durch Wiederholung, damit macht man ihn oft kaputt.
Wie ich den Fragesteller verstanden habe, spielt er Karten. Per Hand! Und möchte nur mit dem Computer verschiedene Mischvarianten ausmessen, z.B. die Folge 1xAbheben, 2xRiffeln, 3xÜberhand, 1x Abheben.
Exakt. Auch wenn ich mittlerweile auch schon darauf gekommen bin dass sich wohl je nach Spiel ein Pseudo-Mischverfahren mehr anbietet als zu versuchen das "Beste" General-Purpose Mischverfahren zu finden.
-
-
knivil schrieb:
Ich habe schon viele Mischmethoden durch und frage mich was die beste ist.
Und warum nimmst du nicht bewaehrte Algorithmen dafuer?
Ich glaub' er will in echt Karten spielen. Also so ohne Computer, mit echten Karten in der Hand.
Und will jetzt verschiedene Misch-Techniken vergleichen. Also Karten Mischen, Ergebnis aufschreiben, in ein Computerprogramm füttern und das Programm sagt dann "gut" oder "weniger gut".
-
nuhr schrieb:
-
Das ist nicht "assi", es ist nur ziemlich unfreundlich formuliert.
Stimmt aber grundsätzlich.
-
ich wuerde das bestimmen indem ich ein kontext basiertes kompressionsverfahren drueber laufen lasse und je besser die randomizierung ist, desto schlechte das kompressionsverhaeltnis.
was natuerlich impliziert dass du nicht eine einzige sortierung begutachtest, sondern am besten ein paar tausend sortierergebnisse in eine datei schreibst und diese dann komprimierst.
wenn du rein statistisch/theoretisch bewertest, machst du das ja mit einem verfahren und oft kann man fuer solche verfahren ein pattern finden, was total vorhergesehen, da generiert, ist, aber bei der bewertung sehr gute ergebnisse liefert.
eine kompression hingegen ist wie eine black box, du weisst nicht genau welches pattern gut waere, aber du weisst dass die kompression sich sehr anstrengt wiederholende/redundante pattern zu finden.versuch z.b. lzma von 7z.
-
rapso schrieb:
ich wuerde das bestimmen indem ich ein kontext basiertes kompressionsverfahren drueber laufen lasse und je besser die randomizierung ist, desto schlechte das kompressionsverhaeltnis.
"ABCDEFGHIJKLMNOPQRSTUVWXYZZYXWVUTSRQPONMLKJIHGFEDCBAABBCCDDEEFFGGHHIIJJKKLLMMNNOOPPQQRRSSTTUUVVWWXXYYZZ" komprimiert total schlecht. Heißt das, dass die Folge unsortiert ist? Ich könnte noch lange weiter machen und an die Folge anhängen, so dass das Ergebnis kaum komprimierbar ist, aber für einen Menschen offensichtlich geordnet ist. Das kann ich machen, weil ich sowohl (ungefähr) weiß, was die Kompressionsalgorithmen suchen und weg komprimieren, als auch was der TE wohl mit "Unsortiertheit" meint. Die beiden Begriffe sind verschieden.
-
Oder man hat die Folge bei Z angefangen bis A, dann ist sie nicht sortiert(da sie nicht von A-Z geht und ein Sortieralgo wird wahrscheinlich viele Schritte benötigen und auch ein Packer bringt keine guten Resultate. Also ist ein langer Weg eines Sortieralgo, sowie eine schlechte Kompressionsrate kein Garant für Unsortiertheit sein.
Was ist denn Sortiertheit überhaupt? Vielleicht das nahe beieinander liegen von Nachfolger und Vorgänger?
-
Och, man koennte ein Hidden Markov Model trainieren und schauen ob die versteckten Uebergange alle gleichwahrscheinlich sind. Weiterhin kann die Entropie betrachtet werden.
Was ist denn Sortiertheit überhaupt?
Wenn es bezueglich einer Ordnungsrelation geordnet ist.
-
knivil schrieb:
Was ist denn Sortiertheit überhaupt?
Wenn es bezueglich einer Ordnungsrelation geordnet ist.
Also immer? Das ist sicherlich nicht mit Sortiertheit gemeint.
