JavaScript怎樣實現(xiàn)元素全排列

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

排列 (Permutation / Arrangement)

概念

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

A = n! / (n - m)!

! 表示數(shù)學(xué)中的階乘運算符，可以通過以下函數(shù)實現(xiàn)：

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

當(dāng) n = m 時，稱為 全排列，其值等于：

A = n!

全排列相當(dāng)于將所有元素進行排序，得到所有不同順序情況的個數(shù)；

分析

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

用數(shù)組舉例分析：

全排列：

    [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

實現(xiàn)

let arr = [1, 2, 3];

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

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

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

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

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

拓展

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

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怎樣實現(xiàn)元素全排列”這篇文章的所有內(nèi)容，感謝各位的閱讀！希望分享的內(nèi)容對大家有幫助，更多相關(guān)知識，歡迎關(guān)注億速云行業(yè)資訊頻道！