Unsortiertheit einer Zahlenreihe bestimmen
-
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.
-
knivil schrieb:
Bashar schrieb:
Also immer? Das ist sicherlich nicht mit Sortiertheit gemeint.
Nein, ich habe nicht auf das Auswahlaxiom angespielt.
Das brauchen wir hier nicht.
Ich dachte "bezueglich" reicht aus, weil Ordnung ohne Bezug macht keinen Sinn.
Du schreibst immer sehr knapp, ich geh bei deinen Postings davon aus, dass kein Wort zuviel und keins zuwenig ist, und jedes an seinem durchdachten Platz steht.
-
Ich nimm dir das jetzt auch nicht uebel
Das brauchen wir hier nicht.
Aber ich dachte der Wohlordnungssatz folgt aus diesem, bzw. ist aequivalent. Zumindestens dachte ich, du spielst darauf an. Nun gut bei endlichen Mengen brauchen wir den nicht, da die Relation einfach aufgezaehlt werden kann.
-
Mit Häufigkeitsanalysen und Referenzmustern dürfte man schon recht weit kommen.
Als Kriterium für "Sortiertheit" kann man u.a. einen Sortieralgo hernehmen, der schneller ist, desto "sortierter" das Material ist, als Schablone ein oder mehrere Refernzmuster.
Beim Skatspiel von http://www.skat-spiel.de/ fand ich sehr störend, das man öfter fast die gleichen Karten wie vorher auch schon bekam. Das ist zwar in der Realität manchmal ganz ähnlich, aber nicht so extrem. So hat man häufiger so etwas wie grüne Welle über mehrere Spiele.
(neben einer anderen Macke, dass man das Spiel(im Spiel) nicht sinnvoll abbrechen kann (s.o.), ist das Programm recht gut).
-
8589934592 schrieb:
Als Kriterium für "Sortiertheit" kann man u.a. einen Sortieralgo hernehmen, der schneller ist, desto "sortierter" das Material ist, als Schablone ein oder mehrere Refernzmuster.
Gleiches Problem wie beim Vorschlag über Kompressionsalgorithmen. Sortiertheit im Sinne eines Sortieralgorithmus ist ganz was anderes als man allgemein darunter versteht.
Beispiel ein Sortieralgorithmus, der durch Vertauschungen die Elemente an ihren Platz bringt. Dann braucht er bei "ABCDFEG" nur wenig zu tun und ist schnell fertig. Das ist es auch, was du beschreibst. Jedoch bei der nach intuitivem Verständnis sogar noch besser sortierten Folge "GFEDCBA" braucht er maximal lange und würde diese als vollkommen unsortiert ansehen.
Beim Skatspiel von http://www.skat-spiel.de/ fand ich sehr störend, das man öfter fast die gleichen Karten wie vorher auch schon bekam. Das ist zwar in der Realität manchmal ganz ähnlich, aber nicht so extrem. So hat man häufiger so etwas wie grüne Welle über mehrere Spiele.
Das klingt sehr ungewöhnlich. Es wäre für den Programmierer ein Einzeiler, die Karten perfekt zu mischen. Die Modellierung eines realen Mischvorgangs wäre hingegen sowohl von der Planung als auch von der Umsetzung her sehr aufwändig. Und das Ergebnis auf jeden Fall schlechter. Wieso sollte man so etwas tun?
Ich vermute, du siehst hier Muster im Zufallsrauschen, die gar nicht da sind. Das machen Menschen dauernd. Es gibt zwar sehr, sehr viele Handkartenkombinationen, so dass man niemals erwarten kann, eine bestimmte Hand zu erhalten. Aber es gibt auch sehr, sehr viele Hände, bei denen jeweils ein paar Karten gleich oder ähnlich sind, so dass es durchaus realistisch ist, mehrmals nacheinander ähnliche Hände zu bekommen. Ein Mensch geht dann gleich von einem Muster aus, weil wir so geschaltet sind, Muster zu suchen.
-
knivil schrieb:
Das brauchen wir hier nicht.
Aber ich dachte der Wohlordnungssatz folgt aus diesem, bzw. ist aequivalent.
Die Mindestanforderung, die ich an eine "Folge" stelle ist, dass die Indexmenge wohlgeordnet ist. Das zu sichern ist das Problem desjenigen, der die Folge vorgibt, nicht meins, also brauch ich das Axiom nicht.
Zumindestens dachte ich, du spielst darauf an.
Nein eigentlich nur auf das triviale: a < b definiert dadurch, dass a in der Folge vor b kommt.
Das ganze funktioniert natürlich nur, wenn alle Elemente der Folge verschieden sind, wie in dem Kartenmodell. (1, 2, 1) ist bezüglich keiner Ordnungsrelation sortiert.
BTW ich möchte noch einen Begriff in den Raum werfen: Kolmogorov-Komplexität, die kürzestmögliche Länge eines Programms, die einen gegebenen String erzeugt als Maß für den Informationsgehalt. Der einzige Willkürfaktor ist dabei die verwendete Programmiersprache. Da sollte man vielleicht Turingmaschinen oder sowas verwenden.
-
Bashar schrieb:
Kolmogorov-Komplexität
Als Definition tauglich, als Berechnungsvorschrift aber nicht.
-
SeppJ schrieb:
8589934592 schrieb:
Als Kriterium für "Sortiertheit" kann man u.a. einen Sortieralgo hernehmen, der schneller ist, desto "sortierter" das Material ist, als Schablone ein oder mehrere Refernzmuster.
Gleiches Problem wie beim Vorschlag über Kompressionsalgorithmen. Sortiertheit im Sinne eines Sortieralgorithmus ist ganz was anderes als man allgemein darunter versteht.
Nach meiner Definition ist eine umgekehrte Reihenfolge mit dem Bespielalgo als Kriterium maximal Unsortiert. Das stimmt vielleicht aus jener Sicht nicht, wäre aber aus anderer Sicht nicht falsch. Man könnte die Auswertung der Zeiten dahingehend erweitern, dass zu lange Zeiten auch nicht akzeptiert werden - so ähnlich wie Extremwerte herausstreichen, etwa um Stichproben zurechtzuschneiden.
SeppJ schrieb:
8589934592 schrieb:
Beim Skatspiel von http://www.skat-spiel.de/ fand ich sehr störend, das man öfter fast die gleichen Karten wie vorher auch schon bekam. Das ist zwar in der Realität manchmal ganz ähnlich, aber nicht so extrem. So hat man häufiger so etwas wie grüne Welle über mehrere Spiele.
Das klingt sehr ungewöhnlich. Es wäre für den Programmierer ein Einzeiler, die Karten perfekt zu mischen.
Genau diesen Satz müssen wir aber, nachdem, was wir bisher wissen(oder nicht wissen) bezweifeln?
(oder ...oh gott!)
