JavaScript怎樣實現元素全排列

這篇文章主要介紹JavaScript怎樣實現元素全排列，文中介紹的非常詳細，具有一定的參考價值，感興趣的小伙伴們一定要看完！

排列 (Permutation / Arrangement)

概念

n 個不同元素中任意選取 m (m <= n) 個元素進行排列，所有排列情況的個數叫做 排列數，其值等于：

A = n! / (n - m)!

! 表示數學中的階乘運算符，可以通過以下函數實現：

function factorial(n) {
 if (n === 0 || n === 1) {
 return 1;
 
 } else if (n < 0) {
 return null;
 
 } else {
 return n * factorial(n - 1);
 }
}

console.log(factorial(4)); // 24

當 n = m 時，稱為 全排列，其值等于：

A = n!

全排列相當于將所有元素進行排序，得到所有不同順序情況的個數；

分析

利用階乘函數，通過上述數學公式只能得到所有情況的個數值，不容易得到具體的每種情況，要獲取每種情況的輸出值的話需要另尋他法；

用數組舉例分析：

全排列：

    [1, 2, 3] => [             
                    [1, 2, 3],
                    [1, 3, 2],
                    [2, 1, 3],
                    [2, 3, 1],
                    [3, 1, 2],
                    [3, 2, 1]
                 ]
               
                共 6 種情況

    樹狀圖表示：
   
      1       2       3
     / \     / \     / \
    2   3   1   3   1   2
    |   |   |   |   |   |
    3   2   3   1   2   1   =>  6

3 個元素中選取 2 個時：(n = 3, m = 2)

    [1, 2, 3] => [             
                    [1, 2],
                    [1, 3],
                    [2, 1],
                    [2, 3],
                    [3, 1],
                    [3, 2]
                 ]
               
                共 6 種情況
   
    樹狀圖表示：
   
      1       2       3
     / \     / \     / \
    2   3   1   3   1   2   =>  6

實現

let arr = [1, 2, 3];

/*
參數 a 為輸入數組，
元素個數 n 為 a 的長度，
選取個數為 m；
*/
function permutation(a, m) {

 // 保存最終輸出結果
 let result = [];
 
 // 定義 m 值默認等于 n，即全排列
 let n = a.length;
 m = m || n;
 
 // 定義遞歸函數保存結果到數組中
 // _a 為輸入數組，
 // tmpResult 為保存單個情況結果的數組
 function recur(_a, tmpResult = []) {
 if (tmpResult.length === m) {
 
  // 結果達到 m 個時保存結果，
  // 停止遞歸并進入下一次遍歷
  result.push(tmpResult);
  
 } else {
  for (let i = 0; i < _a.length; i++) {
  
  // 復制一份輸入數組，防止引用值被改變
  let tmpA = _a.concat();
  
  // 復制一份保存結果的數組，防止每次遍歷相互影響
  let _tmpResult = tmpResult.concat();
  
  // 保存當前遍歷值
  _tmpResult.push(tmpA[i]);
  
  // 刪除當前遍歷值，傳遞參數進入下一層遞歸
  tmpA.splice(i, 1);
  recur(tmpA, _tmpResult);
  }
 }
 }
 
 // 開始執行遞歸，然后返回最后結果
 recur(a);
 return result;
}

console.log(permutation(arr));
// 3 個數全排列：
/*
[  
 [1, 2, 3], 
 [1, 3, 2], 
 [2, 1, 3], 
 [2, 3, 1], 
 [3, 1, 2], 
 [3, 2, 1]
]
*/

console.log(permutation(arr, 2));
// 3 個數中選取 2 個數排列：
/*
[  
 [1, 2], 
 [1, 3], 
 [2, 1], 
 [2, 3], 
 [3, 1], 
 [3, 2]
]
*/

最終實現函數就是 permutation(a, m)，其中參數 a 為輸入數組，包含需要排列的所有元素，參數 m 為選取需要排列的個數，默認等于輸入數組的長度，即默認全排列，注意 m 不能大于元素個數；

拓展

以上函數輸出值為一個二維數組，如果需要便于觀察，輸出一個一維數組，可以定義一個合并函數：

function merge(arr) {
 return arr.map(x => x.join(''));
}

let result = merge(permutation([1, 2, 3]));
console.log(result);
// [123, 132, 213, 231, 312, 321]

以上是“JavaScript怎樣實現元素全排列”這篇文章的所有內容，感謝各位的閱讀！希望分享的內容對大家有幫助，更多相關知識，歡迎關注億速云行業資訊頻道！