0

I'm stuck with some heap's permutation algorithm. I wrote some JavaScript code to recursively find every possible permutation of a value: either an array or a string. My code seems to work perfectly when I console.log() the permuted values but when I push them to another array I get the same value for all of them. I'm confused.

My code contains two separate functions: one does the swapping of the elements and the other one recursively finds the possible permutation:

arr = ["a", "b", "c"];
newArr = [];

// swap mechanism here
function swap(arr, pos1, pos2) {
    var temp = arr[pos1];
    arr[pos1] = arr[pos2];
    arr[pos2] = temp;
};

function perm(arr, nArr, n) {
    n = n || arr.length; 
    if (n === 1) {
        console.log(arr); // console.log() works great
        newArr.push(arr); // pushing the permuted values does not
    }
    else {
        for(var i = 1; i <= n; i += 1) {
            perm(arr, nArr, n - 1);
            if (n % 2) {
                var j = 1;
            }
            else {
                var j = i;
            }
            swap(arr, j - 1, n - 1);
        }
    }
};
Nimantha
  • 6,405
  • 6
  • 28
  • 69
Wadson Fourrien
  • 3
  • 1
  • Welcome to StackOverflow. Please read and follow the posting guidelines in the help documentation. [Minimal, complete, verifiable example](http://stackoverflow.com/help/mcve) applies here. We cannot effectively help you until you post your MCVE code and accurately describe the problem. We should be able to paste your posted code into a text file and reproduce the problem you described. – Prune Aug 10 '17 at 21:26

1 Answers1

2

This is simple (heap) reference vs. (stack) value question. The reason is quite simple: arr in all recursive calls references the same array in memory. Thus when you call newArr.push(arr) another reference to the same object is added to the result list. And when you do swap, you swap elements for all elements of newArr as they point to the same array. See also Copying array by value in JavaScript for a possible workaround. (Basically use Array.slice method to create an independent copy).

SergGr
  • 23,570
  • 2
  • 30
  • 51
  • Thank you so much, brother. I was so confused but I think I'm understanding what the issue was. One quick question: How come console.log() would show all the permuted values? I don't quite understand that part. – Wadson Fourrien Aug 10 '17 at 21:56
  • @WadsonFourrien, `console.log` show current value at the moment of execution. At that moment the (only) array is in the state you want (and all references from `newArr` point to the same array in that state). But when you call `swap` next time you modify that (the same) array and its state is now different from the one that you've logged last time. It might be helpful to set a breakpoint and look at the `newArr` on 3rd or 4th iteration to see how it contains several references to the same memory. – SergGr Aug 10 '17 at 22:11