JavaScript陣列全排列生成

---

在本題中，要求我們使用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中剛剛儲存的特定當前元素遞迴地執行步驟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 ]  ]

下面提到的程式碼是檢視問題陳述時人們可以想到的直接程式碼，稍後您可以當然將其最佳化到更好的空間和時間質量，使其更有效和高質量。

在上面的程式碼中，我們聲明瞭一個接收陣列輸入的函式。然後我們一步一步地進行，首先是剪接每次迭代的第一個元素，並將陣列中存在的其他元素組合起來以形成一個新的分離陣列，然後使用遞迴和剪接和連線JavaScript方法來生成分離陣列的排列，以與我們儲存的每個迭代的當前元素組合，以產生給定陣列的不同排列的最終結果。

時間複雜度

在上面的演算法中，我們最初使用for迴圈遍歷陣列的長度，最壞情況下導致O(n)，然後使用slice方法在最佳情況下花費O(1)來分離每次迭代的每個第一個元素，以及連線方法連線剩餘的元素直到長度，導致O(n)，新增到O(n) + O(1) + O(n) = O(2n) = O(n)，其中常數無關緊要，然後是巢狀迴圈來遍歷剩餘的元素，最壞情況下導致O(n)，導致O(n^2)最壞時間複雜度。

所佔空間複雜度僅為O(1)。

結論

這就是我們如何透過邏輯思考和編碼上下文來解決上述問題陳述，在巢狀迴圈和JavaScript方法（如splice和concat）以及遞迴的支援下，來解決生成陣列中存在的元素的不同排列的問題。