使用Heap算法进行排列，带有神秘的逗号

Question

我整天都在研究一个排列算法，以备周五的入学申请。在这之后，我终于弄懂了Heap算法，它对我来说似乎最简单、最优雅。

以下是该算法的示例：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);     

最终排列数组的日志在这里：

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

它可以正确地获取前12个排列，然后神秘地添加了一个逗号，并且前12个排列被重复。我被难住了。

编辑：上面是更新后的代码，考虑到评论中的建议来帮助。仍然只能获得一半的排列。

- zazou

---

在JavaScript中，数组是以0为基准的。当n%2等于0时，localArr[n]和localArr[1]看起来非常可疑。而且i<=n-1可以简化为传统的i < n（或者i != n）。在基本情况下，你确定当n等于1时也要执行循环吗？ - Cameron

你只会得到前6个排列，没有逗号。 - PM 77-1

第21行和22行：您正在使用“n”，但应该是“n-1”。 - Romain

Cameron，非常感谢你帮我拿到它们。似乎并没有解决我的问题。@Romain BOOM 就是这样！我真是个傻瓜！非常感谢你们的帮助... - zazou

哦...今天我真的有点不在状态。看起来我仍然没有得到所有的排列组合，只有其中一些。我可能需要好好休息一下。如果有人有任何想法，请告诉我。(Y)(Y)(Y) - zazou

Answer 1

这里的问题是在使用索引 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"]

- Ja͢ck

---

你的回答非常有帮助。我在周末一直在尝试解决这个谜题。顺便说一下： 可以消除那个交换函数的需要，并在generate函数内部进行交换： arr[n%2 ? 0 : i] = [ arr[n-1], arr[n-1] = arr[n % 2 ? 0 :i]][0];http://jsfiddle.net/Paceaux/dyqcfpyu/这可能不是易读的方法，但它消除了函数或临时变量的需要。 - paceaux

你好，我想在这里添加评论。我遇到了同样的问题，很难理解这段代码。你能否请多加解释或详细说明一下？非常感谢您的帮助，再次感谢您的代码。 - learningjavascriptks

Answer 2

自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

通过这个，我们可以像这样实现 Heap's algorithm:

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

- Olian04

---

这真的很棒！顺便提一下，您可以在函数签名中使用默认的n=arr.length，并使用交换函数使其更加简洁： const swap = (a, b, arr) => ([arr[a], arr[b]] = [arr[b], arr[a]]);用法：swap(n % 2 ? 0 : i, n - 1, arr); - arami

Answer 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-

- Matthew Voss

---

注意：回调函数中的值是具有交换索引的相同数组。如果您想在回调函数中构建唯一排列列表，则需要调用 p.slice()。 - Shanimal

谢谢分享，这非常有用！您能详细说明如何访问（更具体地说，循环遍历）p中的排列吗？打印到控制台的p的数据类型是什么？它似乎是一个数组的数组，但我无法循环遍历或访问/存储被记录到控制台的单个数组。 - joeruzz

这可以被修改以仅返回带有n个可能值限制的所有排列吗？例如，从五个值的选择中返回所有三个值的排列？ - joeruzz