JavaScript 生成数组的所有可能排列

在给定的问题陈述中，我们被要求通过从暴力方法到优化解决方案，生成输入的数组的所有可能排列。

JavaScript中的数组是什么

如果您熟悉其他编程语言，如C、C++或Java，您一定听说过”数组”这个术语。

在编程中，数组是一个将相似数据元素集中在一起的集合。

现在，一个重要的问题出现了：如果数组在所有语言中通常都是相同的，那么JavaScript如何使数组更加独特和可用？

让我们了解一下JavaScript中数组的整体工作原理。

数组是存储多个元素的对象。由于数组也是对象，它具有一些属性和方法，使在JavaScript中更容易使用数组。

示例

以下是在JavaScript中定义数组的语法：-

const arrayExample  = [ 10 , 30 , 50 ,60 ];
console.log(arrayExample);

输出

[10, 30, 50, 60]

JavaScript中的数组排列是什么

数组的排列指的是对数组中的元素进行洗牌和排序。它使用数组作为输入源，生成所有可能的元素排列方式或排列。

如果我们在JavaScript中有一个包含n个元素的数组，则它生成n！种可能的排序和输出元素的方式。

元素的排列是解决问题陈述的核心，其中输入和输出可以如下可视化：

const arr = [ 1 , 2 , 3 ] ;

// generate all permutation 

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

寻找排列背后的逻辑

寻找数组元素的排列的逻辑与数学中的排列类似，在编程的角度来看，我们将用一个数组[1,2,3]来演示一些重复的步骤。

比如，我们将分离数组的第一个元素，并将其与已经按时间顺序排列的其他元素组合，结果返回[1,2,3]。然后将相同的分离的元素与时间顺序的交换顺序(2,3)组合在一起，得到一个新的排列集[1,3,2]。

这个逻辑会一直重复下去，直到数组长度耗尽，利用递归技术生成不同步骤的排列，每一步都需要一个核心分离元素。

步骤

步骤1 ：声明一个名为generatePermutation的函数，将一个元素数组作为输入。

步骤2 ：声明最终结果数组，其中包含数组输入中所有给定元素的不同组合的所有排列。现在先将其声明为空数组。

步骤3 ：我们在步骤1中声明的函数实际上是一个递归函数，有两个基本情况：如果数组的长度为0，即为空数组，那么它没有排列；如果数组的长度为1，即数组只有一个元素，那么单个元素的排列始终是一个元素，因此结果将是相同的数组，只有一个元素。

这两种基本情况是为了避免无限循环和代码的模糊性。

步骤4 ：现在，声明一个for循环，它将遍历数组的末尾，每次迭代根据i的第一个值保存当前元素。然后使用类似于javascript中的slice方法将当前元素存储在步骤4的第一部分中，分离出其他元素，并使用concat方法将刚刚发生的部分组合起来，从而得到一个数组中元素的排列组合。

步骤5 ：需要对步骤4中保存的特定当前元素进行递归地执行相同的步骤，通过交换其他元素来生成数组中的第二个组合。

步骤6 ：第二个嵌套循环的结果是交换元素的排列，以生成元素的不同组合，然后与当前元素连接，实现步骤5。

步骤7 ：这就是嵌套循环和递归对数组中的每个元素进行工作以生成组合和排序的不同排列的方式，这些元素由用户提供作为输入源。

示例

function generatePermutation (arr)
{
   let resultArr = [];
   if(arr.length === 0) return [];
   if(arr.length ===1) return [arr];

   for(let i =0 ; i<arr.length ; i++)
   {
     const currentElement = arr[i];

     const otherElements = arr.slice(0,i).concat(arr.slice(i+1));
     const swappedPermutation = generatePermutation(otherElements);

     for(let j =0 ; j < swappedPermutation.length ; j++)
     {
       const finalSwappedPermutation = 
       [currentElement].concat(swappedPermutation[j]);

       resultArr.push(finalSwappedPermutation);
     }
   }

   return resultArr;
}

const arr = [1,2,3];
const finalPermutedArray = generatePermutation(arr);
console.log(finalPermutedArray);

输出

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

以下提到的代码是面对问题陈述时人们可以想到的直接解决方案，随后您可以优化空间和时间以提高效率和质量。

在上面的代码中，我们声明了一个接受数组输入的函数。然后我们一步一步地进行，首先使用splice方法将每次迭代的第一个元素分离出来，并结合数组中的其他元素来形成一个新的分离数组，然后使用递归和splice、concat JavaScript方法生成分离数组的排列组合，并与我们在每次迭代中存储的当前元素结合，以产生给定输入的不同排列组合的最终结果。

时间复杂度

在上述算法中，我们最初使用了一个for循环，其在最坏情况下需要O(n)的时间，然后是使用splice方法将每个迭代的第一个元素分离出来，最好情况下需要O(1)的时间，再然后是使用concat方法将剩余元素连接在一起，最坏情况下需要O(n)的时间，最终的时间复杂度为O(n) + O(1) + O(n) = O(2n) = O(n)，其中常数并不重要，最后是嵌套循环来遍历剩余元素，最坏情况下的时间复杂度为O(n^2)。

所占用的空间复杂度仅为O(1)。