Rearrangements using the secret comma heap algorithm

Question

I spent the whole day (finally) wrapping my head around the permutation algorithm in practice to receive applications on Friday. The heap algorithm seemed to me the simplest and most elegant.

here is an example: http://en.wikipedia.org/wiki/Heap%27s_algorithm

function permutationArr(num) { var str = num.toString(); var arr = str.split(''); var permutations = []; function getPerm(arr,n){ var localArr = arr.slice(0); var i; var swap; var temp; if(n==1){ permutations.push(localArr.toString()); return; } for(i=0;i<n;i++){ getPerm(localArr,n-1); swap = (n%2 ? i: 0); temp = localArr[swap]; localArr[swap] = localArr[n-1]; localArr[n-1] = temp; } } getPerm(arr,arr.length); console.log(permutations); return; } permutationArr(1234); 

The log for the final permutation array is here:

  ["1,2,3,4", "1,3,2,4", "4,2,3,1", "4,3,2,1", "4,1,3,2", "4,3,1,2", "1,,3,4,2", "1,3,,4,2", "4,,3,1,2", "4,3,,1,2", "4,1,3,,2", "4,3,1,,2", "1,2,3,4,", "1,3,2,4,", "4,2,3,1,", "4,3,2,1,", "4,1,3,2,", "4,3,1,2,", "1,,3,4,2", "1,3,,4,2", "4,,3,1,2", "4,3,,1,2", "4,1,3,,2", "4,3,1,,2"] 

It receives the first 12 permutations in order, and then the "," is added mysteriously, and the first 12 permutations are repeated. I'm at a dead end.

EDIT: Above is an updated code considering what the comments said to help. Still only half the permutations.

Answer 1

The problem, besides using the n index, where you should use n - 1 , is that you are assuming that the array should be copied between calls (i.e. immutable behavior).

The algorithm assumes that the array is always the same at every recursive step, so thanks to the way JavaScript handles the scope, you can greatly simplify the code:

 function permutationArr(num) { var arr = (num + '').split(''), permutations = []; function swap(a, b) { var tmp = arr[a]; arr[a] = arr[b]; arr[b] = tmp; } function generate(n) { if (n == 1) { permutations.push(arr.join()); } else { for (var i = 0; i != n; ++i) { generate(n - 1); swap(n % 2 ? 0 : i, n - 1); } } } generate(arr.length); return permutations; } console.log(permutationArr(1234)); 

Output

 ["1,2,3,4", "2,1,3,4", "3,1,2,4", "1,3,2,4", "2,3,1,4", "3,2,1,4", "4,2,3,1", "2,4,3,1", "3,4,2,1", "4,3,2,1", "2,3,4,1", "3,2,4,1", "4,1,3,2", "1,4,3,2", "3,4,1,2", "4,3,1,2", "1,3,4,2", "3,1,4,2", "4,1,2,3", "1,4,2,3", "2,4,1,3", "4,2,1,3", "1,2,4,3", "2,1,4,3"] 

Answer 2

Updated answer from January 2018: The accepted answer is absolutely correct, but since then js has evolved. And with it some new features appear, 2 of the witches can help with this answer.

Array destructuring :

 let [a, b] = [1, 2]; // a=1, b=2 

Generators :

 function *foo { yield 1; yield 2; yield 3; } const bar = foo(); bar.next(); // 1 bar.next(); // 2 bar.next(); // 3 

With this, we can implement the heap algorithm as follows:

 function *generate(arr, n) { if (n === undefined) { n = arr.length; } if (n === 1) { yield arr; } else { for (let i = 0; i < n - 1; i++) { yield *generate(arr, n-1); if (n % 2 === 0) { [arr[n-1], arr[i]] = [arr[i], arr[n-1]]; } else { [arr[n-1], arr[0]] = [arr[0], arr[n-1]]; } } yield *generate(arr, n-1); } } for (let a of generate([1, 2, 3, 4])) { console.log(`[${a.join(', ')}]`); } 

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