Loading [MathJax]/extensions/tex2jax.js
NOIP学习小站
西安交通大学附属中学航天学校

排列枚举

排列枚举,就是枚举所有元素的排列(要考虑元素的先后顺序)情况。例如三个数 {1,2,3} 的所有排列情况有:{1,2,3},{1,3,2},{2,1,3},{2,3,1},{3,1,2},{3,2,1}一共 6 种情况。 四个数{1,2,3,4} 的所有排列情况有:{1,2,3,4}、{1,2,4,3}、{1,3,2,4}、{1,3,4,2}、{1,4,2,3}、{1,4,3,2}、{2,1,3,4}、{2,1,4,3}、{2,3,1,4}、{2,3,4,1}、{2,4,1,3} 、{2,4,3,1}、{3,1,2,4}、{3,1,4,2}、{3,2,1,4}、{3,2,4,1}、{3,4,1,2}、{3,4,2,1}、{4,1,2,3}、{4,1,3,2}、{4,2,1,3}、{4,2,3,1}、{4,3,1,2}、{4,3,2,1} 一共 24 种情况。

下面的四重循环程序可以输出四个数{1,2,3,4} 的所有排列:

Plain text
Copy to clipboard
Open code in new window
EnlighterJS 3 Syntax Highlighter
#include<iostream>
using namespace std;
int main(){
int cnt = 0;
for(int i1=1;i1<=4;i1++){ //枚举第一个数
for(int i2=1;i2<=4;i2++){ //枚举第二个数
//第二个数不能和第一个数重复
if(i2==i1) continue;
for(int i3=1;i3<=4;i3++){ //枚举第三个数
//第三个数不能和前两个数重复
if(i3==i1 || i3==i2) continue;
for(int i4=1;i4<=4;i4++){ //枚举第四个数
//第四个数不能和前三个数重复
if(i4==i1 || i4==i2 || i4==i3) continue;
cout<<"{"<<i1<<","<<i2<<","<<i3<<","<<i4<<"} ";
cnt++;
}
}
}
}
cout<<endl<<cnt<<endl;
return 0;
}
#include<iostream> using namespace std; int main(){ int cnt = 0; for(int i1=1;i1<=4;i1++){ //枚举第一个数 for(int i2=1;i2<=4;i2++){ //枚举第二个数 //第二个数不能和第一个数重复 if(i2==i1) continue; for(int i3=1;i3<=4;i3++){ //枚举第三个数 //第三个数不能和前两个数重复 if(i3==i1 || i3==i2) continue; for(int i4=1;i4<=4;i4++){ //枚举第四个数 //第四个数不能和前三个数重复 if(i4==i1 || i4==i2 || i4==i3) continue; cout<<"{"<<i1<<","<<i2<<","<<i3<<","<<i4<<"} "; cnt++; } } } } cout<<endl<<cnt<<endl; return 0; }
#include<iostream>
using namespace std;
int main(){
	int cnt = 0;
    for(int i1=1;i1<=4;i1++){				//枚举第一个数 
    	for(int i2=1;i2<=4;i2++){			//枚举第二个数
			//第二个数不能和第一个数重复 
    		if(i2==i1) continue; 
    		for(int i3=1;i3<=4;i3++){		//枚举第三个数
				//第三个数不能和前两个数重复 
    			if(i3==i1 || i3==i2) continue; 
    			for(int i4=1;i4<=4;i4++){	//枚举第四个数
    				//第四个数不能和前三个数重复 
    				if(i4==i1 || i4==i2 || i4==i3) continue;
    				cout<<"{"<<i1<<","<<i2<<","<<i3<<","<<i4<<"} ";
    				cnt++;
    			}
    		}
		}
	}
	cout<<endl<<cnt<<endl;
    return 0;
}

如果要输出四个数{1,2,3,4} 选三个数的所有排列,只需要三重循环枚举选出来的两个数即可:

