【递归】全排列

Description

 输入一个数字n，输出从1~n组成的数字的全排列，每个排列占一行，输出按照数值升序排列

比如输入2，则输出是：

12

21

又如输入3，则输出是：

123

132

213

231

312

321

Input

 第一行是一个整数m，代表有m个测试用例

接下来的m行，每行是一个整数n，0 < n < 10

Output

 对于每个用例，输出它的全排列，每个排列占一行，输出按照数值升序排列

Sample Input

 Copy sample input to clipboard

2
2
3

Sample Output

12
21
123
132
213
231
312
321

Problem Source: 第四周 5班

 

解题思路：

QAQ之前因为最后几个不能顺序输出，老是乱位置，看了好几个博客都没大懂，直到我看到一个用字符串处理的。。。简直好用!!!!又好懂!!!!!233333

参考博客http://blog.csdn.net/jokers_i/article/details/8217063

实现代码：

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

void fun(const string& sf, const string& sr) {//sf表示前部分，sr表示后部分 
    if (sr.size() == 1) {
        cout << sf << sr << endl;
    } else {
        for (int i = 0; i < sr.size(); i++)
            fun(sf+sr[i], string(sr).erase(i, 1));
    }
}

int main() {
    int m, n, i;
    string sr;
    cin >> m;
    while (m--) {   //m个测例 
        cin >> n;
        for (i = 0; i < n; i++)
            sr += i  + '1';    //转换成一个字符串的全排列 
        fun("", sr);
        sr="";
    }
}