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

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)

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

建议实施分析：

当我们调用

permute(filteredArray)

时，它返回一个包含filteredArray所有可能排列的数组（我们的信仰之跃）。由于原始数组中的每个元素都有其唯一的子排列集，因此我们需要迭代所有这些子排列并将当前元素 (

el

) 添加到每个子排列之前。 例如，让我们看一下数组

[1, 2, 3]

。现在，让我们考虑一下

1

：

1. 选取第一个元素

   1

   并过滤数组以获得

   [2, 3]

   。现在我们调用

   permute([2, 3])

   来获取子排列：

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

   （信仰）。

2. 我们需要将元素

   1

   添加到每个子排列：

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

   。这就是为什么我们使用嵌套循环来迭代

   subPermutations

   调用返回的

   permute(filteredArray)

   。

使用扩展语法

...subPermutations

而不循环（根据您的代码）子排列将导致不正确的组合，因为它不会覆盖每个元素的所有可能的排列。

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