Komplexe Permutation mehrerer Elemente in PHP

Stefan · 18.10.10, 17:06 Uhr · PHP

Um komplexe XML Dokumente wie XHTML Seiten oder ähnliches zu durchsuchen, bietet sich die XPATH Extension in den jeweiligen Programmiersprachen an. Ich hatte das Problem, dass ich ein variable Anzahl Tags ab einer bestimmten Verschachtelungstiefe finden musste. Bei zwei unterschiedlichen Elementen ist der Bau der XPath-Query vielleicht noch per Hand möglich, wenn allerdings die Elemente schon auf 3 bei einer Verschachtelungstiefe von 5 wachsen, ist der manuelle Aufwand sehr groß und fehleranfällig.

Beispiel:
Gesucht werden <div> und <span> Elemente bei einer Verschachtelungstiefe von 2.

<?php
$array = array('div', 'span');
$length = 2;
?>

Ergibt:

Array
(
    [div/div] => Array
        (
            [0] => div
            [1] => div
        )

    [div/span] => Array
        (
            [0] => div
            [1] => span
        )

    [span/div] => Array
        (
            [0] => span
            [1] => div
        )

    [span/span] => Array
        (
            [0] => span
            [1] => span
        )

)

Um das manuelle Erstellen zu ersparen, habe ich folgende Klasse erstellt, die die Permutation automatisiert erfolgen zu lassen:

Der PHP Aufruf:

$permutation = Permutation::complex($array, $length);

Die Klasse:

class Permutation {
    protected static $_result = array();

    /**
     * generate complex permutation matrix
     * from a given array with n elements
     * with a given custom length
     *
     * @example
     * given:
     * $array = array('div', 'span');
     * $length = 2;
     *
     * result:
     * Array
     * (
     *    [div/div] => Array
     *        (
     *            [0] => div
     *            [1] => div
     *        )
     *    [div/span] => Array
     *        (
     *            [0] => div
     *            [1] => span
     *        )
     *    [span/div] => Array
     *        (
     *            [0] => span
     *            [1] => div
     *        )
     *    [span/span] => Array
     *        (
     *            [0] => span
     *            [1] => span
     *        )
     * )
     *
     * @param array   $array  list of elements to permute
     * @param integer $length length of array list to permute
     * @return array list of all permuations
     */
    public static function complex($array, $length) {
        $result = self::_doPermute($array, $length);

        self::_cleanArray($result);
        $tmpArray = array();
        for ($i = 0; $i < count(self::$_result); $i++) {
            $arrayKey = implode('/', self::$_result[$i]);
            $tmpArray[$arrayKey] = self::$_result[$i];
        }
        self::$_result = $tmpArray;
        return self::$_result;
    } 

    /**
     * generate permutation of given elements
     * (recursive method)
     *
     * @param array   $array  list with given elements to permute
     * @param integer $length deepth of permutated list
     * @return array $res list of (partly) permuted elements
     */
    private static function _doPermute($array, $length) {
        $res = array();

        for ($i = 0; $i < count($array); $i++) {
            $row = array();
            if ($length == 0) {
                $row[$array[$i]] = true;
            } else {
                for ($z = 0; $z < $length; $z++) {
                    $row[$array[$i]][] = self::_doPermute($array, $length - 1);
                }
            }

            $res[] = $row;
        }
        return $res;
    }

    /**
     * cleanes given enourmous nested array and generate
     * a less nested array with each real array element as key
     * (recursive method)
     *
     * @param array $array  list of nested, unclean elements
     * @param array $prefix list of prefixed elements for clean array
     * @return void()
     */
    private static function _cleanArray($array, $prefix = array()) {
        foreach ($array as $key => $value) {
            if (!is_array($value)) {
                self::$_result[] = array_merge($prefix, array($key));
            } else {
                if (count($value) != 1 && !preg_match('/\d/',$key)) {
                    $prefix = array_merge($prefix, array($key));
                }
                self::_cleanArray($value, $prefix);
            }
        }
    }
}