Unsortiertheit einer Zahlenreihe bestimmen
-
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.
-
krümelkacker schrieb:
Kolmogorov-Komplexität würde mich hier überhaupt nicht interessieren. Es geht doch "nur" darum, dass jede Permutation gleichwahrscheinlich ist.
Ne, das hätte mein Verfahren auf S.1 ja auch gelöst. Aber dann kam, dass Karten möglichst gut verteilt sein sollen, also z.B. je nach Spiel nicht ganz viele Karten gleicher Klasse zusammensind oder so.
In meinen Augen ist das aber unsinnig. Wenn der Zufall so will, hat man eben alle Klassen auf einmal. Dann macht das Spiel vielleicht keinen Spaß, aber es ist eben zufällig.
-
Eisflamme schrieb:
In meinen Augen ist das aber unsinnig. Wenn der Zufall so will, hat man eben alle Klassen auf einmal. Dann macht das Spiel vielleicht keinen Spaß, aber es ist eben zufällig.
So eine Konstellation ist aber auch extrem unwahrscheinlich. Wenn es nicht darum geht, Mischverfahren zu vergleichen, sondern ein gutes Mischverfahren zu wählen, dann ist rein zufällige Anordnung sicher eines oder das beste Verfahren.
-
SeppJ schrieb:
Dass ein üblicher PRNG halbwegs gute Zufallszahlen liefert, darf ja wohl angenommen werden.
Jetzt wäre wohl noch zu klären, was genau "halbwegs gute Zufallszahlen" sind.
(Bei der Beziehung geordneter -> schneller versuche ich nichts umzudefinieren. Es ging mir eher darum, auf diese natürliche Beziehung hinzuweisen, und Anhaltspunkte zu finden. (Vielleicht ist ein rein sequentieller Algorithmus auch eher ungeeignet für die Aufgabe, vielleicht auch nicht, aber darum geht es in erster Line nicht.)
-
8589934592 schrieb:
SeppJ schrieb:
Dass ein üblicher PRNG halbwegs gute Zufallszahlen liefert, darf ja wohl angenommen werden.
Jetzt wäre wohl noch zu klären, was genau "halbwegs gute Zufallszahlen" sind.
Wie ich bei meinem Vorschlag auf Seite 3 schon anmerkte und wie Michael E. auf Seite 1 sagte:
SeppJ schrieb:
Das ist übrigens dem sehr ähnlich, was die Tests machen, die man auf Zufallszahlengeneratoren los lässt, wie Michael E. schon anmerkte.
Michael E. schrieb:
Schau dir mal an, wie die Güte von PRNGs abgeschätzt wird.
Also:
http://en.wikipedia.org/wiki/Randomness_testMan muss hier noch beachten, dass man eine Stichprobe ohne Zurücklegen aus einer Gesamtmenge hat, wodurch diese Tests nicht direkt anwendbar sind. Aber ich habe ja schon beschrieben, wie man das machen könnte. Eigentlich war der Thread schon mit der 2. Antwort (Michael E.) gelöst.
edit: Und ich sehe gerade, ein paar weitere Antworten auf der ersten Seite beschreiben das gleiche.
