Bit-String-Matrix erzeugen
Codeschnipsel | letzte Änderung am 14. April '11 um 21:50 Uhr
Motivation
Wir möchten eine Matrix erzeugen, die für n Variablen alle möglichen Bitfolgen in ihren Zeilen enthält. Anwendung findet die Matrix zum Beispiel, wenn eine Wahrheitstabelle für einen gegeben booleschen Ausdruck für alle möglichen Zustände der Eingangsvariablen erzeugt werden soll.
Vorüberlegungen
Hilfreich ist es, wenn man sich zunächst überlegt, wie viele Kombinationen an Bitstrings bei n Variablen erzeugt werden müssen und wie die Matrix zum Beispiel für 1 oder 2 Variablen aussehen könnte. Bei n Variablen sind es 2^n verschiedene Kombinationen.
1 Variable
1
0
2 Variablen
1 0
0 0
1 1
0 1
Dabei habe ich die Reihenfolge der Zeilen für die Matrix der 2 Variablen bewusst gewählt, da man so bereits ein Muster erkennen kann, das wir ausnutzen werden.
Die Matrix für eine Variable findet sich nämlich offensichtlich in der Matrix für die 2 Variablen wieder; und das gleich 2 mal.
Wir schreiben eine rekursive Funktion
Unser Rekursionsanfang besteht darin, festzustellen, ob die Anzahl der Variablen 1 beträgt. Ist dies der Fall, erzeugen wir von Hand die oben gezeigte 2x1 Matrix und liefern sie zurück.
<?php
function getBitStringMatrix($num_vars) {
if ($num_vars == 1) {
return array(
array(1),
array(0)
);
}
// ...
}
Für alle anderen Fälle machen wir einen Rekursionsschritt und rufen die Funktion erneut auf, allerdings reduzieren wir beim Aufruf den Parameter, der die Anzahl der Variablen angibt, um 1.
<?php
function getBitStringMatrix($num_vars) {
// ...
$matrix = getBitStringMatrix($num_vars - 1);
// ...
}
Dann bauen wir mit Hilfe der erhaltenen Matrix eine Matrix mit verdoppelter Spalten- sowie Zeilenanzahl auf. Dazu nehmen wir die Matrix und hängen an jede Zeile zunächst eine 0 und wiederholen das Ganze, hängen diesmal allerdings eine 1 an. Rekursiv fortgesetzt erhalten wir so Matrizen für eine „beliebige“ Anzahl an Variablen.
<?php
function getBitStringMatrix($num_vars) {
// Rekursionsanfang
if ($num_vars == 1) {
return array(
array(1),
array(0)
);
}
// Rekursionsschritt
$matrix = getBitStringMatrix($num_vars - 1);
$m = array();
$c = count($matrix);
for ($i = 0; $i <= 1; ++$i) {
for ($j = 0; $j < $c; ++$j) {
$element = $matrix[$j];
$m[] = array_merge($element, array($i));
}
}
return $m;
}
