Unexpected output of Javascript function

Question

I'm trying to write a function that can perform permutation.

For example, if I input [1, 2, 3], the expected answer will be

[ [ 3, 2, 1 ], [ 3, 2, 1 ],[ 3, 2, 1 ],[ 3, 2, 1 ],[ 3, 2, 1 ],[ 3, 2, 1 ] ]

But instead of showing the answer, it returns [[ ],[ ],[ ],[ ],[ ]]

Any ideas?

var permute = (nums) => {
    results = [];

    var backtrack = (nums, result) => {
        if (nums.length === result.length) {
            results.push(result);
        } else {

            for (var i = 0; i < nums.length; i++) {
                if (result.indexOf(nums[i]) > -1) {
                    continue;
                }
                result.push(nums[i]);
                backtrack(nums, result);
                result.pop();
            }
        }
    }
    backtrack(nums, []);
    return results;

};

console.log(permute([1, 2, 3]));

Nina Scholz · Accepted Answer · 2018-05-15 12:35:01Z

5

You could take a local copy of result by slicing this array to prevent the same object reference in the result set.

var permute = (nums) => {
    var results = [];
    var backtrack = (nums, result) => {
        if (nums.length === result.length) {
            results.push(result.slice());           // push copy
        } else {
            for (var i = 0; i < nums.length; i++) {
                if (result.indexOf(nums[i]) > -1) {
                    continue;
                }
                result.push(nums[i]);
                backtrack(nums, result);
                result.pop();
            }
        }
    };
  
    backtrack(nums, []);
    return results;
};

console.log(permute([1, 2, 3]).map(a => a.join(' ')));

A version without pushing and popping.

var permute = (nums) => {
    var results = [];
    var backtrack = (nums, result) => {
        if (nums.length === result.length) {
            results.push(result);
        } else {
            for (var i = 0; i < nums.length; i++) {
                if (result.indexOf(nums[i]) > -1) {
                    continue;
                }
                backtrack(nums, result.concat(nums[i])); // use a new array
            }
        }
    };
  
    backtrack(nums, []);
    return results;
};

console.log(permute([1, 2, 3]).map(a => a.join(' ')));

edited May 15, 2018 at 12:35

answered May 15, 2018 at 12:12

Nina Scholz

388k26 gold badges367 silver badges417 bronze badges

Sign up to request clarification or add additional context in comments.

3 Comments

johnhckuo Over a year ago

Thanks! So this is due to object & array in js are pass by reference; therefore, the references in results become empty after the function is complete right ?

Nina Scholz Over a year ago

right. otoh you need this reference to manipulate with push and pop, but only inside of the actual function. it yould work if you replace result.push(nums[i]); backtrack(nums, result); result.pop(); just with backtrack(nums, result.concat(nums[i]));

johnhckuo Over a year ago

Wow, never thought of that. Thanks buddy ! :)

Emeeus · Accepted Answer · 2018-05-15 12:56:52Z

0

Just Another approach using reverse(), an special case of permutation which OP gives as an example:

var arr = [ [ 3, 2, 1 ], [ 3, 2, 1 ],[ 3, 2, 1 ],[ 3, 2, 1 ],[ 3, 2, 1 ],[ 3, 2, 1 ] ];

var permuted = arr.map((num) => {

    return num.reverse();

});

console.log(permuted);

edited May 15, 2018 at 12:56

answered May 15, 2018 at 12:28

Emeeus

5,2922 gold badges30 silver badges42 bronze badges

2 Comments

Nina Scholz Over a year ago

how does reversing generate a permutation of the data?

Emeeus Over a year ago

The expected response given by OP is a reverse. It's an special case of permutation.

Collectives™ on Stack Overflow

Unexpected output of Javascript function

2 Answers 2

3 Comments

2 Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

2 Answers 2

3 Comments

2 Comments

Your Answer

Sign up or log in

Post as a guest

Related