Luis Eduardo Alvarez Luis Eduardo Alvarez - 9 months ago 28
Javascript Question

Javascript - Permutations remove the duplicates elements

that is found here in stack but i want somes changes.

function perms(data) {
if (!(data instanceof Array)) {
throw new TypeError("input data must be an Array");
}

data = data.slice(); // make a copy
var permutations = [],
stack = [];

function doPerm() {
if (data.length == 0) {
permutations.push(stack.slice());
}
for (var i = 0; i < data.length; i++) {
var x = data.splice(i,1);
stack.push(x);
doPerm();
stack.pop();
data.splice(i, 0, x);
}
}

doPerm();
return permutations;
}

var input = "552".split('');
var result = perms(input);
for (var i = 0; i < result.length; i++) {
result[i] = result[i].join('-');
}


The result of that is :

5-5-2

5-2-5

5-5-2

5-2-5

2-5-5

2-5-5

but , are 3 elements duplicates the result must be :

5-5-2

5-2-5

2-5-5

how can i fix that issue .

Answer Source

Basically, you have one issue,

var x = data.splice(i, 1)[0];
//                       ^^^ is missing

because you get an array with splicing. The result is a deep nested array with

data.splice(i, 0, x);

This inserts the array later on position i.

For preventing duplicates, you need a check, if the actual value is already inserted in the result set with

permutations.some(function (a) {
    return a.every(function (b, j) {
        return stack[j] === b;
    });
}) || permutations.push(stack.slice());

which test the arrays and if no match, the push is performed.

function perms(data) {
    if (!(data instanceof Array)) {
        throw new TypeError("input data must be an Array");
    }

    data = data.slice(); // make a copy
    var permutations = [],
        stack = [],
        hash = Object.create(null);

    function doPerm() {
        if (data.length == 0) {
            permutations.some(function (a) {
                return a.every(function (b, j) {
                    return stack[j] === b;
                });
            }) || permutations.push(stack.slice());
            return;
        }
        for (var i = 0; i < data.length; i++) {
            var x = data.splice(i, 1)[0];
            stack.push(x);
            doPerm();
            stack.pop();
            data.splice(i, 0, x);
        }
    }

    doPerm();
    return permutations;
}

var input = "552".split('');
var result = perms(input);
for (var i = 0; i < result.length; i++) {
    result[i] = result[i].join('-');
}

console.log(result);