首页 算法学习

C++计算排列与组合

排列

如果计算排列数，直接利用公式即可。下面的代码是输出每一种排列的情况

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
/******************************************************
@params:
nums:要排列的数据
left:排列的左区间
right:排列的右区间
ans:记录所有排列的情况的数目
*******************************************************/
void permutate(vector<int>& nums, int left, int right, int& ans)
{
	//区间左端点和右端点相同，输出结果
    if(left == right){
        ans++;
        for(int num: nums){
            cout << num << " ";
        }
        cout << endl;
        return;
    }
    for(int i = left; i < right; i++){
        swap(nums[i], nums[left]);				//确定第一个数字
        permutate(nums, left + 1, right, ans);  //排列后面的数字
        swap(nums[i], nums[left]);				//回溯
    }
    return;
}

组合

如果是需要输出每种组合的情况，可以还用回溯的思想

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
/********************************
@params:
nums:用来组合的数据
pos:当前选择到了nums的哪个位置
cnt：当前已经选择的数字的总数目
K:挑选的总数目
ans:记录组合的所有情况的数目
visited:记录nums中每个数字是否被选择
*********************************/
void combine(vector<int>& nums, int pos, int cnt, int K, int& ans, vector<bool>& visited)
{
	//如果已经标记的数字的总数目和K相等就输出
    if(cnt == K){
        ans++;
        for(int i = 0; i < nums.size(); i++){
            if(visited[i]){
                cout << nums[i] << " ";
            }
        }
        cout << endl;
        return;
    }
    //如果当前选择的位置到了数组末尾，直接返回
    if(pos == nums.size()){
        return;
    }
    //选择位于pos的数字
    visited[pos] = true;
    combine(nums, pos + 1, cnt + 1, K, ans, visited);
    //不选择位于pos的数字
    visited[pos] = false;
    combine(nums, pos + 1, cnt, K, ans, visited);
}

如果是只计算组合数，比较实用的是利用递推公式进行计算

这个公式的含义是从$m$个数中取出$n$个数，可以分为两种情况：

  • 包括第$m$个数，此时只需要从前$m-1$个数中取出$n-1$个数，一共有$C_{m-1}^{n-1}$种情况；
  • 不包括第$m$个数，此时只需要从前$m-1$个数中取出$n$个数，一共有$C_{m-1}^{n}$种情况。
1
2
3
4
5
6
7
8
9
10
11
12
//计算从m里面取n个数的组合数
    int combine(int m, int n)
    {
        vector<vector<int>> dp(m + 1, vector<int>(n + 1, 0));
        for(int i = 0; i <= m; i++){
            dp[i][0] = 1;
            for(int j = 1; j <= min(i, n); j++){
                dp[i][j] = dp[i - 1][j] + dp[i - 1][j - 1];
            }
        }
        return dp[m][n];
    }