如何按照大小顺序输出一个数字序列的全排列

常见的全排列问题，是可以用递归去解决的，但是递归是很难保证输出的结果的大小顺序的，当然我们可以保存所有的结果，然后对于结果进行排序，这样无疑增加了时间上的复杂度，那么我们如何解决这个问题呢？
其实，这个问题我们可以用另外一个经典的套路来解决：
给定一个数X，他的兄弟数Y定义为：是由X中的数字组合而成，并且Y是大于X的数中最小的。例如，38276的兄弟数字为38627。给定X，求Y。

分析
当开始想到这个题目的时候就想到和求排列很像，想借用排列的方法，但是发现用这个方法不知道在哪里停止，无法降低O(n^2)的复杂度。
那 有没有更好的方法呢？不想对所有情况进行穷举，就要想办法，尽可能缩小要处理的范围，一般的思路，从右边开始，两两交换，查看是否可以找到Y，最开始考虑 两位，进而考虑三位，依次类推，那么如何确定，要考虑多少位呢？假设X的形式如下：x1x2x3...xky1y2y3y4，并且其中 y1>y2>y3>y4，xk

下面以一个具体例子来说明上述过程：

3

4

7

2

2

6

4

1

首先找到，从右边开始的递增的、尽可能长的数位，这里是641。

3

4

7

2

2

(6

4

1)

则，选取前一位数字2，进行交换。641中，大于2的最小的值是4，则作如下交换：

3

4

7

2

4

(6

2

1)

为了得到最小值，对621，从小到大进行排序，得到

3

4

7

2

4

(1

2

6)

则，Y为34724126.

所以，然后我们利用上面讲到的方法，来找到一个最小序列的所有的兄弟数字，就可以求得这个序列的全排列。

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

bool getBrother(string &dest)
{
    if(dest.size() <= 1)
        return false;
    int before = dest.size() - 2;
    int after = dest.size() - 1;
    if(dest[after] > dest[before])
    {
        swap(dest[after], dest[before]);
        return true;
    }
    char min = '9';
    int pos;
    while((--before) >= 0)
    {
        pos = 0;//每次循环记得要把pos复位
        for(int i = after; i > before; i--)
        {
            if(dest[i] > dest[before] && dest[i] < min)
            {
                min = dest[i];
                pos = i;
            }
        }
        if(pos > before)
        {
            swap(dest[pos], dest[before]);
            sort(&dest[before + 1], &dest[after + 1]);//从开始元素到待排序元素的下一个位置
            return true;
        }
    }
    return false;
}

void allRank(string &dest)
{
    if(dest.size() <= 1)
        return;
    sort(&dest[0], &dest[dest.size()]);
    do{
        cout << dest << endl;
    }while(getBrother(dest));
}

int main()
{
    string s("12543");
    allRank(s);
    return 0;
}