基础算法--排列组合

墨蓝 2021-09-21 03:38 368阅读 0赞

### 一、排列 ###

定义：排列，一般地，从n个不同元素中取出m（m≤n）个元素，按照一定的顺序排成一列，叫做从n个元素中取出m个元素的一个排列(permutation)。特别地，当m=n时，这个排列被称作全排列(all permutation)。

根据定义可以看出排列是具有一定的顺序的

实现方式：

vector版：

//排列
    #include<iostream>
    #include<vector>
    using namespace std;
    void Permutation(vector<int> &a, vector<int> &b, int l){
    	//b用于临时存储结果。len(b)=len(a),l为左侧游标，初始值取0
    	int len = a.size();
    	if (l == len) { 
    		for (int i=0;i<b.size();i++){
    			cout << b[i]<< ' ';
    		}
    		cout << endl;
    		return; 
    	}
    	for (int i = l; i < len; i++){
    		b[l]= a[i];
    		swap(a[i], a[l]);
    		Permutation(a, b,l+1);
    		swap(a[i], a[l]);
    	}
    }
    int main()
    {
    	int num[9]={1,2,3,4,5,6,7,8,9};
    	int n;
    	cin>>n; //选出n个数 
    	vector<int> a(num,num+n),b(n);
    	Permutation(a,b,0);
    	return 0;
    }

数组版：

#include<iostream>
    using namespace std;
    void Permutation(int *a,int *b,int size,int l){
    	if(l == size)
    	{
    		for(int i=0;i<l;i++)
    		{
    			cout<<*(b+i)<<" ";
    		}
    		cout<<endl;
    		return;
    	}
    	for(int i=l;i<size;i++)
    	{
    		int temp;
    		*(b+l)=*(a+i);
    		temp = *(a+l); *(a+l) = *(a+i); *(a+i) = temp;
    		Permutation(a,b,size,l+1);
    		temp = *(a+l); *(a+l) = *(a+i); *(a+i) = temp;
    	} 
    }
    int main()
    {
    	int a[]={1,2,3,4,5,6,7,8,9};
    	int n;
    	cin>>n;
    	int b[n];
    	Permutation(a,b,n,0);
    	return 0;
     }

STL中的全排列模板：

在STL模板中给出了一种排列的方式：next\_permutation();   包含在头文件\#include<algorithm>中

这里需要在注意全排列和排列不同，能否使用视情况而定！！

#include<iostream>
    #include<cstdio> 
    #include<algorithm>
    using namespace std;
    int main()
    {
    	int num[]={1,2,3,4,5,6,7,8,9};
    	int n;
    	cin>>n;
    	do{
    		for(int i=0;i<n;i++)
    		{
    			printf("%d ",num[i]); 
    		}
    		printf("\n");
    	}while(next_permutation(num,num+n));
    	return 0;
    }

上述得全排列和排列算法可以解决任意元素的排列，但是排列出来的结果的次序是不同的

左侧是next\_permutation()的，右侧是上面的vector版本(数组版本和vector版本相同)

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQwMjc5Nzk1_size_16_color_FFFFFF_t_70][]

前一段时间我偶然发现了还有一种全排列的算法，但是这种做法只能做连续的整数的全排列

代码并非本人所写，在这里只是提供给大家看看，侵删！！

#include <bits/stdc++.h>
    using namespace std;
    int n,a[15];
    bool book[15]; 
    void dfs(int x)
    {
    	if(x==n+1)
    	{
    		for(int i=1;i<=n;i++)
    		{
    			printf("%d ",a[i]);
    		}
    		printf("\n");
    		return;
    	}
    	for(int i=1;i<=n;i++)
    	{
    		if(book[i]==false)
    		{
    			a[x]=i;
    			book[i]=true;
    			dfs(x+1);
    			book[i]=false;
    		}
    	}
    }
    int main()
    {
    	scanf("%d",&n);
        dfs(1);
    	return 0;
    }

从上面这个算法我们可以看到，它是通过标记元素的使用与否来选取元素。但是有一点美中不足的是他只有在做连续的小的数据的时候会比较方便，当待排列的数据出现1000000 2 3 4 5 77777 这样的数据的时候再使用这样的标识法做，开辟的空间就会比较大，强行用空间换时间就不那么划算了。

但是他这种标识法我们是可以借鉴的，我们来想想他标识的是什么?有的人一看就能明白，标识的数据本身，这么说也没有错，但我们换个角度想想，我们如果当作他标识的不是数据本身呢，而是标识的数据的位置呢，标识第一个数据有没有被用过，第k个数据有没有被用过.....，这个时候我们举一反三想想，如果我能够人为的给任意的待排列的数据加上标识，然后再使用这种方法，那么是不是即便是数据再大，我做的仍旧是1-N的全排。

