Forums Neueste Beiträge
 

Beste Mischung

07/01/2012 - 13:04 von Michael Steyer | Report spam
Hallo Newsgroup,

mich beschàftigt schon seit làngerem die Frage, wie man die Qualitàt der
Mischung z.B. eines Kartenspiels quantitativ beschreiben kann. Es geht um
Permutationen der Ausgangsanordung (1,2,..,n), die als zirkulàr angenommen
werden: hinter der letzten Karte kommt wieder die erste, so dass einfaches
Abheben keine Änderung der Mischungsqualitàt bewirkt. Ebenso betrachte ich
eine Richtungsumkehr nicht als Mischung. Als schlechte Mischung soll auch
eine Permutation gelten, die durch abwechselndes Ablegen der Elemente auf k
Stapel (k teilt n) entstanden ist.

Diese Aufgabe kann man auf mindestens 2 Weisen betrachten:

1. Man sucht eine Maßzahl, so dass die Mischung auf irgendeinem
Signifikanzniveau als zufàllig angenommen werden kann. Hier bin ich nicht zu
einem brauchbaren Ansatz gekommen, eine Lösung würde mich aber auch sehr
interessieren.

2. Man sucht eine Art beste Mischung, also eine Permutation, die auf eine zu
definierende Weise möglichst unterschiedlich von der Ausgangsanordnung ist -
so àhnlich wie z.B. das Teilungsverhàltnis des goldenen Schnittes in
gewissem Sinn als irrationalste Zahl bezeichnet werden kann, da die
Kettenbruchentwicklung langsamer als bei jeder anderen Zahl konvergiert.
Vergleichbar dazu wàre z.B. die größte Anzahl der notwendigen
Transpositionen (Vertauschung von Nachbarelementen), aber das lieferte
bisher keine plausiblen Ergebnisse. Diese beste Mischung kann durchaus
konstruiert sein, darf also beim Zufàlligkeitstest (1) durchfallen.

Das beste, was mir bisher dazu eingefallen ist, ist eine Matrix (n-1)x(n-1),
die die Hàufigkeit der Abstànde modulo n von 2 Elementen in vorgegener
Richtung vor und nach der Permutation gegeneinander aufzàhlt. Diese Matrix
hat in ihrer Gesamtheit alle der gewünschten Invarianzeigenschaften. Die
optimale Matrix in dem Sinn 2 wàre dann eine, bei der die Abstànde möglichst
gleich verteilt wàren. Alle Matrixeintràge =1 geht nicht, mindestens ein
Eintrag muss =2 sein. Aber auch das passiert nicht, ab n=5 sind immer Nullen
dabei (warum? Beweis!).

Man kann jetzt die "Beste Mischung" als diejenige bezeichnen, die möglichst
wenig Nullen hat, oder auch als die, die möglichst wenig 2en hat. Allerdings
ist eine der offenen Fragen, ob für alle n eine Permutation existiert, die
keinen Eintrag größer als 2 enthàlt. Für n>! habe ich noch keine derartige
Permuation gefunden; wenn es sie gibt, ist sie ziemlich selten.

Für n=6 ist die "Beste Mischung" u.a. (3,2,6,4,5,1) mit der Differenzmatrix

1,1,2,1,1
2,1,0,1,2
0,2,2,2,0
2,1,0,1,2
1,1,2,1,1

Weiß jemand etwas über das Thema ? Ich hàtte gemeint, das Thema sei
wohlbekannt, da es sicherlich auch für technische Anwendunden von
allgemeinem Interesse ist, aber gefunden habe ich bisher nichts wirklich
Nützliches.

Herzlichen Dank für jeden Beitrag!

Michael
 

Lesen sie die antworten

#1 ram
07/01/2012 - 13:18 | Warnen spam
"Michael Steyer" writes:
mich beschàftigt schon seit làngerem die Frage, wie man die
Qualitàt der Mischung z.B. eines Kartenspiels quantitativ
beschreiben kann.



Durch den Zahlenwert »1«. D. h., wenn man nur eine einzelne
Mischung betrachtet, kann man ihr keine besondere Qualitàt
zuordnen. Eigentlich kann man das nicht einmal für eine endliche
Folge von Mischungen, sondern nur für ein bestimmtes Mischverfahren.

Die Idee, einer einzelnen Mischung eine Qualitàt zuzuordnen,
erinnert mich etwas an die Frage, welche Zahl am zufàlligsten sei.

Aber heuristisch könnte man sagen, daß eine endliche Folge von
Mischungen (oder, wenn Du es unbedingt willst, eine einzelne
Mischung) um so besser ist, desto größer ihre Entropie ist.

Es geht um Permutationen der Ausgangsanordung (1,2,..,n), die
als zirkulàr angenommen werden: hinter der letzten Karte
kommt wieder die erste, so dass einfaches Abheben keine
Änderung der Mischungsqualitàt bewirkt. Ebenso betrachte ich
eine Richtungsumkehr nicht als Mischung. Als schlechte
Mischung soll auch eine Permutation gelten, die durch
abwechselndes Ablegen der Elemente auf k Stapel (k teilt n)
entstanden ist.



Dadurch verminderst Du die Entropie aber, àhnlich, wie wenn
Du sagen würdest »Wenn eine 1 oder 6 kommt, soll noch einmal
gewürfelt werden, da diese beiden Zahlen nicht zufàllig
genug sind.« Insgesamt wird dadurch aber das Ergebnis dann
aber vorhersagbarer.

Weiß jemand etwas über das Thema ? Ich hàtte gemeint, das Thema sei
wohlbekannt, da es sicherlich auch für technische Anwendunden von
allgemeinem Interesse ist, aber gefunden habe ich bisher nichts wirklich
Nützliches.



Du könntest auch sagen, daß Du eine möglichst hohe
algorithmische Komplexitàt haben willst.

http://www.bertramkoehler.de/vom.htm
http://page.mi.fu-berlin.de/alt/vor...andout.pdf
http://de.wikipedia.org/wiki/Kolmog...xit%C3%A4t
http://de.wikipedia.org/wiki/Entropie_(Informationstheorie)

Ähnliche fragen