题解 | #全排列#

#include<iostream>
#include<string>
#include<vector>
using namespace std;

//相当于一根不完全的n叉树 
void PaiLie(string str,vector<int> remain,int* seq,int length,int remove=-1,int layer=0){
	if(layer!=0){
		*(seq+layer-1) = remain.at(remove);//确认掉本层的字母 
		remain.erase(remain.begin()+remove);
	}
	if(layer==length){//生成了一个完整的序列 
		for(int i=0;i<length;i++)
			cout<<str[seq[i]];
		cout<<endl; 
	} else {//序列不完整，继续生成 
		int n = remain.size();
		for(int i=0;i<n;i++){
			PaiLie(str,remain,seq,length,i,layer+1);
		}
	} 
	
} 

int main(){//习题8.2  北京大学  输出字符串的全排列 
	//生成一个数字序列的全排列，再按照该排列打印字符串即可
	//示例给出的打印顺序是123 132 213 231 312 321
	string str;
	while(cin>>str){
		vector<int> id;
		int n = str.size();
		int* seq = (int*)malloc(sizeof(int)*n);
		for(int i=0;i<n;i++){
			id.push_back(i);
		}
		PaiLie(str,id,seq,n);
	}
}