信息学奥赛一本通C++语言——1199：全排列

【题目描述】
给定一个由不同的小写字母组成的字符串，输出这个字符串的所有全排列。

我们假设对于小写字母有‘a’ <‘b’ < … <‘y’<‘z’，而且给定的字符串中的字母已经按照从小到大的顺序排列。

【输入】
只有一行，是一个由不同的小写字母组成的字符串，已知字符串的长度在1到6之间。

【输出】
输出这个字符串的所有排列方式，每行一个排列。要求字母序比较小的排列在前面。字母序如下定义：

已知S=s1s2…sk,T=t1t2…tk，则S<T等价于，存在p(1≤p≤k)，使得s1=t1,s2=t2,…,sp−1=tp−1,sp<tp成立。

【输入样例】
abc
【输出样例】
abc
acb
bac
bca
cab
cba
【提示】
本题目禁止使用STL及包含可以使用的相关调用。
【源代码】

递归法

#include<iostream>
#include<cstdio>
#include<cstring>
using namespace std;
string a,b;
int len;
void perm(int x);//定义全排列函数
int main() {
	cin>>a;
	len=a.length();
	perm(0);
	return 0;
}
void perm(int x) {//x是当前数组b的长度，由于b是从0开始命名的，所以x也可以做本次操作的b的当前位的指针
	if(x==len) {//递归边界，本次结束了，输出结果
		for(int i=0; i<len; ++i)
			cout<<b[i];
		cout<<endl;
	} else { //没有结束，将b[x]的位置确定下来
		bool bj=0;//判断a[i]是否在b中出现过将要使用的标记
		char t;
		for(int i=0; i<len; ++i) {//枚举第x位是a[i]
			t=a[i];//提取a[i]并暂存
			bj=0;
			for(int j = 0; j < x; ++j) {//扫一遍b数组，判断a[i]是否在已排列的数组中出现
				if(b[j]==t) {//已排列的数组中有a[i]
					bj=1;//打标记
					break;//跳出(已经找到了，再找下去也不会找到a[i]了，因为字符串不重复)
				}
			}
			if(bj)//b[j]就是之前出现过的a[i]，所以再找下一个a[i]放入b
				continue;
			else {
				b[x] = a[i];//这是a[i]没有出现的情况，就把a[i]放到b[j+1]中。
				perm(x+1);//在确定前x位的基础上，全排列x+1位以及后面的元素
			}
		}
	}
}