Array combinations, permutations and arrangements

combinatorial-analysis.js

// permutation: Permutação
// P(n) = n!
// Exemplo: número de anagramas da palavra LIVRO = P(5) = n!
// Possibilidades de uma fila de 25 pessoas = P(25) = 25!

// combination: Combinação
// C(p,n) = = n! / p!(n - p)!
// Exemplo: formar comissão de 3 pessoas escolhidas entre 10 pessoas. C(3,10) = 10! / 3!(10 - 3)!

// arrangement: Arranjo
// Note que permutação é um caso particular de arranjo onde p = n
// A(p,n) = n! / (n - p)!
// Exemplo: pódio 20 competidores devem ser organizados em 3 lugares e a ordem importa. A(3,20) = 20! / (20 - 3)!

// Note também que o arranjo nada mais é do que uma combinação seguida da permutação do resultado da combinação.

// Usage:
// console.log([1,2,3,4].combinations(2));
// >> [ [ 1, 2 ], [ 1, 3 ], [ 1, 4 ], [ 2, 3 ], [ 2, 4 ], [ 3, 4 ] ]

// console.log([1,2,3,4].permutations());
// >> [ [ 1, 2, 3, 4 ],
// >>   [ 1, 2, 4, 3 ],
// >>   [ 1, 3, 2, 4 ],
// >>   [ 1, 3, 4, 2 ],
// >>   [ 1, 4, 2, 3 ],
// >>   [ 1, 4, 3, 2 ],
// >>   [ 2, 1, 3, 4 ],
// >>   [ 2, 1, 4, 3 ],
// >>   [ 2, 3, 1, 4 ],
// >>   [ 2, 3, 4, 1 ],
// >>   [ 2, 4, 1, 3 ],
// >>   [ 2, 4, 3, 1 ],
// >>   [ 3, 1, 2, 4 ],
// >>   [ 3, 1, 4, 2 ],
// >>   [ 3, 2, 1, 4 ],
// >>   [ 3, 2, 4, 1 ],
// >>   [ 3, 4, 1, 2 ],
// >>   [ 3, 4, 2, 1 ],
// >>   [ 4, 1, 2, 3 ],
// >>   [ 4, 1, 3, 2 ],
// >>   [ 4, 2, 1, 3 ],
// >>   [ 4, 2, 3, 1 ],
// >>   [ 4, 3, 1, 2 ],
// >>   [ 4, 3, 2, 1 ] ]

// console.log([1,2,3,4].arrangements(2));
// >> [ [ 1, 2 ],
// >>   [ 2, 1 ],
// >>   [ 1, 3 ],
// >>   [ 3, 1 ],
// >>   [ 1, 4 ],
// >>   [ 4, 1 ],
// >>   [ 2, 3 ],
// >>   [ 3, 2 ],
// >>   [ 2, 4 ],
// >>   [ 4, 2 ],
// >>   [ 3, 4 ],
// >>   [ 4, 3 ] ]

Array.prototype.combinations = function(p) {
    var combs, head, tailcombs;

    if (p > this.length || p <= 0) {
        return [];
    }

    if (p == this.length) {
        return [this];
    }

    if (p == 1) {
        combs = [];
        for (i = 0; i < this.length; i++) {
            combs.push([this[i]]);
        }
        return combs;
    }

    combs = [];
    for (var i = 0; i < this.length - p + 1; i++) {
        head = this.slice(i, i+1);
        tailcombs = this.slice(i + 1).combinations(p - 1);
        for (var j = 0; j < tailcombs.length; j++) {
            combs.push(head.concat(tailcombs[j]));
        }
    }
    return combs;
};

Array.prototype.permutations = function() {
    if (this.length === 0) {
        return [[]];
    }

    var result = [];

    for (var i = 0; i < this.length; i++) {
        var copy = Object.create(this);
        var head = copy.splice(i, 1);
        var rest = copy.permutations();
        for (var j = 0; j < rest.length; j++) {
            var next = head.concat(rest[j]);
            result.push(next);
        }
    }

    return result;
};

Array.prototype.arrangements = function(p) {
    var combinations = this.combinations(p);
    var arrangements = [];
    combinations.forEach(function(combination) {
        var ps = combination.permutations();
        ps.forEach(function(p) {
            arrangements.push(p);
        });
    });
    return arrangements;
};