题目描述

按照字典序输出自然数 1到 n 所有不重复的排列,即 n 的全排列,要求所产生的任一数字序列中不允许出现重复的数字。

输入格式

输出格式

一个整数 n。

输入输出样例

1n1 \sim n组成的所有不重复的数字序列,每行一个序列。

每个数字保留 5个场宽。

输入 #1

3

输出 #1

    1    2    3
    1    3    2
    2    1    3
    2    3    1
    3    1    2
    3    2    1

说明/提示

1≤n≤9。

分析过程

首先是朴素方法,因为n的范围不大,我们可以构造一个状态数组,用于标记1n1\sim n 的数字的选中状态。我们只要先选定第一个数,再选下一个,一直选到第n个数;尝试完一种方案的话再换一个数继续进行尝试,直到找出所有的排列组合来。

标记数组+回溯

#include <iostream>
#include <cstdio>
using namespace std;
bool vis[10];//标记状态 数字是否的组合中
int rk[10];//存放组合好的数字
int n;//个数
void dfs(int d){//d-已挑选好的数字
	if(d==n){//当已选好了n个数
		for(int i=0;i<n;i++){//输出这个组合的n个数
			printf("%5d",rk[i]);//注意场宽为5
		}
		printf("\n");
		return ;
	}
	for(int i=1;i<=n;i++){//从1~n中寻找不在组合中的数
		if(!vis[i]){//不在组合中
			vis[i]=true;//标记
			rk[d]=i;//将数字存入组合
			dfs(d+1);//更改参数,递归调用,寻找下一个数
			vis[i]=false;//回溯状态
		}
	}
}
int main(){
	scanf("%d",&n);
	dfs(0);//调用,从最开始一个数都没有开始
	return 0;
}

对于数字来说首先它的个数不多,n最大到9,其次它的状态只有两种,选或者是没选。这时候,我们可以采用状态压缩的方式来解决这道问题。每个数选没选,我们用一个二进制的数来表达,1表示选了,0表示没选。以n为4为例,00001111的所有的四位二进制数,即可表达n个数的状态,再将这些数描述为十进制的数字就是 02n10 \sim 2^n-1 的数字。

需要用到的几个二进制操作

lowbit

int lowbit(int x){
	return x&(-x);
}

将第j位改为1/0

state=state|(1<<j);//将第j位改为1
state=state&(~(1<<j));//将第j位改为0

代码实现

#include <iostream>
#include <cstdio>
using namespace std;
int rk[10];
int Log[1030];
int n;
int all;
int lowbit(int x){//得到x对应二进制的最低位的1及其后边所有的0构成的数值。
	return x&(-x);
}
void dfs(int state,int d){
	//state 0 ~ 2^9 表示状态 d-代表已经选了几个数
	if(state==all){//全部选好
		for(int i=0;i<d;i++){//输出选好的n个数
			printf("%5d",rk[i]);
		}
		printf("\n");
		return ;
	}
	
	//从没选的数中 挑选一个数
	//为了方便处理 将没选过的二进制位翻转为1
	int vis=all&~state;//与all 进行按位与 是为了仅将n位二进制进行处理,以免影响操作
	while(vis){
		int x=lowbit(vis);
		rk[d]=Log[x]+1;//将选中的数字存入 数组中
		dfs(state|x,d+1);
		vis-=x;
	}
	
}
int main(){
	scanf("%d",&n);
	all=(1<<n)-1;//全选的状态 二进制下是n位1
	Log[1]=0;//预处理  Log[x] == log2(x)
	for(int i=2;i<=all;i++){
		Log[i]=Log[i/2]+1;
	}
	dfs(0,0);
	return 0;
}

Q.E.D.


( ノ^ω^)ノ゚ 稻 花 香 里 说 丰 年 , 听 取 WA 声 一 片 。(╥╯^╰╥)