Komplexe Permutation in JavaScript

Stefan · 19.10.10, 14:14 Uhr · Allgemeines, JavaScript

Wie im anderen Artikel bereits für PHP beschrieben, gibt es hier die gleiche Funktionalität der komplexen Permutation mehrerer Elemente in n Varianten noch mal als JavaScript Funktion, um z.B. durch die XPath Extension auch dort alle relevanten Varianten erstellt werden können:

/**
 * generates permutation of n elements with a length of n
 *
 * @example
 * given:
 * var tags = ['div', 'section'];
 * var length = 2;
 *
 * result:
 * [
 *  ['div', 'div'],
 *  ['div', 'section'],
 *  ['section', 'div'],
 *  ['section', 'section']
 * ]
 *
 * call:
 * var result = permutation(tags, length);
 *
 * @param array  {Object} array list of elements to permute
 * @param length {Number} total dimension to permute
 * @returns {Object} array of items
 */
var permutation = function (array, length) {
    var _result = [];

    // do permutations
    var _doPermute = function(array, length) {
        var res = [];
        for (var i = 0; i < array.length; i++) {
            var row = {};
            if (length == 1) {
                row[array[i]] = true;
            } else {
                if (!row[array[i]]) {
                    row[array[i]] = [];
                }
                row[array[i]].push(_doPermute(array, length - 1));
            }
            res.push(row);
        }
        return res;
    };

    // clean resulted permutations from non real nested array items
    var _cleanArray = function(array, prefix) {
        for (var key in array) {
            if (typeof(array[key]) != 'object') {
                _result.push(prefix.concat([key]));
            } else {
                if (/^\d+$/.test(key) === false) {
                    prefix = prefix.concat([key]);
                }
                _cleanArray(array[key], prefix);
            }
        }
    }

    // call functions
    var tmpResult = _doPermute(array, length),
        tmpArray = {},
        output = [];

    _cleanArray(tmpResult, []);

    for (var i = 0; i < _result.length; i++) {
        var arrayKey = _result[i].join('/');
        tmpArray[arrayKey] = _result[i];
    }

    // store unique items in resultset
    for (var key in tmpArray) {
        output.push(tmpArray[key]);
    }
    return output;
};