Plain text
Copy to clipboard
Open code in new window
EnlighterJS 3 Syntax Highlighter
//四选三排列
#include<iostream>
using namespace std;
int main(){
int cnt = 0;
for(int i1=1;i1<=4;i1++){ //枚举第一个数
for(int i2=1;i2<=4;i2++){ //枚举第二个数
//第二个数不能和第一个数重复
if(i2==i1) continue;
for(int i3=1;i3<=4;i3++){ //枚举第三个数
//第三个数不能和前两个数重复
if(i3==i1 || i3==i2) continue;
cout<<"{"<<i1<<","<<i2<<","<<i3<<"} ";
cnt++;
}
}
}
cout<<endl<<cnt<<endl;
return 0;
}
//四选三排列 #include<iostream> using namespace std; int main(){ int cnt = 0; for(int i1=1;i1<=4;i1++){ //枚举第一个数 for(int i2=1;i2<=4;i2++){ //枚举第二个数 //第二个数不能和第一个数重复 if(i2==i1) continue; for(int i3=1;i3<=4;i3++){ //枚举第三个数 //第三个数不能和前两个数重复 if(i3==i1 || i3==i2) continue; cout<<"{"<<i1<<","<<i2<<","<<i3<<"} "; cnt++; } } } cout<<endl<<cnt<<endl; return 0; }
//四选三排列
#include<iostream>
using namespace std;
int main(){
	int cnt = 0;
    for(int i1=1;i1<=4;i1++){				//枚举第一个数 
    	for(int i2=1;i2<=4;i2++){			//枚举第二个数
			//第二个数不能和第一个数重复 
    		if(i2==i1) continue; 
    		for(int i3=1;i3<=4;i3++){		//枚举第三个数
				//第三个数不能和前两个数重复 
    			if(i3==i1 || i3==i2) continue; 
    			cout<<"{"<<i1<<","<<i2<<","<<i3<<"} ";
    			cnt++; 
    		}
		}
	}
	cout<<endl<<cnt<<endl;
    return 0;
}

注意对比和前面四选三组合情况程序的区别:

Plain text
Copy to clipboard
Open code in new window
EnlighterJS 3 Syntax Highlighter
//四选三组合
#include<iostream>
using namespace std;
int main(){
for(int i1=1;i1<=2;i1++){
for(int i2=i1+1;i2<=3;i2++){
for(int i3=i2+1;i3<=4;i3++){
cout<<i1<<" "<<i2<<" "<<i3<<endl;
}
}
}
return 0;
}
//四选三组合 #include<iostream> using namespace std; int main(){ for(int i1=1;i1<=2;i1++){ for(int i2=i1+1;i2<=3;i2++){ for(int i3=i2+1;i3<=4;i3++){ cout<<i1<<" "<<i2<<" "<<i3<<endl; } } } return 0; }
//四选三组合
#include<iostream>
using namespace std;
int main(){
    for(int i1=1;i1<=2;i1++){
        for(int i2=i1+1;i2<=3;i2++){
            for(int i3=i2+1;i3<=4;i3++){
                cout<<i1<<" "<<i2<<" "<<i3<<endl;
            }
        }
    }
    return 0;
}

如果是更多的数的全排列,用上面的多重循环实现过于复杂。进一步,如果数的数量是一个变量,是无法用多重循环处理的。

其实 \(n\) 个元素的全排列一共有 \(n!\) 种的情况,所以枚举 \(n\) 个元素全排列的算法的时间复杂度是 \(O(n!)\)。这里介绍STL(标准模板库)中的一个函数 next_permutation 来实现全排列枚举,后面我们还可以使用搜索算法来实现更普遍的排列枚举。

next_permutation 函数的功能很强大,其使用方法和sort函数类似:next_permutation(a,a+n),实现的功能是调整数组a[0]~a[n-1]元素的位置以更换成下一个排列形式,注意这里是每调用一次更换成下一个排列。例如数组a初始元素是{1,2,3},调用一次next_permutation(a,a+3),数组a会变成{1,3,2};再调用一次next_permutation(a,a+3),数组a会变成{2,1,3}。并且next_permutation函数有返回值,当没有下一个排列的时候会返回 false。

来看例题:P1706 全排列问题

将1~n存入到数组中,通过反复调用 next_permutation 函数直到其返回值为 false 为止,每调用一次输出数组中的元素即可。考虑到数组初始状态也是一种排列形式,所以这里使用 do...while 循环:

