I have spent the whole day (finally) wrapping my head around a permutation algorithm in practice for an admissions application on Friday. Heap's algorithm seemed most simple and elegant to me.
here is an example of it: 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 permutations 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 gets the first 12 permutations alright, and then a ',' gets added mysteriously, and the first 12 permutations are repeated. I'm stumped.
EDIT: above is the updated code taking into consideration what comments said to help. Still only getting half the permutations.
The problem, besides using index n
where you should be using n - 1
is that you assume the array must be copied between calls (i.e. immutable behaviour).
The algorithm assumes that the array is always the same in each recursive step, so thanks to how JavaScript handles 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));
["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"]
If you love us? You can donate to us via Paypal or buy me a coffee so we can maintain and grow! Thank you!
Donate Us With