next_permutation

产生一个数列的全排列，自己想了一个实现算法，和stl里面的实现算法一样，具体的思路都在注释中。
代码中还实现了一种递归的做法，参考了网上的资料，递归的做法代码简短很多，但可操作性而言，没有next方式好。因为实际应用中需要针对每个permutation作相应的操作。用递归的话需要把操作写在permutation的实现中，耦合性很高。
另外，递归的方式受限于系统栈空间的大小，N只能在一定范围内处理。理论上，next的方式N可以无限大。

代码如下:

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

#define N 5

int li[N];

bool next_permu(int start, int end){
    if (end < start) return false;
    // find the longest increase sub str from the end
    int ptr1;
    for (ptr1 = end - 1; ptr1 >= start; --ptr1){
        if (li[ptr1] < li[ptr1 + 1])break;
    }
    if (ptr1 < start) return false;

    // find the first one which is larger than li[ptr] from the end
    // it is guaranteed that this ptr2 will be found
    int ptr2;
    for (ptr2 = end; ptr2 > ptr1; --ptr2){
        if (li[ptr2] > li[ptr1])break;
    }

    // swap the numbers pointed by ptr1 and ptr2
    int temp = li[ptr1];
    li[ptr1] = li[ptr2];
    li[ptr2] = temp;

    // reverse the string from ptr1 + 1 to end
    for (int i = ptr1 + 1, j = end; i < j; ++i, --j){
        temp = li[i];
        li[i] = li[j];
        li[j] = temp;
    }
    return true;
}

// the recursive solution
void permu(int num){
    if (num == 1){
        for (int i = 0; i < N; ++i){
            cout << li[i] << " ";
        }
        cout << endl;
        return;
    }
    for (int i = N - num; i < N; ++i){
        swap(li[N - num], li[i]);
        permu(num - 1);
        swap(li[N - num], li[i]);
    }
}

int main(int argc, const char * argv[]) {
    for (int i = 1; i <= N; ++i){
        li[i - 1] = i;
    }
    do{
        for (int i = 0; i < N; ++i){
            cout << li[i] << " ";
        }
        cout << endl;
    }
    while (next_permu(0, N - 1));

    permu(N);
    return 0;
}