每日编程-20170321

James

　　题目:亮亮深吸一口气，小心地将盒子打开，里面是一张地图，地图上除了一些奇怪的字母以外没有任何路线信息，这可让亮亮犯了愁，这些字母代表了什么意思呢？ 亮亮绞尽脑汁也想不出什么思路，突然，亮亮眼前一亮，“我可以把这些字母所有的排列方式全部写出来，一定可以找到答案！” 于是，亮亮兴奋的开始寻找字母里的秘密。
　　输入描述:
每组数据输入只有一行，是一个由不同的大写字母组成的字符串，已知字符串的长度在1到9之间，我们假设对于大写字母有'A' < 'B' < ... < 'Y' < 'Z'。
　　输出描述:
输出这个字符串的所有排列方式，每行一个排列，要求字母序比较小的排列在前面。
　　输入例子:
WHL
　　输出例子:
HLW
　　HWL
　　LHW
　　LWH
　　WHL
　　WLH
　　解答：
　　递归好难搞
　　整体思路就是，先把输入排序
　　然后使用递归思想：
　　将得到的数组的第一个与后面的依次互换
　　将互换后的数组的第一个删掉，剩下的内容递归
　　一直到剩下最后一个
　　输出数组



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

void Exchange(char &a, char &b) { char c = a;    a = b;    b = c; }
void Arrange(char* s, int ss) {
     for (size_t i = 0; i < ss - 1; i++)
         for (size_t j = i + 1; j < ss; j++)
             if (s>s[j])    Exchange(s, s[j]);
}
void quanPai(char *s, int ss, int pos) {　　//依次输入数组，长度，开始位置
     if (pos == ss - 1){    cout << s << endl;    return;    }　　//如果开始位置已经是最后一个，输出，返回
     for (size_t i = pos; i < ss; i++)　　//将第一个依次与后面的互换
     {
         Exchange(s[pos], s);
         quanPai(s, ss, pos+1);
         Exchange(s[pos], s);　　//每次换位都要基于原本的顺序，所以下一层返回后需要换回来
     }
}

int main() {
     char input[10];
     cin >> input;
     Arrange(input,strlen(input));
     quanPai(input, strlen(input), 0);
}