Plain text
Copy to clipboard
Open code in new window
EnlighterJS 3 Syntax Highlighter
#include<bits/stdc++.h>
using namespace std;
int a[10];
int main()
{
int n;
scanf("%d",&n);
for(int i=0;i<n;i++) a[i] = i+1;
do{
for(int i=0;i<n;i++) printf("%5d",a[i]);
printf("\n");
}while(next_permutation(a,a+n));
return 0;
}
#include<bits/stdc++.h> using namespace std; int a[10]; int main() { int n; scanf("%d",&n); for(int i=0;i<n;i++) a[i] = i+1; do{ for(int i=0;i<n;i++) printf("%5d",a[i]); printf("\n"); }while(next_permutation(a,a+n)); return 0; }
#include<bits/stdc++.h>
using namespace std;
int a[10];
int main()
{
	int n;
	scanf("%d",&n);
	for(int i=0;i<n;i++) a[i] = i+1;
	do{
		for(int i=0;i<n;i++) printf("%5d",a[i]);
		printf("\n");
	}while(next_permutation(a,a+n));
    return 0;
}

来看下面的例子,会发现 next_permutation 函数在处理过程中如果发现数组中的元素是非下降排列的时候,就认定没有其他排列了,此时函数的返回值是false。所以如果要遍历所有的排列情况,可以在 do...while 循环前先对数组中的元素按升序排序处理:

Plain text
Copy to clipboard
Open code in new window
EnlighterJS 3 Syntax Highlighter
#include<iostream>
#include<algorithm>
using namespace std;
int a[5] = {5,4,3,2,1};
int main()
{
do{
for(int i=0;i<5;i++)
cout<<a[i]<<" ";
cout<<endl;
}while(next_permutation(a,a+5));
return 0;
}
#include<iostream> #include<algorithm> using namespace std; int a[5] = {5,4,3,2,1}; int main() { do{ for(int i=0;i<5;i++) cout<<a[i]<<" "; cout<<endl; }while(next_permutation(a,a+5)); return 0; }
#include<iostream>
#include<algorithm>
using namespace std;
int a[5] = {5,4,3,2,1}; 
int main()
{
    do{
    	for(int i=0;i<5;i++)
			cout<<a[i]<<" ";
    	cout<<endl;
	}while(next_permutation(a,a+5));
    return 0;
}
Plain text
Copy to clipboard
Open code in new window
EnlighterJS 3 Syntax Highlighter
#include<iostream>
#include<algorithm>
using namespace std;
int a[5] = {5,4,3,2,1};
int main()
{
sort(a,a+5);
do{
for(int i=0;i<5;i++)
cout<<a[i]<<" ";
cout<<endl;
}while(next_permutation(a,a+5));
return 0;
}
#include<iostream> #include<algorithm> using namespace std; int a[5] = {5,4,3,2,1}; int main() { sort(a,a+5); do{ for(int i=0;i<5;i++) cout<<a[i]<<" "; cout<<endl; }while(next_permutation(a,a+5)); return 0; }
#include<iostream>
#include<algorithm>
using namespace std;
int a[5] = {5,4,3,2,1}; 
int main()
{
	sort(a,a+5);
    do{
    	for(int i=0;i<5;i++)
			cout<<a[i]<<" ";
    	cout<<endl;
	}while(next_permutation(a,a+5));
    return 0;
}

当要进行全排列的数中有重复的数时, next_permutation 函数可以自动实现排列情况不重复。

Plain text
Copy to clipboard
Open code in new window
EnlighterJS 3 Syntax Highlighter
#include<bits/stdc++.h>
using namespace std;
const int N = 4;
int a[N] = {1,2,2,2};
int main()
{
do{
for(int i=0;i<N;i++)
printf("%5d",a[i]);
printf("\n");
}while(next_permutation(a,a+N));
return 0;
}
#include<bits/stdc++.h> using namespace std; const int N = 4; int a[N] = {1,2,2,2}; int main() { do{ for(int i=0;i<N;i++) printf("%5d",a[i]); printf("\n"); }while(next_permutation(a,a+N)); return 0; }
#include<bits/stdc++.h>
using namespace std;
const int N = 4;
int a[N] = {1,2,2,2};
int main()
{
	
    do{
        for(int i=0;i<N;i++)
			printf("%5d",a[i]);
        printf("\n");
    }while(next_permutation(a,a+N));
    return 0;
}

