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

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

一、定义

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

二、常见问题

​ 一般的问题：

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

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

三、组合

1、求解方式

栗子1求组合：

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

现要求你输出所有组合。

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

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

题解：

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

图1 所有组合

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

重难点：

怎么做到节点不重复？

答：每次从当前节点的下一个节点出发 怎么做到是组合而不是排列？

组合和排列都有先后顺序，区别是组合的先后顺序是固定的（由小到大或者由大到小），而排列不固定

代码如下：

#include

#include //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

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

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

#include //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

#include //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

#include //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;

}

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