1. Einleitung
Dieser Artikel erläutert das prognostizierbare Mischen von Arrays. Ziel ist es also, ein Array zwar zufällig zu mischen, diesen Mischvorgang aber von einem Schlüssel bzw. Seed abhängig zu machen, sodass er bei gleichem Schlüssel/Seed auch gleich abläuft. Dies kann beispielsweise dann nützlich sein, wenn man in einer Box auf einer Webseite Links anzeigen will, die auf zufällige Unterseiten verweisen, sich aber gleichzeitig bei jedem Neuladen der Seite nicht verändern sollen (die Seite soll also möglichst statisch sein).
Vorgestellt werden hier drei verschiedene Methoden, um dies zu erreichen. Die erste greift auf die PHP-Methode shuffle() zurück und sollte in den allermeisten Fällen verwendet werden. Die beiden anderen Methoden stellen eigene Implementierungen dar, welche beispielhaft zeigen, wie man das Ziel jeweils mit einem eigenen Algorithmus erreichen könnte.
2. Mischen mit shuffle()
Die mit Abstand einfachste Methode zum Mischen von Arrays ist die Verwendung von shuffle(&$array). Dazu muss das zu mischende Array nur an shuffle() übergeben werden. Da die Übergabe per Referenz erfolgt, ist das Array direkt gemischt, die Rückgabe von shuffle() kann ignoriert werden. Man sollte das Array daher vorher kopieren, wenn man es noch in seiner ursprünglichen Form weiterverwenden will.
shuffle() bietet von sich aus keinen Parameter an, über den ein Seed übergeben werden könnte, um ein vorhersehbares Mischen zu bewirken. Auch die Dokumentation auf php.net gibt keinen Hinweis diesbezüglich. Tatsächlich aber greift shuffle() offenbar auf den alten Zufallsgenerator in PHP zurück. Für diesen lässt sich der Seed über srand($seed) festlegen, wodurch auch das Verhalten von shuffle() prognostizierbar wird. Das nächste Beispiel zeigt die Anwendung anhand zweier gleicher Mischvorgänge:
<?php // Erster Test $arr = array(0, 1, 2, 3, 4, 5); srand(1000); shuffle($arr); print_r($arr); // Ein zweites mal, um zu zeigen, dass das Mischen bei gleichem Seed // ebenfalls immer gleich ablaeuft $arr = array(0, 1, 2, 3, 4, 5); srand(1000); shuffle($arr); print_r($arr); ?>
Array
(
[0] => 5
[1] => 1
[2] => 3
[3] => 4
[4] => 2
[5] => 0
)
Array
(
[0] => 5
[1] => 1
[2] => 3
[3] => 4
[4] => 2
[5] => 0
)
Im nächsten Beispiel wird shuffle() in eine eigene Funktion ausgelagert, welche bereits einen Seed erwartet. Die Funktion setzt den Zufallsgenerator automatisch auf den gewünschten Seed, wendet ein mal shuffle() an und gibt das Ergebnis zurück. Das ursprüngliche Array bleibt erhalten und kann weiterverwendet werden.
<?php
function shuffle_seed($arr, $seed) {
srand($seed);
shuffle($arr);
return $arr;
}
// Erster Test
$arr = array(0, 1, 2, 3, 4, 5);
print_r(shuffle_seed($arr, 1000)); // erster Test
print_r(shuffle_seed($arr, 1000)); // zweiter Test
?>
Array
(
[0] => 5
[1] => 1
[2] => 3
[3] => 4
[4] => 2
[5] => 0
)
Array
(
[0] => 5
[1] => 1
[2] => 3
[3] => 4
[4] => 2
[5] => 0
)
3. Mischen durch zufälliges Vertauschen
Eine weitere mögliche Methode zum Mischen eines Arrays ist es, über alle Werte im Array zu iterieren und jeden einzelnen mit einem zufälligen anderen Wert im Array zu tauschen. Am Ende des Durchlaufens des Arrays sollte (fast) jeder Wert ein mal seine Position gewechselt haben. Die nachfolgende Funktion „seededShuffle($arr, $seed)” implementiert dieses Verhalten. Sie iteriert mit einer for-Schleife über alle Werte im Array. Bei jeder einzelnen Iteration wird der Schlüssel eines zufälligen anderen Werts im Array gebildet. Die Zufallsberechnung erfolgt über mt_rand(min, max), wobei min dem Wert 0 (niedrigster Schlüssel) und max dem Wert count($arr)-1 (größtmöglicher Schlüssel) entspricht. Um sicherzustellen, dass die Schlüssel von 0 an durchnummeriert sind (0, 1, 2, 3, ...) wurde vor der Schleife noch array_values() auf das Array angewendet. Damit das Mischen immer gleich verläuft, wird einmalig am Anfang der Funktion mt_srand($seed) aufgerufen, wodurch der Seed des Zufallsgenerators auf $seed gesetzt wird. Alle nachfolgend generierten Zufallszahlen sind von diesem Seed abhängig. Bei gleichem Seed werden auch gleiche Zufallszahlen erzeugt.
<?php
function seededShuffle($arr, $seed) {
mt_srand($seed);
$arr = array_values($arr);
$c = count($arr);
$out = array();
$tmp = null;
// durchlaeuft alle Elemente und vertauscht jedes
// mit einem zufaelligen anderen Element im Array
for ($x=0; $x<$c; ++$x) {
$rnd = mt_rand(0, $c-1);
$tmp = $arr[$rnd];
$arr[$rnd] = $arr[$x];
$arr[$x] = $tmp;
}
return $arr;
}
$arr = array(0, 1, 2, 3, 4, 5, 6, 7, 8, 9);
$arr = seededShuffle($arr, 999666333);
var_dump($arr);
// Wiederholung, um zu zeigen, dass das Mischen immer gleich ablaeuft
$arr = array(0, 1, 2, 3, 4, 5, 6, 7, 8, 9);
$arr = seededShuffle($arr, 999666333);
var_dump($arr);
?>
array(10) {
[0]=>
int(0)
[1]=>
int(3)
[2]=>
int(7)
[3]=>
int(5)
[4]=>
int(6)
[5]=>
int(4)
[6]=>
int(8)
[7]=>
int(2)
[8]=>
int(1)
[9]=>
int(9)
}
array(10) {
[0]=>
int(0)
[1]=>
int(3)
[2]=>
int(7)
[3]=>
int(5)
[4]=>
int(6)
[5]=>
int(4)
[6]=>
int(8)
[7]=>
int(2)
[8]=>
int(1)
[9]=>
int(9)
}
4. Mischen durch zufälligen Schlüssel und ksort()
Die nächste Funktion „seededShuffleBySort($arr, $seed)” verwendet ebenfalls den Zufallsgenerator als Basis, das grundsätzliche Vorgehen ist aber anders. Diesmal werden per foreach-Schleife nacheinander alle Elemente aus $arr in ein Ausgabearray $out übertragen. Während der Iteration wird jeweils für jedes Element ein neuer Schlüssel generiert. Dieser Schlüssel ist zufällig gewählt aus dem Bereich zwischen 0 und 10.000 mal der Anzahl der Elemente in $arr. Nach Ende der foreach-Schleife wird ein mal ksort($arr) auf das Array $arr angewendet. Dadurch wird dieses anhand seiner Schlüssel aufsteigend sortiert. Da diese zufällig generiert wurden, ist nachher auch die Ordnung der Elemente im Array zufällig. Zuletzt wird das Ausgabearray noch an array_values() übergeben, um die zufälligen Schlüssel in solche umzuwandeln, die mit 0 beginnen (0, 1, 2, 3, ...).
<?php
function seededShuffleBySort($arr, $seed) {
mt_srand($seed);
$c = count($arr);
$out = array();
// jedem Element einen zufaelligen neuen Schluessel zuordnen
foreach ($arr as $val) {
// Es wird solange ein Zufallswert zwischen 0 und Anzahl der Element im Array mal 10000 gebildet
// bis der Zufallswert noch nicht durch einen anderen Schluessel belegt ist.
// Bei Kollisionen wuerden sonst Werte ueberschrieben werden.
// *10000 erfolgt hier, damit der Bereich der Zufallszahlen moeglichst gross ist und es nur selten zu
// Kollisionen kommt.
do {
$newKey = mt_rand(0, $c * 10000);
} while (isset($out[$newKey]));
$out[$newKey] = $val;
}
// anhand der zufaelligen Schluessel sortieren
ksort($out);
// Rueckgabe, aber ohne die Zufallsschluessel
// (stattdessen mit Schluessel der Art 0, 1, 2, 3, 4, ...)
return array_values($out);
}
$arr = array(0, 1, 2, 3, 4, 5, 6, 7, 8, 9);
$arr = seededShuffleBySort($arr, 999666333);
var_dump($arr);
// Wiederholung, um zu zeigen, dass das Mischen immer gleich ablaeuft
$arr = array(0, 1, 2, 3, 4, 5, 6, 7, 8, 9);
$arr = seededShuffleBySort($arr, 999666333);
var_dump($arr);
?>
array(10) {
[0]=>
int(0)
[1]=>
int(3)
[2]=>
int(1)
[3]=>
int(5)
[4]=>
int(4)
[5]=>
int(8)
[6]=>
int(2)
[7]=>
int(6)
[8]=>
int(7)
[9]=>
int(9)
}
array(10) {
[0]=>
int(0)
[1]=>
int(3)
[2]=>
int(1)
[3]=>
int(5)
[4]=>
int(4)
[5]=>
int(8)
[6]=>
int(2)
[7]=>
int(6)
[8]=>
int(7)
[9]=>
int(9)
}