Unsortiertheit einer Zahlenreihe bestimmen
-
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!)
-
8589934592 schrieb:
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.
Das ist keine Lösung des Problems. Dein erster Vorschlag versucht die Problemstellung umzudefinieren, so dass sie zu deiner Lösung passt
. Dein zweiter Vorschlag geht an meinem Einwand vorbei. Ich bräuchte bloß 20 Sekunden mehr, um ein Beispiel zu liefern, welches nach dem hier gegebenen Begriff perfekt sortiert ist, aber für den Sortieralgorithmus mittel viele Vertauschungen bedeutet. Wie wäre es mit AZCXEV...EWDYB?SeppJ schrieb:
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!) Warum? Dass ein üblicher PRNG halbwegs gute Zufallszahlen liefert, darf ja wohl angenommen werden.
-
Kolmogorov-Komplexität würde mich hier überhaupt nicht interessieren. Es geht doch "nur" darum, dass jede Permutation gleichwahrscheinlich ist. Dazu kann man eben einen entsprechenden Shuffle-Algorithmus nehmen, der seine Zufallszahlen aus einem genügend großen Entropie-Pool bekommt.
-
SeppJ schrieb:
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.
das ist void.
du willst nicht die kompression testen
du willst sortierverfahren vergleichen.Heißt das, dass die Folge unsortiert ist?
wie definierst du sortiertheit?
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.
lass dich nicht abhalten.[edit]bitte mit referenzfolge die "fuer einen menschen offensichtilch nicht geordnet ist" und dennoch besser komprimiert, z.b. mit lzma
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.
versuche dieses wissen in einen algorithmus zu verwandeln, dann haettest du dem threadstarter vielleicht sehr geholfen.
-
rapso schrieb:
SeppJ schrieb:
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.
das ist void.
du willst nicht die kompression testen
du willst sortierverfahren vergleichen. Ich will weder Sortierverfahren testen, noch habe ich vorgeschlagen, dazu einen Kompressionsalgorithmus zu benutzen.Gibt es da irgendwelche Techniken zu bestimmen wie unsortiert eine Zahlenreihe ist?
Dies ist das Ziel.
Heißt das, dass die Folge unsortiert ist?
wie definierst du sortiertheit?
Ich habe oben einen Vorschlag gemacht, wie eine Berechnungsvorschrift aussehen könnte.
Die hier gezeigte Folge ist offensichtlich sortiert. Jeder Mensch erkennt sofort die Muster. Auch ein automatisierter Randomness Test erkennt sofort ein Muster. Ein üblicher Kompressionsalgorthmus jedoch nicht. Daher taugt der Vorschlag nicht, die Sortiertheit anhand der Kompressionsfähigkeit festzumachen.
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.
lass dich nicht abhalten.[edit]bitte mit referenzfolge die "fuer einen menschen offensichtilch nicht geordnet ist" und dennoch besser komprimiert, z.b. mit lzma
Wozu? Glaubst du mir nicht, dass ich das könnte? Verstehst du nicht, wieso die von mir vorgegebene Zeichenkette so schlecht komprimiert? Ich habe es ausprobiert, sie komprimiert tatsächlich schlecht mit lzma. Kannst du das Muster nicht selber fortführen? Allein, dass du das Muster leicht fortführen könntest, ohne meinen Algorithmus zu kennen, zeigt doch schon, dass es eine ziemlich sortierte Folge ist.
Ich weiß auch nicht, was das mit "fuer einen menschen offensichtilch nicht geordnet ist". Ich muss kein Positivbeispiel bringen. Dies ist ein Gegenbeispiel, bei dem der Vorschlag mit dem Kompressionsalgorithmus offensichtlich versagt.
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.
versuche dieses wissen in einen algorithmus zu verwandeln, dann haettest du dem threadstarter vielleicht sehr geholfen.
Ich habe konkrete Vorschlage gemacht. Andere ebenfalls. Ich sage bloß noch zusätzlich, was an einigen der anderen Vorschlägen nicht stimmt. An diesem Vorschlag stimmt nicht, dass ein Kompressionsalgorithmus eine ganz bestimmte Art von Mustern sucht. Das sind aber längst nicht alle Muster und es ist nicht schwer, leicht zu erkennende Muster zu finden, die durch die gängigen Algorithmen nicht zu komprimieren sind.
-
krümelkacker schrieb:
Es geht doch "nur" darum, dass jede Permutation gleichwahrscheinlich ist.
Das gefällt mir. Bei 32 Karten gibt's evtl ein wenig viele Permutationen, um sinnvoll nachzuzählen. Aber dann zählt man eben was anderes, wie nur die Permutationen der vorderen 20 Karten.
