Permutations via Heap's algorithm with a mystery comma

Question

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.

Faculty

Arrays are 0-based in javascript. localArr[n] and localArr[1] (when n%2 is 0) look mighty suspicious. Also i<=n-1 can be simplified to the conventional i < n (or i != n). And are you sure you mean to also execute the loop when n is 1 in the base case? – Sonorant

You get just first 6 permutations without commas. – Drool

Line 21 and 22: You're using "n" but it should be "n-1" – Tatia

Cameron Thanks so much for picking them up. Didn't seem to solve my problem. @Tatia BOOM thats it! I am a bufoon! Thankyou so much for your help guys... – Faculty

Oh .. i'm really not with it today. looks like I'm still not getting all the permutations. only a few of them. i might sleep on it. if anyone has any ideas (Y)(Y)(Y) – Faculty

Answer 1

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)); 

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"]

Pa

Your answer was very helpful. I was trying to solve this riddle over the weekend. just as an FYI: It's possible to eliminate the need for that swap function, and do the swapping inside the generate function: arr[n%2 ? 0 : i] = [ arr[n-1], arr[n-1] = arr[n % 2 ? 0 :i]][0]; jsfiddle.net/Paceaux/dyqcfpyu it's not necessarily legible approach, but it eliminates the need for the function or temporary variables. – Complexion

hello, I would like to add comment on this, I am on the same problem, It's hard to understand this code, can you please explain/elaborate more? I'd really appreciate, anyways, thanks for your code – Repose

Answer 2

Updated answer since Jan-2018: The accepted answer is absolutely correct, but js has evolved since then. And with it comes some new features, 2 of which could help 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's algorithm like this:

function *heaps(arr, n) {
  if (n === undefined) n = arr.length;
  if (n <= 1) yield arr;
  else {
    for (let i = 0; i < n - 1; i++) {
      yield *heaps(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 *heaps(arr, n-1);
  }
}


for (let a of heaps([1, 2, 3, 4])) {
  console.log(`[${a.join(', ')}]`);
}

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

Fimbria

This is really great! Side note that you could make this slightly more concise using a default n=arr.length in the function signature, and by using a swap function: const swap = (a, b, arr) => ([arr[a], arr[b]] = [arr[b], arr[a]]); Usage: swap(n % 2 ? 0 : i, n - 1, arr); – Annamariaannamarie

Answer 3

I'm sharing this answer because I want to show how a narrow set of features in old javascript can be concise and clear as well. It is sometimes an advantage to write code that runs in the oldest of javascript engines and ports easily to other languages like C. Using a callback in this case works well because it makes the function available to a wider array of uses such as reducing a large set of permutations to a unique set as they are created.

Very short variable names can make the algorithm more clear.

function swap(a, i, j) { var t = a[i]; a[i] = a[j]; a[j] = t }
function perm(arr, n, cb) {
  if (n === 1) {
    cb(arr);
  } else {
    for (var i = 0; i < n; i++) {
      perm(arr, n - 1, cb);
      swap(arr, n % 2 ? 0 : i, n - 1);
    }
  }
}

perm([1, 2, 3, 4], 4, function(p) {
  console.log(p);
})

This is a useful function for testing, so I made this available to the data-driven test kit I use:

https://github.com/quicbit-js/test-kit#tpermut-

Olivas

note: the value in the callback is the same array with swapped indices. If you want to build a list of unique permutations in the callback, you need to call p.slice() – Gae

Thanks for sharing, this is incredibly useful! Can you elaborate on how to access (and more specifically, loop through) the permutations within p? What is the data type of p that is printing to the console? It appears to be an array of arrays but I am unable to loop through or access/store the individual arrays that are being logged to the console. – Buster

And can this be modified to return all permutations with only a limited number of the n possible values? i.e. return all three-value permutations from a selection of five values? – Buster