查找数组的排列 - 我哪里出错了？

Question

所以我们有一个数组，我需要找到其中项目的所有排列。

例如，

arr = [1, 2] should return [[1, 2], [2,1]]

现在这是我的思考过程：

如果数组为空，它应该返回

[]

，这给了我基本条件。

if(arr.length === 0) return [];

现在我们可以像这样进一步破解这个问题：

permutation([item1, item2]) = [[item1, ...permutation(item2)], [item2, ...permutation(item1)]

// permutation([1, 2, 3]) = [[1, ...permutation(2,3)], [2, ...permutation(1,3)], [3, ...permutation(1,3)]

因此我尝试编码：

function findPermutation(arr){

  function permute(arr){
    if(arr.length === 0) return [];//empty array base condition
    var res= [];
    for(let el of arr){
      //Reducing the array
      var filteredArray = arr.filter(a=> a!== el);
      //taking recursive leap of faith
      var temp = permute(filteredArray);
      res.push([el, ...(temp)])
    }
    
    //I suspect the problem could be here. It doesn't result
   //correctly so final output remains incorrect
    return res;
  }
  
  return permute(arr);
}
console.log(findPermutation([1, 2, 3]))

但不知何故，我在返回

res

时犯了一些错误，导致给出错误的结果。

我哪里错了，上面的思考过程是否正确？

Answer 1

您遵循的方法是正确的。但是，您的实现需要稍作修改。因此，当您将元素推入

res

数组时，您需要将其推入与

permute(filteredArray)

调用返回的每个子排列组合的数组中。实现此目的的一种方法是使用嵌套循环。

function findPermutation(arr) {
  function permute(arr) {
    if (arr.length === 0) return [
      []
    ]; // Return array with an empty array

    const res = [];
    for (let el of arr) {
      const filteredArray = arr.filter(a => a !== el);
      const subPermutations = permute(filteredArray);

      // note the below loop
      for (let subPermutation of subPermutations) {
        res.push([el, ...subPermutation]);
      }
    }

    return res;
  }

  return permute(arr);
}

console.log(findPermutation([1, 2, 3]));