Zufällige Mischung

Nicht nur für Kartenspiele

Das zufällige Mischen von Elementen (shuffle) ist als Grundlage jedes Kartenspiels bekannt. Hier wird gezeigt, wie Mischung mit Programmen ausgeführt werden kann.
Algorithmen Ausgewählte IT-Rezepte (Zufallszahlen)
Demonstration Mischen und Sortieren
Algorithmus Erstellung von Mischungs-Programmen

Demonstration von Mischen ↔ Sortieren
Mischung ist die Umkehrung von Sortierung und umgekehrt:




Status: Die Elemente sind geordnet.

  Verzögerung in ms/Schritt
  1 2 3 4 5 6 7 8 9 10 11 12
Alle hier demonstrierten Vorgänge werden verzögert ausgeführt. Damit ihr Browser jeden Schritt einzeln darstellen kann, wird der Vorgang nicht (wie üblich) in Programm-Schleifen ausgeführt, sondern in Einzelschritten, die mit einem Timer Ereignis-gesteuert werden. Interaktion und Animation wurden ausschließlich mit → Javascript und → DOM-Methoden programmiert. Diese Methode garantiert geringste Server-Belastung und erfordert keinerlei spezielle Resourcen an (ihrem) Client-PC.

Algorithmus zum Mischen
Methode:
(1) Weisen sie jedem zu mischenden Element eine Zufallszahl zu.
♦ Details zum Thema Zufallszahlen

(2) Sortieren sie die Elemente nach den Zufallszahlen. 		Zahlreiche Varianten sind möglich. Details finden sie im Internet unter Stichwort "shuffle".
Die hier gezeigte Methode hat den Vorteil, dass nur ein minimales Programm zum eigentlichen Mischen benötigt wird, der Rest wird von jedem beliebigen Sortierprogramm erledigt. (Moderne Programmiersprachen bieten bequeme und sehr schnelle Sortier-Funktionen).
Weiters kann die Mischung durch geeignete Wahl der Zufallszahlen auch auf einen Teil der Elemente beschränkt werden.
► Meist befinden sich die zu mischenden Elemente in einem Array (hier in a1).

► Legen sie ein weiteres Array (hier a2) der gleichen Größe an und füllen sie es mit → Zufallszahlen. Das wird in diesem Beispiel durch die Funktion mix ausgeführt.

► Sortieren sie das Array mit den Zufallszahlen (a2) und gleichzeitig das Array mit den zu mischenden Elementen (a1). Das wird in diesem Beispiel durch die Funktion sort ausgeführt. An deren Stelle kann auch jede andere Sortier-Funktion verwendet werden.

► Zum Austausch von zwei Array-Elementen wird hier die Funktion xchange verwendet.

Falls sich die zu mischenden Elemente nicht in einem Array befinden, können sie diese vor Beginn der Mischung / Sortierung in ein entsprechendes Array einlesen.
Wenn das nicht möglich ist, können sie die Funktion xchange(a1,i,j) so modifizieren, dass die beiden Elemente vertauscht werden.

Diese Methode kann auch auf eine große Anzahl von Elementen angewendet werden. In diesem Fall verzichten sie auf Arrays (zu großer Speicherbedarf) und lesen entsprechende Daten (z.B. von einer Datei oder Datenbank) ein. Der Ersatz von Arrays durch Dateien bedingt allerdings einen bedeutend höheren Zeitaufwand (z.B. Faktor 1000). 		Mischen mit Javascript (vereinfacht):
// Test-Array:
a1 = new Array("weiss","rot","grün","blau","schwarz");
// Hilfs-Array:
a2 = new Array();
// Anwendung:
mix();
sort();

// Funktionen
function mix() {
for(var i=0;i<a2.length;i++) {
a2[i]=Math.random();
}
}

function sort() {
for(var i=0;i<(a2.length-1);i++) {
for(var j=i+1;j<a2.length;j++) {
if(a2[j]<a2[i]) {
xchange(a1,i,j);
xchange(a2,i,j);
}
}
}
}

function xchange(a,i,j) {
// Austausch der Elemente i,j von Array a
var x=a[j];   a[j]=a[i];   a[i]=x;
}
Live-Berechnung mit dem gezeigten Programm:


Tipp: Wiederholen sie Mischen oder Sortieren !
a1 = (weiss,rot,grün,blau,schwarz)
♦ Details zum Thema Array in Javascript, Perl, PHP, VBA

Zum Inhaltsverzeichnis Homepage von PS-Trainer   >   Entwicklung   >   Algorithmen   >   Zufallszahlen   >   Mischen