[js]Combinations And Permutations(組合せと順列)

PermutationAndCombination.js

// http://d.hatena.ne.jp/zecl/20090127/p1

/** 組み合わせ */
var Combinations = (function() {
    var _public,
        _items = null,
        _length = 0,
        _indices = null,
        _combinations = null,
        _finalIndices = null,
        init = function(items, select) {
            if (!items) {
                throw 'items is null.';
            }
            if (!select) {
                select = items.length;
            }
            if (select < 0) {
                throw 'select < 0.';
            }
            if (items.length < select) {
                throw 'itmes.length < select';
            }
            
            _items = items;
            _length = select;
            _combinations = [];
            _indices = [];
            if (select == 0) {
                return;
            }
            compute();
        },
        compute = function() {
            var arr = new Array(_items.length - 1), i = 0;
            for(; i < _items.length; i++) {
                arr[i] = i;
            }
            getIndices(arr, []);
            for(i = 0; i < _indices.length; i++) {
                _combinations.push(getCurrent(_indices[i]));
            }
        },
        getCurrent = function(indices) {
            var comb = new Array(_length), i = 0;
            for(; i < _length; i++) {
                comb[i] = _items[indices[i]];
            }
            return comb;
        },
        getIndices = function(enables, used) {
            var i = 0, nowEnables, nowUsed;
            for(; i < enables.length; i++) {
                nowEnables = enables.concat();
                nowUsed = used.concat();
                nowUsed.push(nowEnables.splice(0, i + 1)[i]);
                if (nowUsed.length >= _length) {
                    _indices.push(nowUsed);
                } else {
                    getIndices(nowEnables, nowUsed);
                }
            }
        },
        toString = function() {
            return (_items ? (_items.length + 'C' + _length + ' - ' + _combinations.length) : '') + 'Combinations.';
        };
    var Combinations = function() {
        _public = this;
        init.apply(this, arguments);
    };
    Combinations.prototype = {
        get:        function() { return _combinations; },
        toString:   function() { return toString(); }
    };
    return Combinations;
})();

/** 順列 */
var Permutations = (function() {
    var _public,
        _items = null,
        _length = 0,
        _permutations = null,
        _indices = null,
        _finalIndices = null,
        init = function(items, select) {
            if (!items) {
                throw 'items is null.';
            }
            if (!select) {
                select = items.length;
            }
            if (select < 0) {
                throw 'select < 0.';
            }
            if (items.length < select) {
                throw 'itmes.length < select';
            }
            
            _items = items;
            _length = select;
            _indices = [];
            _permutations = [];
            if (select == 0) {
                return;
            }
            compute();
        },
        compute = function() {
            // [ {x:1}, {x:2}, {x:3}, {x:4}, {x:5} ]
            // select:3 => 5P3 = 5*4*3 = 60
            // 0,1,2  0,1,3  0,1,4
            // 0,2,1  0,2,3  0,2,4
            // 0,3,1  0,3,2  0,3,4
            // 0,4,1  0,4,2  0,4,3
            // 1,0,2  1,0,3  1,0,4
            // 1,2,0  1,2,3  1,2,4
            // ...
            // 4,2,0  4,2,1  4,2,3
            // 4,3,0  4,3,1  4,3,2
            var arr = new Array(_items.length - 1), i = 0;
            for(; i < _items.length; i++) {
                arr[i] = i;
            }
            getIndices(arr, []);
            for(i = 0; i < _indices.length; i++) {
                _permutations.push(getCurrent(_indices[i]));
            }
        },
        getIndices = function(enables, used) {
            var i = 0, nowEnables, nowUsed;
            for (; i < enables.length; i++) {
                nowEnables = enables.concat();
                nowUsed = used.concat();
                nowUsed.push(nowEnables.splice(i, 1)[0]);
                if (nowUsed.length === _length) {
                    _indices.push(nowUsed);
                } else {
                    getIndices(nowEnables, nowUsed);
                }
            }
        },
        getCurrent = function(indices) {
            var comb = new Array(_length), i = 0;
            for(; i < _length; i++) {
                comb[i] = _items[indices[i]];
            }
            return comb;
        },
        toString = function() {
            return (_items ? (_items.length + 'P' + _length + ' - ' + _permutations.length) : '') + 'Permutations.';
        };
    var Permutations = function() {
        _public = this;
        init.apply(this, arguments);
    };
    Permutations.prototype = {
        get: function() { return _permutations; },
        toString: function() { return toString(); }
    };
    return Permutations;
})();