本文主要是介绍组合型和排列型枚举，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
组合型枚举
排列组合是大家都接触过的概念，而组合型枚举则是在 n 个元素中随机选出 m 个元素的问题。对于每一种可能的选择方案，我们需要确定选择了哪 m 个元素，这就是组合型枚举。
组合型枚举有一套固定的流程和算法模板，需要大家进行记忆。
chosen = []
n = 0
m = 0def calc(x):if len(chosen) > m:returnif len(chosen) + n - x + 1 < m:returnif x == n + 1:for i in chosen:print(i,end=' ')print('')returnchosen.append(x)calc(x + 1)chosen.pop()calc(x + 1)if __name__ == '__main__':tem = input().split()n = int(tem[0])m = int(tem[1])calc(1)题目：公平抽签
题目描述:
小 A 的学校，蓝桥杯的参赛名额非常有限，只有 m 个名额，但是共有n 个人报名，其中 m≤n。作为老师非常苦恼，他不知道该让谁去，他在寻求一个绝对公平的方式。于是他准备让大家抽签决定，即 m 个签是去，剩下的是不去。小 A 非常想弄明白最后的抽签结果是什么样子的，到底有多少种结果。
请设计一个程序帮助小 A。最后输出各种情况的人名即可，一行一种情况，每种情况的名字按照报名即输入顺序排序。
第一行 输入 N,M。
第二行 到第 N+1 行 共输入 N 个人名每种情况输出 M 个人名，空格隔开。
样例：
输入：3 2
xiaowang
xiaoA
xiaoli输出：xiaowang xiaoA
xiaowang xiaoli
xiaoA xiaoli题目解析：
实际上还是组合型枚举，但是输出元素为人名，我们可以将人名存起来，输出的时候，根据数字下标找到提前存好的人名，直接输出即可。
#include <iostream>
#include <vector>
using namespace std;int n; //共计N个数
int m; //选m个数
vector<string> name;
vector<string> ans;
vector<int> chosen;
void calc(int x)
{if (chosen.size() > m || chosen.size() + (n - x + 1) < m) //剪枝return;if (x == n + 1){ //选够了m个数输出string ansTem = "";for (int i = 0; i < chosen.size(); i++)ansTem += name[chosen[i] - 1] + " ";ans.push_back(ansTem);return;}chosen.push_back(x);calc(x + 1);chosen.pop_back(); //消除痕迹calc(x + 1);}
int main()
{cin >> n >> m;for (int i = 0; i < n; i++){string s;cin >> s;name.push_back(s);}calc(1);for (int i =0; i < ans.size(); i++)cout << ans[i] << endl;
}排列型枚举
上面说过，组合型枚举就是让你在 n 个中，随机选出 m 个 ，问你有多少种方案，而且每一种方案选择了哪 m 个，这就是组合型枚举。
而排列型枚举相对组合型枚举就简单了一点，就是n 个的全排列，即从 n 个中选取 n 个但是关心内部的顺序。
相比较组合只关心有多少个集合，而排列是关心集合内的排列方式。即排列型枚举就是寻找Ann问题。
而且排列型枚举也是有着比较成熟的模板需要大家进行记忆。
int n; //共计N个数
int order[20];
bool chosen[20];
void calc(int k)
{if (k == n + 1){for (int i = 1; i <= n; i++)cout << order[i] << " ";puts("");return;}for (int i = 1; i <= n; i++){if (chosen[i])continue;order[k] = i;chosen[i] = 1;calc(k + 1);chosen[i] = 0;order[k] = 0;}
}
int main()
{cin >> n;calc(1);
}座次问题
题目描述:
小 A 的学校，老师好不容易解决了蓝桥杯的报名问题，现在老师又犯愁了。现在有 N 位同学参加比赛，但是老师想给他们排座位，但是排列方式太多了。老师非常想弄明白最后的排座次的结果是什么样子的，到底有多少种结果。
请设计一个程序帮助老师。最后输出各种情况的人名即可，一行一种情况，每种情况的名字按照报名即输入顺序排序。第一行 输入 N； 第二行 到 第 N+1 行 共输入 N 个人名。由于小 A 学校承办能力实在有限，所以其中 N 小于等于 10 人。
输入：3
xiaowang
xiaoA
xiaoli输出：xiaowang xiaoA xiaoli
xiaowang xiaoli xiaoA
xiaoA xiaowang xiaoli
xiaoA xiaoli xiaowang
xiaoli xiaowang xiaoA
xiaoli xiaoA xiaowang代码：
#include <iostream>
#include <vector>
using namespace std;int n; //共计N个数
vector<string> name;
int order[20];
bool chosen[20];
void calc(int k)
{if (k == n + 1){for (int i = 1; i <= n; i++)cout << name[order[i] - 1] << " ";puts("");return;}for (int i = 1; i <= n; i++){if (chosen[i])continue;order[k] = i;chosen[i] = 1;calc(k + 1);chosen[i] = 0;order[k] = 0;}
}int main()
{cin >> n;for (int i = 0; i < n; i++){string s;cin >> s;name.push_back(s);}calc(1);
}
这篇关于组合型和排列型枚举的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