程序输出内容如下,可以发现 next_permutation 函数实现了排列情况不重复:

Plain text
Copy to clipboard
Open code in new window
EnlighterJS 3 Syntax Highlighter
1 2 2 2
2 1 2 2
2 2 1 2
2 2 2 1
1 2 2 2 2 1 2 2 2 2 1 2 2 2 2 1
    1    2    2    2
    2    1    2    2
    2    2    1    2
    2    2    2    1

其实前面解决的“P1618 三连击(升级版)”也可以使用排列枚举来处理,时间复杂度是\(O(9!)\),1s内可以处理完毕:

Plain text
Copy to clipboard
Open code in new window
EnlighterJS 3 Syntax Highlighter
#include<bits/stdc++.h>
using namespace std;
int a[10];
int main()
{
int A,B,C,x,y,z,cnt=0;
cin>>A>>B>>C;
for(int i=1;i<=9;i++) a[i] = i;
do{
x = a[1]*100+a[2]*10+a[3];
y = a[4]*100+a[5]*10+a[6];
z = a[7]*100+a[8]*10+a[9];
if(x*B==y*A && x*C==z*A){ //不用除法避免浮点数误差
cout<<x<<" "<<y<<" "<<z<<endl;
cnt++;
}
}while(next_permutation(a+1,a+10));
if(cnt==0) cout<<"No!!!"<<endl;
return 0;
}
#include<bits/stdc++.h> using namespace std; int a[10]; int main() { int A,B,C,x,y,z,cnt=0; cin>>A>>B>>C; for(int i=1;i<=9;i++) a[i] = i; do{ x = a[1]*100+a[2]*10+a[3]; y = a[4]*100+a[5]*10+a[6]; z = a[7]*100+a[8]*10+a[9]; if(x*B==y*A && x*C==z*A){ //不用除法避免浮点数误差 cout<<x<<" "<<y<<" "<<z<<endl; cnt++; } }while(next_permutation(a+1,a+10)); if(cnt==0) cout<<"No!!!"<<endl; return 0; }
#include<bits/stdc++.h>
using namespace std;
int a[10];
int main()
{
	int A,B,C,x,y,z,cnt=0;
	cin>>A>>B>>C;
	for(int i=1;i<=9;i++) a[i] = i;
	do{
		x = a[1]*100+a[2]*10+a[3];
		y = a[4]*100+a[5]*10+a[6];
		z = a[7]*100+a[8]*10+a[9];
		if(x*B==y*A && x*C==z*A){       //不用除法避免浮点数误差
			cout<<x<<" "<<y<<" "<<z<<endl;
			cnt++;
		}
	}while(next_permutation(a+1,a+10));
	if(cnt==0) cout<<"No!!!"<<endl;
    return 0;
}

再来看例题:P1088 火星人

仔细分析题意会发现问题求解的是\(n\)个元素第\(m\)个排列情况,使用next_permutation函数可以让程序变得很简洁高效:

Plain text
Copy to clipboard
Open code in new window
EnlighterJS 3 Syntax Highlighter
#include<bits/stdc++.h>
using namespace std;
int a[10001],n,m;
int main(){
cin>>n>>m;
for(int i=0;i<n;i++) cin>>a[i];
for(int i=0;i<m;i++) next_permutation(a,a+n);
for(int i=0;i<n;i++) cout<<a[i]<<" ";
return 0;
}
#include<bits/stdc++.h> using namespace std; int a[10001],n,m; int main(){ cin>>n>>m; for(int i=0;i<n;i++) cin>>a[i]; for(int i=0;i<m;i++) next_permutation(a,a+n); for(int i=0;i<n;i++) cout<<a[i]<<" "; return 0; }
#include<bits/stdc++.h>
using namespace std;
int a[10001],n,m;
int main(){
    cin>>n>>m;
    for(int i=0;i<n;i++) cin>>a[i];
    for(int i=0;i<m;i++) next_permutation(a,a+n);
    for(int i=0;i<n;i++) cout<<a[i]<<" ";
    return 0;
}

需要注意的是,枚举所有排列情况的算法时间复杂度是\(O(n!)\),一般情况下在1s内很难枚举超过11个元素的全排列!使用排列枚举要特别关注问题规模,避免超时!

登录

注册