排列 (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]

總結

以上就是這篇文章的全部內容了，希望本文的內容對大家的學習或者工作具有一定的參考學習價值，謝謝大家對VeVb武林網的支持。