Javascript returning a sparse array from "push" operations despite the logged value having numbers

Question

I'm working on my backtracking algorithim skills and I've run into a problem. The problem is to generate all permutations of an array of distinct integers i.e permute([1,2,3]) => [[1,3,2], [1,2,3], [2,1,3], [2,3,1], [3,1,2], [3,2,1]]

I have the written like so:

var permute = function(nums) {
        var backtrack = function(nums, chosen, solutions) {
          if (chosen.length === nums.length) {
              // I'm not mutating nums.length so I don't get why this is pushing on empty arrays
              console.log(chosen); 
              solutions.push(chosen);
          } else {
              for (let i = 0; i < nums.length; i++) {
                  if (!chosen.includes(nums[i])) {
                      chosen.push(nums[i]);
                      backtrack(nums, chosen, solutions);
                      chosen.pop();              
                  }
              }
          }
        }
        var chosen = [];
        var solutions = [];
        backtrack(nums, chosen, solutions);
        return solutions;
}

When I log out the chosen array variable on line 5, it has 4 values as I expect. However, I noticed that Javascript claims it has 4 values but a length property of zero. This means that when I run my function permute([1,2,3]), I get a result of [[], [], [], [], [], []] or nums.length factorial number of sparse arrays. I suspect that my loop is the problem and I'm not fully understanding all these array references I'm passing around but I'm not sure what else to do. Logging out chosen is what I expect. I appreciate any help or further readings.

This is not specific to the Chrome console environment. If I run this inside of a node repl I see the same behavior.

See https://stackoverflow.com/questions/23429203/weird-behavior-with-objects-console-log — CertainPerformance, Aug 17 '18 at 06:42
I don't see any sparse arrays in your code, since you're always `push`ing. (that's a good thing, sparse arrays should never exist if you can avoid it) — CertainPerformance, Aug 17 '18 at 06:43

Nina Scholz · Accepted Answer · 2018-08-17T07:01:44.497

You mutate the same array chosen. For pushing a result, you could add a copy of the chosen array.

solutions.push(chosen.slice());

The part

for (let i = 0; i < nums.length; i++) {
    if (!chosen.includes(nums[i])) {
        chosen.push(nums[i]);
        backtrack(nums, chosen, solutions);
        chosen.pop();
    }
}

iterates all elements of nums and checks if the value is already in chosen. If not, the value is pushed into the array chosen. Then the backtracking takes place and after this, the last value of chosen gets removed.

At the end, chosen is an empty array, which is the result of the pushing of the same array/object reference.

As result, you get the right amount of items (6), but always the same empty array.

var permute = function(nums) {
        var backtrack = function(nums, chosen, solutions) {
          if (chosen.length === nums.length) {
              // I'm not mutating nums.length so I don't get why this is pushing on empty arrays
              //console.log(chosen); 
              solutions.push(chosen.slice());
          } else {
              for (let i = 0; i < nums.length; i++) {
                  if (!chosen.includes(nums[i])) {
                      chosen.push(nums[i]);
                      backtrack(nums, chosen, solutions);
                      chosen.pop();              
                  }
              }
          }
        }
        var chosen = [];
        var solutions = [];
        backtrack(nums, chosen, solutions);
        return solutions;
}

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

.as-console-wrapper { max-height: 100% !important; top: 0; }

Thanks, this works well. Can you explain a little more about why the original value of `chosen` [] was part of the solutions when the if block that compares array lengths would not run with it? i.e. [].length will never equal [1,2,3].length? — johnnyutah, Aug 17 '18 at 06:53

Javascript returning a sparse array from "push" operations despite the logged value having numbers

1 Answers1