用循环方法实现C语言的排列组合
排列组合是我们高中时期就学过的知识,还记得当初被甲乙丙丁们站在一排的数学问题所折磨,苦不堪言呐。在实际编程过程中,我们也常遇到排列组合的问题。
那么,什么是排列组合呢?百度百科给的解释通俗易懂。排列组合是组合学最基本的概念,前后两者并不相同。所谓排列,就是指从给定个数的元素中取出指定个数的元素进行排序。组合则是指从给定个数的元素中仅仅取出指定个数的元素,不考虑排序。例如3个男生和5个女生站成一排,3个男生必须相互紧邻,有多少种站法的问题,像下面这样。
在数学题中,我们通常只需要求出所有排列或者组合的总数即可,一两个公式就能算出来。但是,在实际应用中,有时须将排列组合的每一种情况都列出来,方便下一步的操作。稍微简单的问题,如在ABCD四个字母中选出两个来,不费吹灰之力便能列出。但是问题更复杂些呢,8个字母中选5个?16个字母中选7个?手动列出来就难多了吧。
如题目所示,这里我要介绍的是利用循环法实现排列组合,方法简洁、很易懂。言归正传,下面就开整。
示例:在0~7这8个整数中选出5个不重复的数,列出所有情况。先列出代码。
#include<opencv2/opencv.hpp>
#include<iostream>
#include<fstream>
#include<math.h>
#include<string>
#include<algorithm>
#include<time.h>
using namespace cv;
using namespace std;
bool Equal_Judgement(vector<vector<int>> result, vector<int> temp);
int main(int argc, char** argv){
clock_t begin_t, end_t; //定义开始和结束时间变量
double duration; //记录整个循环需要的时间
vector<vector<int>> Permutation; //定义向量容器,存储排列组合的所有情况
vector<int> Array; //定义向量容器,存储每一种情况里的元素
begin_t = clock(); //获取当前时间
int record = 0;
for(int i = 0; i < 8; i++){ //一共8个整数
for(int j = 0; j < 8; j++){
if(j == i) continue; //第二个数不能与第一个数重复
for(int k = 0; k < 8; k++){
if(k == i || k == j) continue; //第三个数不能和前两个数重复
for(int l = 0; l < 8; l++){
if(l == i || l == j || l == k) continue; //第四个数不能和前三个数重复
for(int m = 0; m < 8; m++){
if(m == i || m == j || m == k || m == l) continue; //以此类推
Array.clear(); //容器清空
Array.push_back(i); //往容器中添加元素
Array.push_back(j);
Array.push_back(k);
Array.push_back(l);
Array.push_back(m);
sort(Array.begin(),Array.end()); //容器中元素从小到大排序
if(Permutation.size() < 1) Permutation.push_back(Array);
else{
bool Judg_Value1;//判断当前Array是否与前面的重复
Judg_Value1 = Equal_Judgement(Permutation, Array);
if(Judg_Value1 == true) {
Permutation.push_back(Array);
record++;
printf("第%d个组合是%d %d %d %d %d\n",record,i,j,k,l,m);}
}
}
}
}
}
}
end_t = clock();
duration = (double)(end_t - begin_t) / CLOCKS_PER_SEC; //计算经过时间
printf( "%f seconds\n", duration );
printf("总共有%d种情况\n", Permutation.size());
waitKey(0);
return 0;
}
bool Equal_Judgement(vector<vector<int>> result, vector<int> temp){
int length;
length = result.size();
sort(temp.begin(), temp.end());
for(int i = 0; i < length; i++){ //判断是否有重复的整型数组
if(temp == result[i]){
return false;
break;
}
}
return true;
}
基本思路:我们定义了两个向量容器,分别命名为Array和Permutation。Array用于存放整数,表示一种组合情况;Permutation用于存放前一个容器Array,表示所有的组合情况。利用5层循环将选择的5个数列出来,再通过函数Equal_Judgement()来判断这种情况是否与之前的组合情况重复,如果没有,则保存起来;重复则舍弃掉。结果如下(组合数从0计)。
这样,我们就实现了从8个数中选5个不重复数的所有组合情况。
在别人的博客中我学习到一种非常巧妙的方法,递归。利用排列组合具有的递归性质进行求解,感兴趣的可以去看这篇博客:https://blog.****.net/u012814856/article/details/73863086。出于好胜心,我将自己的方法与前面的递归法比较了一下,让我惊喜的是,循环法貌似计算速度还更快些。大家感兴趣的可以自己去试试。
欢迎点赞评论留言,分享你独特的见解。