Permutations via Heap's algorithm with a myste

问题:

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.

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

回答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; }

回答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-