实现如下：

#include<iostream>
    #include<map>
    #include<algorithm>
    #define MAX_N 20
    using namespace std;
    bool used[MAX_N]; //标志当前元素是否能够被使用 
    int perm[MAX_N]; //用来存放结果数据 
    map<int, int> p_num;
    //使用map的key-value来存放数据
    //按照key:1~n的顺序,这样使用n!思维就能够通过排列key来得到对应的value的全排 
    void permutation(int pos, int n){ //通常的 1-N 的全排列 
    // pos表示当前选取元素的游标 ， n表示全排的规模 
    	if(pos == n){//取到那个数后 
    		for(int i=0;i<n;i++){ //打印 
    			cout<<perm[i];
    		}
    		cout<<endl;
    		return;	
    	}
    	for(int i=1;i<=n;i++){ 
    		if(!used[i]){//当前元素没有被取到过的时候(flase) 
    			perm[pos] = i;//得到当前的数i（i的取值1-9） 
    			used[i] = true; //标识当前这个i已经取到过了 
    			permutation(pos + 1, n); //进入下一个位置的取值 
    			used[i] = false; //使用完成之后将其放回 
    		}
    	}
    	return;
    }
    void permutation_map(int pos, int n){ // 改进
    	if(pos==n){//取到所有数 
    		for(int i=0;i<n;i++){
    			cout<<perm[i];
    		}
    		cout<<endl;
    		return;	
    	} 
    	for(int i=1;i<=n;i++){
    		if(!used[i]){ //数能取
    			perm[pos] = p_num[i]; //将map中的key为 i的元素放入(因为key的取值是1-9，所以就相当于是做了N!的全排，但实际全排的元素是map中的value) 
    			used[i] = true;
    			permutation_map(pos + 1, n);
    			used[i] = false;
    		}
    	}
    	return; 
    } 
    
    int main(){
    	int num[] = {2,4,1,5,7,8,3,7,4};
    	for(int i=0;i<9;i++){
    		p_num[i+1]=num[i];
    	}
    	permutation_map(0, 9);
    	return 0;
    }

### 二、组合 ###

定义：组合（combination）一般地，从n个不同的元素中，任取m（m≤n）个元素为一组，叫作从n个不同元素中取出m个元素的一个组合。

根据定义可以看出组合是不考虑元素之间顺序的

实现方式：

vector版：

//排列组合 
    #include<iostream>
    #include<vector>
    using namespace std;
    void Combination(vector<int> &a, vector<int> &b, int l, int m, int M){
    	//b用于临时存储结果。len(b)==M；l为左侧游标，初始值取0；M是取出个数；m用于指示递归深度，初始值取M）
    	if (m == 0) { //b已取满
    		for (int i = 0; i < b.size(); i++)//输出 
    			cout << b[i]<< ' ';
    		cout << endl;
    		return;
    	}
    	for (int i = l; i < a.size(); i++){//每一轮可以取的数 
    		b[M-m] = a[i]; //当前层数决定能放的位置 
    		Combination(a, b,i+1,m - 1,M);
    	}
    }
    int main()
    {
    	int num[10]={0,1,2,3,4,5,6,7,8,9};
    	int n;
    	cin>>n;
    	vector<int> a(num,num+10),b(n);
    	Combination(a,b,0,n,n);
    	return 0;
    }

数组版：

#include<iostream>
    using namespace std;
    void Combination(int a[],int *b,int a_size,int b_size,int t,int n,int num){
    	// t是当前选取数据的下标，n是递归层数，还需取数的个数，会随着递归减少，num是需要取的个数(定值) 
    	if(n==0)
    	{
    		for(int i=0;i<b_size;i++)
    		{
    			cout<<*(b+i)<<" ";
    		}
    		cout<<endl;
    		return;
    	}
    	for(int i=t;i<a_size;i++)//组合
    	{
    		*(b+(num-n))=a[i];
    		Combination(a,b,a_size,b_size,i+1,n-1,num);
    	} 
    }
    int main()
    {
    	int a[]={0,1,2,3,4,5,6,7,8,9};
    	int n;
    	cin>>n;
    	int b[n];
    	Combination(a,b,10,n,0,n,n);
    	return 0;
     }

感谢阅读！！

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQwMjc5Nzk1_size_16_color_FFFFFF_t_70]: /images/20210920/003457c97d6d4d6e9e76b726232feefb.png