排列组合

📐 数学公式

■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■
阶乘函数（符号：!）
■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■
表示将一系列递减的自然数相乘。 例子：

4! = 4 × 3 × 2 × 1 = 24
7! = 7 × 6 × 5 × 4 × 3 × 2 × 1 = 5,040
1! = 1


■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■
排列的计数
■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■
▶ 设 A 是有 n 个元素的集合，则有 2^n 个子集
▶ 如果 1 ≤ r ≤ n, 那么 n 个对象中每次取 r 个的排列数是 n • (n-1) • (n-2) •...• (n-r+1)
▶ 设 A 是 {a,b,c}， A 的可能排列为 3! = 3 × 2 × 1 = 6 种
▶ 简化公式(排列公式)为：

nPr = n! ÷ (n-r)!


▶ 在一个有n个对象的集合中，第 1 个对象出现 k[1] 次，第 2 个对象出现 k[2] 次，则该集合所形成的不同排列数为

n! ÷ ( k[1]! • k[2]! •...• k[t]! )  (其中 k[1] + k[2] + ... + k[t] = n)


■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■
组合的计数
■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■
▶ 设 A = {1,2,3,4}, 每次取三个时，A 的不同组合可以是： 
A[1] = {2,3,4} = {2,3,1} = {1,3,2} = {3,1,2} = {3,2,1}
A[2] = {1,2,4} = {2,4,1} = {1,4,2} = {4,1,2} = {4,2,1}
A[3] = ...

▶ 设 A 是一个集合且  |A| = n, 0 ≤ r ≤ n, 那么每次取 r 个时 A 的元素的组合数为：

nCr = n! ÷ [ r! • (n-r)! ]

每次取 r 个时，A 的组合数不依赖于 A。


▶ 例子：从一副 52 张纸牌中分发 5 张，则有 51! ÷ (5!47!) = 2598960 种组合方法


■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■
鸽巢原理(存在性证明)
■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■
如果你学过离散数学，就会学到这个原理的证明。如果 n 只鸽子被分配到 m 个鸽巢里，且 m < n， 那么至少有 1 个鸽巢含有 2 只或者更多只鸽子。



■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■
概率基础
■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■
样本空间 ( 硬币正反面作为样本排列： A = {HH, HT, TH, TT} )
对事件赋予概率
“等可能” 的结果

■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■
递归关系
■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■
比如斐波那契数列

📌 JavaScript

参考代码：index.js

/**
 * 元素的排列方式
 * @param {Array} items  - 需要组合的元素，使用数组表示
 * @returns {Array} 所有组合的数组集合
 */
export function permutations(items) {

    const results = [];

    /* 递归组合 */
    function permute(arr, memo = []) {
        let currentArr;

        for (let i = 0; i < arr.length; i++) {

            /* 每次以被删除的元素作为数组初始值 */
            currentArr = arr.splice(i, 1);
            if (arr.length === 0) {
                results.push(memo.concat(currentArr));
            }

            /* 克隆一个被删除元素后的新数组, 直接将 arr 结果传入 permute() 函数也是可以的 */
            const arrRes = arr.slice();
            permute(arrRes, memo.concat(currentArr));

            /* 注意：splice后的数组，会覆盖原来的数组，造成for或者forEach循环的次数减少, 因此我们要将删除的元素重新push进去 */
            arr.splice(i, 0, currentArr[0]);
        }

        return results;
    }

    permute(items);

    return results;
}



/**
 * 元素的组合方式(取出元素没有考虑重复性)
 * @param {Array} arr - 输入数组
 * @param {Number} quantity - 要取出的元素数量(用来组合)
 * @param {Number} index - arr 中的当前索引
 * @param {Array} tempArr - 临时数组
 * @param {Number} tempArrIndex - tempArr 中的当前索引
 * @param {Array} result -  存储每次分组后的结果
 * @returns {Array} 所有组合的数组集合
 */
function combinationUtil(arr, quantity, index, tempArr, tempArrIndex, result) {

    const { length } = arr;

    /* 打印每组的结果 */
    if (index == quantity) {
        const res = [];
        for (let j = 0; j < quantity; j++) {
            res.push(tempArr[j]);
        }
        result.push(res);
        return;
    }

    /* 当没有更多元素可以放入 tempArr 时 */
    if (tempArrIndex >= length) {
        return;
    }


    /* 包含当前元素，原数组向下移位 */
    tempArr[index] = arr[tempArrIndex];
    combinationUtil(arr, quantity, index + 1, tempArr, tempArrIndex + 1, result);

    /* 排除当前元素，临时数组向下移位 */
    combinationUtil(arr, quantity, index, tempArr, tempArrIndex + 1, result);

    return result;
}

export function combinations(arr, quantity) {
    const tempArr = new Array(quantity);

    return combinationUtil(arr, quantity, 0, tempArr, 0, []);
}

测试：test.js

import { permutations, combinations } from './index';


/* 排列 [1, 2, 3] 这3个元素，它们有多少种排列方法(它们是排列是有序的) */
console.log(permutations([1, 2, 3]));
/* 输出
[
    [1,2,3],
    [1,3,2],
    [2,1,3],
    [2,3,1],
    [3,1,2],
    [3,2,1]
]
*/



/* [1, 2, 3, 4]四个元素取出2个，它们的组合为 */
console.log(combinations([1, 2, 3, 4], 2));
/* 输出：
[
[1, 2], 
[1, 3], 
[1, 4], 
[2, 3], 
[2, 4], 
[3, 4]
]
*/