对这个问题的大多数回答都使用昂贵的操作，如连续插入和删除数组中的项，或重复复制数组。

相反，这是典型的回溯解决方案:

function permute(arr) {
  var results = [],
      l = arr.length,
      used = Array(l), // Array of bools. Keeps track of used items
      data = Array(l); // Stores items of the current permutation
  (function backtracking(pos) {
    if(pos == l) return results.push(data.slice());
    for(var i=0; i<l; ++i) if(!used[i]) { // Iterate unused items
      used[i] = true;      // Mark item as used
      data[pos] = arr[i];  // Assign item at the current position
      backtracking(pos+1); // Recursive call
      used[i] = false;     // Mark item as not used
    }
  })(0);
  return results;
}

permute([1,2,3,4]); // [  [1,2,3,4], [1,2,4,3], /* ... , */ [4,3,2,1]  ]

由于结果数组将非常大，因此逐个迭代结果而不是同时分配所有数据可能是一个好主意。在ES6中，这可以通过生成器来完成:

function permute(arr) {
  var l = arr.length,
      used = Array(l),
      data = Array(l);
  return function* backtracking(pos) {
    if(pos == l) yield data.slice();
    else for(var i=0; i<l; ++i) if(!used[i]) {
      used[i] = true;
      data[pos] = arr[i];
      yield* backtracking(pos+1);
      used[i] = false;
    }
  }(0);
}

var p = permute([1,2,3,4]);
p.next(); // {value: [1,2,3,4], done: false}
p.next(); // {value: [1,2,4,3], done: false}
// ...
p.next(); // {value: [4,3,2,1], done: false}
p.next(); // {value: undefined, done: true}

有点晚了，但喜欢在这里添加一个稍微优雅的版本。可以是任何数组…

function permutator(inputArr) {
  var results = [];

  function permute(arr, memo) {
    var cur, memo = memo || [];

    for (var i = 0; i < arr.length; i++) {
      cur = arr.splice(i, 1);
      if (arr.length === 0) {
        results.push(memo.concat(cur));
      }
      permute(arr.slice(), memo.concat(cur));
      arr.splice(i, 0, cur[0]);
    }

    return results;
  }

  return permute(inputArr);
}

添加ES6(2015)版本。也不会改变原始输入数组。工作在控制台Chrome…

const permutator = (inputArr) => {
  let result = [];

  const permute = (arr, m = []) => {
    if (arr.length === 0) {
      result.push(m)
    } else {
      for (let i = 0; i < arr.length; i++) {
        let curr = arr.slice();
        let next = curr.splice(i, 1);
        permute(curr.slice(), m.concat(next))
     }
   }
 }

 permute(inputArr)

 return result;
}

所以…

permutator(['c','a','t']);

收益率…

[ [ 'c', 'a', 't' ],
  [ 'c', 't', 'a' ],
  [ 'a', 'c', 't' ],
  [ 'a', 't', 'c' ],
  [ 't', 'c', 'a' ],
  [ 't', 'a', 'c' ] ]

和…

permutator([1,2,3]);

收益率…

[ [ 1, 2, 3 ],
  [ 1, 3, 2 ],
  [ 2, 1, 3 ],
  [ 2, 3, 1 ],
  [ 3, 1, 2 ],
  [ 3, 2, 1 ] ]

我使用了一个字符串而不是一个数组，似乎我的算法消耗的时间更少。我把我的算法贴在这里，我测量的时间正确吗?

console.time('process');

var result = []

function swapper(toSwap){
    let start = toSwap[0]
    let end = toSwap.slice(1)
    return end + start
}


function perm(str){
    let i = str.length
    let filling = i - 1

    let buckets = i*filling
    let tmpSwap = ''
    for(let j=0; j<filling; j++){
        if(j===0){
            result.push(str)
        }else{
          if(j === 1){
              tmpSwap = swapper(str.slice(1))
              result.push(str[0]+ tmpSwap)
              if(j === filling-1 && result.length < buckets){
                  perm(swapper(str))
              }

          }else{
              tmpSwap = swapper(tmpSwap)
              result.push(str[0]+ tmpSwap)
              if(j === filling-1 && result.length < buckets){
                  perm(swapper(str))
              }
          }
        }
    }

    if(result.length = buckets){
      return result
    }else{
      return 'something went wrong'
    }

}





console.log(perm('abcdefghijk'))

console.timeEnd('process');

一些受到Haskell启发的版本:

perms [] = [[]]
perms xs = [ x:ps | x <- xs , ps <- perms ( xs\\[x] ) ]

function perms(xs) { if (!xs.length) return [[]]; return xs.flatMap(x => { // get permutations of xs without x, then prepend x to each return perms(xs.filter(v => v!==x)).map(vs => [x, ...vs]); }); // or this duplicate-safe way, suggested by @M.Charbonnier in the comments // return xs.flatMap((x, i) => { // return perms(xs.filter((v, j) => i!==j)).map(vs => [x, ...vs]); // }); // or @user3658510's variant // return xs.flatMap((x, i) => { // return perms([...xs.slice(0,i),...xs.slice(i+1)]).map(vs => [x,...vs]); // }); } document.write(JSON.stringify(perms([1,2,3])));

我尝试着做一个简洁而可读的版本，并且是纯函数式编程。

function stringPermutations ([...input]) {
  if (input.length === 1) return input;

  return input
    .map((thisChar, index) => {
      const remainingChars = [...input.slice(0, index), ...input.slice(index + 1)];
      return stringPermutations(remainingChars)
        .map(remainder => thisChar + remainder);
    })
    .reduce((acc, cur) => [...acc, ...cur]);
}

注意，参数格式化将输入字符串转换为数组。不知道这是不是有点太神奇了。我不确定在野外见过。为了真正的可读性，我可能会用input =[…]输入]作为函数的第一行。

我想你可能会喜欢这个:

const permute1 = (arr: any[]): any[][] =>
  arr.reduce(
    (acc, curr) =>
      acc.length > 0
        ? acc
            .map((p) =>
              Array.from({ length: p.length + 1 }, (_, i) =>
                p.slice(0, i).concat(curr, p.slice(i))
              )
            )
            .flat()
        : [[curr]],
    []
  );