Array durch würfeln


DerEisige

Erfahrenes Mitglied
#1
Hallo Leute,
ich hätte da eine allgemeine Frage zu euren Vorgehen, beim durch würfeln der Einträge in einem Array, wie geht ihr dabei vor?
Unbenannt.PNG
 

melmager

Erfahrenes Mitglied
#2
Code:
     // create array list object      
     List arrlist = new ArrayList();
 
     // shuffle the list after fill
     Collections.shuffle(arrlist);
 

Technipion

Erfahrenes Mitglied
#3
Hallo DerEisige,
wie genau ist die Frage gemeint? Meinst du mit Vorgehen die Implementierung in Programmcode? Dann hat melmager ja schon die übliche Lösung gezeigt.

Oder willst du mehr darauf hinaus, welchen Algorithmus wir benutzen würden (sofern wir nicht die Standardfunktionen benutzen)?

Gruß Technipion
 

Technipion

Erfahrenes Mitglied
#6
Ich wollte auf die verschiedenen Algorithmen hinaus.
Okay, dann hat ComFreek ja schon einen der bekanntesten Algorithmen verlinkt. Grundsätzlich lässt sich das Problem "Elemente einer Liste mischeln" auch auffassen als "Finde eine zufällige Permutation der Zahlen 1 bis i, wobei i die Länge einer Liste ist". Und dann interpretiert man die Permutation als neue Liste, bei der an jeder Stelle der Index des Elements aus der ursprünglichen Liste steht. Hast du ja auch als Schema gepostet.

Dazu aber noch einige Hinweise, die vom Algorithmus an sich sogar unabhängig sind:
1) Das Erzeugen von Permutationen ist ein bekanntes Problem mit einer optimalen Laufzeit von O(n). Damit ist auch das Mischeln von Arrays mit O(n) optimal.
2) Bei der Erzeugung von Permutation hängt die Qualität der Ergebnisse entscheidend von der Güte des Zufallsgenerators ab.
Grundsätzlich gibt es für eine Menge mit n Elementen n! mögliche Permutationen (n! = 1 x 2 x 3 x ... x n). Die Fakultätsfunktion wächst aber schnell an...
Meistens verwendet man in der Praxis Pseudozufallsgeneratoren, und die haben eine massive Schwäche: Eine sogenannte Periodenlänge. Die gibt grob gesagt an, nach wie vielen Zahlen man ein Muster in der Verteilung der Zufallszahlen erkennen kann. Ein perfekter Zufallsgenerator würde niemals ein Muster erzeugen!

Wenn die Länge deiner Permutation sich der Periodenlänge des Generators nähert hat das zur Folge, dass zunächst manche Permutationen wahrscheinlicher werden als andere, bzw. ab einem bestimmten Punkt manche Permutationen gar nicht mehr erzeugt werden können. Einfach ausgedrückt: Hat ein Generator weniger interne Zustände als das System, das ich mit ihm erzeugen will, dann sind manche Zustände des Systems nicht erzeugbar. Wie gut du also eine Liste mischeln kannst, hängt davon ab wie gut der Zufallsgenerator ist den du verwendest. Die Standardgeneratoren in C/C++, Java, Python, etc. sind meistens ziemlich lame, dafür aber halt einfach gehalten und auf Geschwindigkeit optimiert. Wird in der Praxis eine bessere Qualität gebraucht trifft man deshalb häufig den Mersenne-Twister an. Hier eine kleine Beispielrechnung um das Problem mit Permutationen besser zu verstehen:

Der Mersenne-Twister hat eine Periodenlänge von etwa 4,3 x 10^6001. Das sind mächtig viele interne Zustände, und das reicht sogar für physikalische Simulationen usw. aus.
ABER: Hat unser Array eine Länge von gerade mal 2080 Elementen, dann sind das schon etwa 2 x 10^6001 mögliche Permutationen. Hier wird also selbst der Mersenne-Twister schon schwache Resultate liefern.

Natürlich sind die kleinen Unebenheiten in der Zufallsverteilung in der Praxis oft vernachlässigbar. Falls doch Wert darauf gelegt wird, gibt es Korrekturverfahren um die Qualität zu verbessern (z.B. mehrmaliges Anwenden). Optimal ist natürlich einen richtigen physikalischen Zufallsgenerator zu benutzen.

Gruß Technipion