Recent Changes - Search:

Hauptmenue (edit)

Php /

FakultaetPermutation

<< ErrorReporting | PhpSchnipsel | FalschrumSchreiben >>

Fakultät und Permutation im Bann der Rekursion

Einleitung:

Wikipedia: Permutation | Fakultät | Rekursion | Kombinatorik

Auf den ganzen mathematischen Krams werde ich hier nicht eingehen. Einzig von der Implementierung in PHP soll die Rede sein.


Fangen wir mal mit einer einfachen rekursiven Fakultäts Funktion an:

// Die Fakultät von $zahl berechnen:
function fak($zahl)
{
  if($zahl <= 1) return 1;
  return $zahl * fak($zahl - 1);
}

Eigendlich, so schon ganz Klasse! Allerdings springt der Ergebnis-Datentype ab fak(14) von Integer nach Float um. Danach wirds ungenau, weil PHP keinen passenden Integertype bereitstellt und bei Float-Berechnungen automatisch Nachkommastellen abschneidet.


PHP bietet die BC-Funktionen. Damit lassen sich "riesige" Zahlen verarbeiten.

// Die Fakultät von $zahl berechnen:
function bcfak($zahl)
{
  if(-1 === bccomp($zahl,2)) return 1;
  return bcmul($zahl,bcfak(bcsub($zahl,1)));
}

Dadurch, daß jetzt alle Zahlen als String übergeben und verarbetet werden müssen, ist diese Variante DEUTLICH langsamer.


Tuning!!
Man achte auf die Statische Variable: $cache. In $cache werden alle berechneten Fakultäten gespeichert. Das macht die Funktion zwar zu Anfang langsamer, bei häufiger Nutzung allerdings, braucht fast nie mehr was berechnet werden. Dadurch wird sie blitzschnell.

// Die Fakultät von $zahl berechnen:
function bcfakcache($zahl)
{
  static $cache = array();
  if(-1 === bccomp($zahl,2)) return 1;
  if(isset($cache[$zahl])) return $cache[$zahl];
  return $cache[$zahl] = bcmul($zahl,bcfakcache(bcsub($zahl,1)));
}

Permutation

Hier dreht es sich um das Vertauschen von Array Elementen.

Wenn man nur eine zufällige Kombination braucht:

$feld = array(0,1,2,3,4,5,6);
shuffle($feld);
echo implode(' ',$feld)."<br>";

Dieses gibt alle möglichen Kombinationen aus:

function perm($pool,$result=array())
{
  if(empty($pool))
  {
   echo implode(' ',$result)."<br>";
  }else
  {
    foreach($pool as $key => $value)
    {
      $neuerpool    = $pool;
      $neuerresult  = $result;
      $neuerresult[]= $value;
      unset($neuerpool[$key]);
      perm($neuerpool,$neuerresult);
    }
  }
}

// Testcode
$feld = array(0,1,2,3,4,5,6);
perm($feld);

Im $feld befinden sich 7 Elemente, also sind damit 7! = 5040 verschiedene Kombinationen möglich. Mit der obrigen perm() Funktion kommt man schnell an die Grenzen des Systems. Ein Array mit 10 Elementen, ist damit kaum noch beherrschbar.


Gezieltes Adressieren von Vertauschungen

Oft braucht man gar nicht alle Vertauschungen, sind ja auch viel zuviele. Also Schluß mit Rekursion und wieder ran an die gute alte Iteration! Mit diesem iterativen Ansatz kann man, auch bei sehr großen Arrays noch, alle Vertauschungen einzeln erreichen.

function permnr($array,$nr)
{
    $anzahl = count($array);
    $result = array();
    $pool   = array_merge(array(),$array); // normalisieren
    $rest   = bcmod($nr,bcfakcache($anzahl)); // wraparound erlauben
    for($i=0;$i<$anzahl;$i++)
    {
      if(-1 === bccomp($rest,1)) return array_merge($result,$pool);
      $wertigkeit = bcfakcache($anzahl-$i-1);
      $offset     = (int)(bcdiv($rest,$wertigkeit));
      $rest       = bcmod($rest,$wertigkeit);
      $result[]   = $pool[$offset];
      unset($pool[$offset]);
      $pool = array_merge(array(),$pool);
    }
    return $result;
}


$feld = array(0,1,2,3,4,5,6,7,8,9,'a','b','c','d','e','f','g','h','i','j','k');
echo 'Mit '.count($feld).' Elementen  gibt es ';
echo bcfakcache(count($feld)).' mögliche Vertauschungen <br>';
$index ="51090942171709439999";
echo implode(' ',permnr($feld,$index)); // vertauschung gezielt holen
echo " ist die Vertauschung Nr: $index<br>";
 

<< ErrorReporting | PhpSchnipsel | FalschrumSchreiben >>

Edit - History - Print - Recent Changes - Search
Page last modified on November 23, 2007, at 01:54 PM