L8_02 排列与组合

一、排列

1.1 排列的定义

从 n 个不同元素中取出 k 个元素，按照一定顺序排成一列，称为从 n 个元素中取 k 个元素的一个排列。

1.2 排列数公式

// P(n, k) = n × (n-1) × ... × (n-k+1) = n! / (n-k)!
long long permutation(int n, int k) {
    if (k > n) return 0;
    long long result = 1;
    for (int i = 0; i < k; i++) {
        result *= (n - i);
    }
    return result;
}

// 全排列 P(n, n) = n!
long long factorial(int n) {
    long long result = 1;
    for (int i = 2; i <= n; i++) {
        result *= i;
    }
    return result;
}

1.3 生成全排列

void generatePermutations(vector<int>& nums, int start, vector<vector<int>>& result) {
    if (start == nums.size()) {
        result.push_back(nums);
        return;
    }
    
    for (int i = start; i < nums.size(); i++) {
        swap(nums[start], nums[i]);
        generatePermutations(nums, start + 1, result);
        swap(nums[start], nums[i]);
    }
}

vector<vector<int>> permute(vector<int>& nums) {
    vector<vector<int>> result;
    generatePermutations(nums, 0, result);
    return result;
}

1.4 生成第k个排列

string getPermutation(int n, int k) {
    vector<int> factorial(n + 1, 1);
    vector<int> nums;
    
    for (int i = 1; i <= n; i++) {
        factorial[i] = factorial[i - 1] * i;
        nums.push_back(i);
    }
    
    k--; // 转换为0-indexed
    string result;
    
    for (int i = n; i >= 1; i--) {
        int index = k / factorial[i - 1];
        k %= factorial[i - 1];
        result += to_string(nums[index]);
        nums.erase(nums.begin() + index);
    }
    
    return result;
}

二、组合

2.1 组合的定义

从 n 个不同元素中取出 k 个元素，不考虑顺序，称为从 n 个元素中取 k 个元素的一个组合。

2.2 组合数公式

// C(n, k) = n! / (k! × (n-k)!)
long long combination(int n, int k) {
    if (k > n) return 0;
    if (k == 0 || k == n) return 1;
    
    k = min(k, n - k); // 优化，减少计算量
    long long result = 1;
    
    for (int i = 0; i < k; i++) {
        result *= (n - i);
        result /= (i + 1);
    }
    
    return result;
}

2.3 组合数性质

// C(n, k) = C(n, n-k)
// C(n, k) = C(n-1, k) + C(n-1, k-1)
// C(n, 0) + C(n, 1) + ... + C(n, n) = 2^n

long long combinationRecursive(int n, int k) {
    if (k == 0 || k == n) return 1;
    return combinationRecursive(n - 1, k) + combinationRecursive(n - 1, k - 1);
}

2.4 生成组合

void generateCombinations(int n, int k, int start, vector<int>& current, vector<vector<int>>& result) {
    if (current.size() == k) {
        result.push_back(current);
        return;
    }
    
    for (int i = start; i <= n; i++) {
        current.push_back(i);
        generateCombinations(n, k, i + 1, current, result);
        current.pop_back();
    }
}

vector<vector<int>> combine(int n, int k) {
    vector<vector<int>> result;
    vector<int> current;
    generateCombinations(n, k, 1, current, result);
    return result;
}

三、二项式定理

3.1 二项式定理公式

// (a + b)^n = Σ(C(n, k) × a^(n-k) × b^k) for k = 0 to n

// 计算二项式展开系数
vector<long long> binomialCoefficients(int n) {
    vector<long long> coeff(n + 1, 1);
    
    for (int i = 1; i <= n; i++) {
        coeff[i] = coeff[i - 1] * (n - i + 1) / i;
    }
    
    return coeff;
}

3.2 二项式定理应用

// 计算 (a + b)^n
long long binomialPower(long long a, long long b, int n) {
    long long result = 0;
    long long a_power = 1;
    
    for (int k = 0; k <= n; k++) {
        long long c = combination(n, k);
        long long b_power = 1;
        
        for (int i = 0; i < k; i++) {
            b_power *= b;
        }
        
        result += c * a_power * b_power;
        a_power *= a;
    }
    
    return result;
}

四、排列组合的应用

4.1 子集生成

// 生成所有子集
vector<vector<int>> subsets(vector<int>& nums) {
    int n = nums.size();
    vector<vector<int>> result;
    
    for (int mask = 0; mask < (1 << n); mask++) {
        vector<int> subset;
        for (int i = 0; i < n; i++) {
            if (mask & (1 << i)) {
                subset.push_back(nums[i]);
            }
        }
        result.push_back(subset);
    }
    
    return result;
}

// 生成大小为k的子集
vector<vector<int>> subsetsOfSizeK(vector<int>& nums, int k) {
    vector<vector<int>> result;
    vector<int> current;
    generateSubsets(nums, 0, k, current, result);
    return result;
}

void generateSubsets(vector<int>& nums, int start, int k, vector<int>& current, vector<vector<int>>& result) {
    if (current.size() == k) {
        result.push_back(current);
        return;
    }
    
    for (int i = start; i < nums.size(); i++) {
        current.push_back(nums[i]);
        generateSubsets(nums, i + 1, k, current, result);
        current.pop_back();
    }
}

4.2 电话号码组合

vector<string> letterCombinations(string digits) {
    if (digits.empty()) return {};
    
    unordered_map<char, string> phone = {
        {'2', "abc"}, {'3', "def"}, {'4', "ghi"},
        {'5', "jkl"}, {'6', "mno"}, {'7', "pqrs"},
        {'8', "tuv"}, {'9', "wxyz"}
    };
    
    vector<string> result = {""};
    
    for (char d : digits) {
        vector<string> temp;
        for (string s : result) {
            for (char c : phone[d]) {
                temp.push_back(s + c);
            }
        }
        result = temp;
    }
    
    return result;
}

4.3 括号生成

void generateParenthesisHelper(int n, int open, int close, string current, vector<string>& result) {
    if (current.size() == 2 * n) {
        result.push_back(current);
        return;
    }
    
    if (open < n) {
        generateParenthesisHelper(n, open + 1, close, current + "(", result);
    }
    if (close < open) {
        generateParenthesisHelper(n, open, close + 1, current + ")", result);
    }
}

vector<string> generateParenthesis(int n) {
    vector<string> result;
    generateParenthesisHelper(n, 0, 0, "", result);
    return result;
}

五、排列组合对比

特性	排列	组合
顺序	考虑顺序	不考虑顺序
公式	P(n,k) = n!/(n-k)!	C(n,k) = n!/(k!(n-k)!)
数量	P(n,k) ≥ C(n,k)	C(n,k) ≤ P(n,k)
应用	排队、排序	选组、抽样