Unsortiertheit einer Zahlenreihe bestimmen
-
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.
-
Bashar schrieb:
Also immer? Das ist sicherlich nicht mit Sortiertheit gemeint.
Nein, ich habe nicht auf das Auswahlaxiom angespielt. Ich dachte "bezueglich" reicht aus, weil Ordnung ohne Bezug macht keinen Sinn. Aber fuer dich: Wenn es bezueglich einer gegebenen Ordnungsrelation geordnet ist.
-
Bashar schrieb:
knivil schrieb:
Was ist denn Sortiertheit überhaupt?
Wenn es bezueglich einer Ordnungsrelation geordnet ist.
Also immer? Das ist sicherlich nicht mit Sortiertheit gemeint.
Als ich den Eingangsbeitrag gelesen habe, musste ich sofort an Entropie denken. Eine Folge ist unsortiert, wenn es viele Folgen wie diese gibt. Das Problem verlagert sich somit jedoch auf die Definition von "wie diese". Man benötigt möglichst viele "makroskopische" Größen (um beim Entropiebegriff der Physik zu bleiben), die einer Kette zugeschrieben werden können. Das kann alles sein. Beispielsweise die Häufigkeit der Folge zwei gleicher Buchstaben oder wie oft zwei Buchstaben mit Abstand (in der Folge) von 4-8 einen Abstand (im Alphabet) < 5 haben. Nicht nur sind der Phantasie hier keine Grenzen gesetzt, nein man möchte sogar möglichst alle diese Größen betrachten. Das geht natürlich nicht. Daher sollte man sich wohl am ehesten auf Größen konzentrieren, die nur wenige Zeichenglieder in der Berechnung benötigen und bei denen der Abstand nicht all zu groß ist, denn solche Muster fallen am ehesten unter den Begriff der "Unsortiertheit".
Das ist übrigens dem sehr ähnlich, was die Tests machen, die man auf Zufallszahlengeneratoren los lässt, wie Michael E. schon anmerkte. Hier wird jedoch das Ergebnis noch "normiert", da die Zahlen der Folge auch aus einer nicht-Gleichverteilung stammen können.
