Source of packages/Combie/Math/Permutation/Array1Dim.php

<?php
/**
 * Permutationen 1 dim
 *
 * Vertauschen von Array Elementen
 *
 * @filesource
 * @author Combie <uli@combie.de>
 * @version $Id$
 * @package Combie
 * @subpackage Math
 */

namespace Combie\Math\Permutation;

use Combie\Math;

/**
 * Permutation eines 1 dimensionalen Arrays
 *
 * Vertauschen von Elementen
 *
 * @example packages/Combie/tests/math/test_permutation_2dim.php
 * @package Combie
 * @subpackage Math
 */
class Array1Dim
{

/**
 * Interne Variable
 * @var array Zwischenergebnis
 */
  private $result_1dim = array();
  
/**
 * Permutation 1 Dim
 *
 * Interne Helfer Funktion
 * Erzeugt alle Permutationen eines ein Dimensionalen Arrays
 * Vorsicht:
 * Rechenzeit und Speicherbedarf nehmen mit der Anzahl der Elemente
 * exponetial zu. Ab ca 10 Elemente dürfte in einer Webserver Umgebung
 * Schluß sein.
 *
 * @param array Das Array mit den Elementen, welche vertauscht werden sollen
 * @param array Zwischenlager welches durch die rekursions Ebenen mitgeschleppt wird
 * @return void Keine Rückgabe
 */
  private function array_1dim_inner(Array $pool,Array $temp=array())
  {
    if(empty($pool))
    {
      $this->result_1dim[] = $temp;
    }else
    {
      foreach($pool as $key => $value)
      {
        $neuerpool    = $pool;
        $neuertemp    = $temp;
        $neuertemp[]  = $value;
        unset($neuerpool[$key]);
        $this->{__FUNCTION__}($neuerpool,$neuertemp); // rekursion
      }
    }
  }
  
/**
 * Permutation 1 Dim
 *
 * Bedient sich der privaten Methode array_1dim_inner()
 * Erzeugt alle Permutationen eines ein Dimensionalen Arrays
 * Vorsicht:
 * Rechenzeit und Speicherbedarf nehmen mit der Anzahl der Elemente
 * exponetial zu. Ab ca 10 Elemente dürfte in einer Webserver Umgebung
 * Schluß sein.
 *
 * @param array Das Array mit den Elementen, welche vertauscht werden sollen
 * @return array Ein Array mit allen möglichen Vertauschungen
 */
  public function getAll(Array $pool)
  {
    $this->result_1dim = array();
    $this->array_1dim_inner($pool);
    return $this->result_1dim;
  }


/**
 * Permutation eines 1 Dimensionalen Arrays
 *
 * Diese Methode kann auch mit SEHR großen Arrays umgehen, weil sie
 * immer nur eine Vertauschung geziel berechnet.
 *
 * @param array Das Array mit den Elementen, welche vertauscht werden sollen
 * @param string|integer die Nummer der gewünschten Vertauschung
 * @return array Die gewünschte Vertauschung
 */
  public static function permnr(Array $array,$nr)
  {
      $anzahl = count($array);
      $result = array();
      $pool   = array_merge(array(),$array); // normalisieren
      $rest   = bcmod($nr,Math\Bc::Fakultaet($anzahl)); // wraparound erlauben
      for($i=0;$i<$anzahl;$i++)
      {
        if(-1 === bccomp($rest,1)) return array_merge($result,$pool);
        $wertigkeit = Math\Bc::Fakultaet($anzahl-$i-1);
        $offset     = (int)(bcdiv($rest,$wertigkeit));
        $rest       = bcmod($rest,$wertigkeit);
        $result[]   = $pool[$offset];
        unset($pool[$offset]);
        $pool = array_merge(array(),$pool);
      }
  }
}
?>