10

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.

4

3 回答 3

12

n除了在应该使用的地方使用索引之外，问题n - 1在于您假设必须在调用之间复制数组（即不可变行为）。

该算法假定数组在每个递归步骤中始终相同，因此由于 JavaScript 处理范围的方式，您可以大大简化代码：

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"]
于 2014-12-18T05:54:06.873 回答
10

自 2018 年 1 月以来更新的答案：接受的答案是绝对正确的，但 js 从那时起已经发展。随之而来的是一些新功能，其中 2 个可以帮助解决这个问题。

数组解构：

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

发电机：

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

有了这个，我们可以像这样实现堆的算法：

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

于 2018-01-26T01:39:36.077 回答
3

我分享这个答案是因为我想展示旧 javascript 中的一组狭窄功能也可以简洁明了。有时编写在最古老的 javascript 引擎中运行的代码并轻松移植到其他语言（如 C）是一种优势。在这种情况下使用回调效果很好，因为它使函数可用于更广泛的用途，例如减少大在创建时将一组排列转换为唯一的集合。

非常短的变量名可以使算法更清晰。

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

这是一个有用的测试功能，所以我将它提供给我使用的数据驱动测试套件：

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

于 2018-09-04T19:16:03.013 回答