排列 (Permutation / Arrangement)

概念

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

A = n! / (n - m)!

! 表示數(shù)學(xué)中的階乘運(yùn)算符，可以通過(guò)以下函數(shù)實(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 時(shí)，稱為 全排列，其值等于：

A = n!

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

分析

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

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

全排列：

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

    樹(shù)狀圖表示：
   
      1       2       3
     / \     / \     / \
    2   3   1   3   1   2
    |   |   |   |   |   |
    3   2   3   1   2   1   =>  6

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

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

實(shí)現(xiàn)

let arr = [1, 2, 3];

/*
參數(shù) a 為輸入數(shù)組，
元素個(gè)數(shù) n 為 a 的長(zhǎng)度，
選取個(gè)數(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 為保存單個(gè)情況結(jié)果的數(shù)組
 function recur(_a, tmpResult = []) {
 if (tmpResult.length === m) {
 
  // 結(jié)果達(dá)到 m 個(gè)時(shí)保存結(jié)果，
  // 停止遞歸并進(jìn)入下一次遍歷
  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ù)進(jìn)入下一層遞歸
  tmpA.splice(i, 1);
  recur(tmpA, _tmpResult);
  }
 }
 }
 
 // 開(kāi)始執(zhí)行遞歸，然后返回最后結(jié)果
 recur(a);
 return result;
}

console.log(permutation(arr));
// 3 個(gè)數(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 個(gè)數(shù)中選取 2 個(gè)數(shù)排列：
/*
[  
 [1, 2], 
 [1, 3], 
 [2, 1], 
 [2, 3], 
 [3, 1], 
 [3, 2]
]
*/

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

拓展

以上函數(shù)輸出值為一個(gè)二維數(shù)組，如果需要便于觀察，輸出一個(gè)一維數(shù)組，可以定義一個(gè)合并函數(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]

總結(jié)

以上就是這篇文章的全部?jī)?nèi)容了，希望本文的內(nèi)容對(duì)大家的學(xué)習(xí)或者工作具有一定的參考學(xué)習(xí)價(jià)值，謝謝大家對(duì)腳本之家的支持。

最新評(píng)論