组合、全排列的联系与解析

一、定义

• 组合：从 n 个不同元素中取出 k 个元素的所有不同组合的个数，叫做从 n 个不同元素中取出 k 个元素的组合数，
• 排列：是将相异对象或符号根据确定的顺序重排。每个顺序都称作一个排列。例如，从一到六的数字有720种排列，对应于由这些数字组成的所有不重复亦不阙漏的序列，例如"4, 5, 6, 1, 2, 3" 与1, 3, 5, 2, 4, 6。

二、常见问题

​ 一般的问题：

1. 求组合或者排序，全列出来
2. 求组合或者排序的数目

注释：后面我们将这两个问题看成树，其中第一个问题在叶子节点输出、第二个问题在根节点返回。理解好这两个概念问题，对后续的搜索、背包、树、图、都将是很好的铺垫。因为后面的算法都会问到这两个问题。

三、组合

1、求解方式

栗子1求组合：

排列与组合是常用的数学方法，其中组合就是从 n个元素中抽出 r个元素（不分顺序且 r <= n），我们可以简单地将 n个元素理解为自然数1,2,…,n，从中任取 r个数。

现要求你输出所有组合。

例如 n=5,r=3所有组合为：

123,124,125,134,135,145,234,235,245,,124,125,134,135,145,234,235,245,345。

题解：

​ 对于组合的求解方式，是把他看成一棵树来看待。至于为什么看成树，原因就是形象、好理解。例如从1-5中，取3个数，进行组合，得到的树如图1 所有组合所示

讯享网

由上图可知，我们选节点的方式是，先把1、2、3、4、5，这5个节点铺开，按顺序选一个节点，节点数为三的时候，直接打印节点。

重难点：

• 怎么做到节点不重复？
  • 答：每次从当前节点的下一个节点出发
• 怎么做到是组合而不是排列？
  • 组合和排列都有先后顺序，区别是组合的先后顺序是固定的（由小到大或者由大到小），而排列不固定

代码如下：

#include<iostream> #include <iomanip>//setw()头文件 using namespace std; const int maxl = 100; int n, r, ans[maxl]; void f(int star, int end, int ans[], int d){//开始的位置、结束的位置、存放的节点、存放的节点数 if (d == r){ for (int i = 1; i <= r; i++){ cout << setw(3) << ans[i]; } cout << endl; return ; } for (int i = star; i <= end; i++){ ans[d + 1] = i; f(i + 1, end, ans, d + 1); } } int main(){ cin >> n >> r;//在n个数中选择r个数进行组合 f(1, n, ans, 0); } 

栗子二（求组合数）：

题目：上题不变，由求组合变成求组合数

题解：

• 其实机智的同学就会发现，在原有的地方加一个全局变量来计数可以吗？答案是可以的。可以把他当作方案一。
• 方案二、就是把方案数返回到根节点，这也是主流操作

方案一，代码如下：

讯享网#include<iostream> using namespace std; int n, r, count; void f(int star, int end, int d){ if (d == r){ count++;//换成计数 return ; } for (int i = star; i <= end; i++){ f(i + 1, end, d + 1); } } int main(){ cin >> n >> r;//在n个数中选择r个数进行组合 f(1, n, 0); cout << count << endl; } 

方案二，代码如下：

#include<iostream> using namespace std; const int maxl = 100; int n, r; int f(int star, int end, int d){ int sum = 0; if (d == r){ return 1; } for (int i = star; i <= end; i++){ sum += f(i + 1, end, d + 1);//从根到当前节点的节点数 } return sum; } int main(){ cin >> n >> r;//在n个数中选择r个数进行组合 cout << f(1, n, 0) << endl; } 

四、排列

由于排列与组合的最大区别上面已经提及，这就不多赘述，直接上代码了。

排列，代码如下：

讯享网#include<iostream> #include <iomanip>//setw()头文件 using namespace std; const int maxl = 100; int n, r, ans[maxl]; bool p[maxl];//判断当前位置有没有来过 void f( int ans[], int d, bool p[maxl]){//开始的位置、结束的位置、存放的节点、存放的节点数 if (d == r){ for (int i = 1; i <= r; i++){ cout << setw(3) << ans[i]; } cout << endl; return ; } for (int i = 1; i <= n; i++){ if (!p[i]){ ans[d + 1] = i; p[i] = !p[i]; f(ans, d + 1, p); p[i] = !p[i];//回溯 ，这里不能影响其兄弟节点 } } } int main(){ cin >> n >> r;//在n个数中选择r个数进行组合 f(ans, 0, p); } 

排列数（方案一），代码如下：

#include<iostream> #include <iomanip>//setw()头文件 using namespace std; const int maxl = 100; int n, r,count = 0; bool p[maxl];//判断当前位置有没有来过 void f( int d, bool p[maxl]){//开始的位置、结束的位置、存放的节点、存放的节点数 if (d == r){ count++; return ; } for (int i = 1; i <= n; i++){ if (!p[i]){ p[i] = !p[i]; f(d + 1, p); p[i] = !p[i];//回溯 ，这里不能影响其兄弟节点 } } } int main(){ cin >> n >> r;//在n个数中选择r个数进行组合 f(0, p); cout << count << endl; } 

排列数（方案二），代码如下：

讯享网#include<iostream> #include <iomanip>//setw()头文件 using namespace std; const int maxl = 100; int n, r; bool p[maxl];//判断当前位置有没有来过 int f(int d, bool p[maxl]){//开始的位置、结束的位置、存放的节点、存放的节点数 int sum = 0; if (d == r){ return 1; } for (int i = 1; i <= n; i++){ if (!p[i]){ p[i] = !p[i]; sum += f(d + 1, p); p[i] = !p[i];//回溯 ，这里不能影响其兄弟节点 } } return sum; } int main(){ cin >> n >> r;//在n个数中选择r个数进行组合 cout << f(0, p) << endl; } 

都看到这了，不妨给个三连呗！！！！