【题解】状态压缩解决全排列

3

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

#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;
}

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

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;
}