求1到N的全排列

计算全排列有两种基本的方法， 递归和字典序。

1. 递归输出全排列

递归比较简单，下面直接贴代码：

void recurPermutation(int *arr, int n, int i)
{
    if(i==n-1) {
        printArray(arr, n);
    }
    for(int j=i; j<n; j++) {
        swap(arr, i, j);
        recurPermutation(arr, n, i+1);
        swap(arr, i, j);
    }
}

输入arr是一个长度是n的数组，数组元素各不相同。
 
2. 按字典序输出全排列
顾名思义是就是将1-n的一个排列看成一个数，然后按照字典的顺序从小到达的输出，
如1--5 的全排列，前面几个为:
1 2 3 4 5
1 2 3 5 4
1 2 4 3 5
1 2 4 5 3
1 2 5 3 4
....

如上面，我们如何由排列1 2 4 5 3得到1 2 5 3 4的呢？先从后往前扫描，找到排列的末尾的最大的递增子串，如最后的５　３；然后将这个子串反转，　得到了串1 2 4 3 5, 然后再刚才的末尾的子串中找出第大于4的最小的数， 即5， 然后将4和5交换。 这样就得到了 1 2 5 3 4了。

代码如下：

void permutation(int *arr, int n)
{
    int i, j, k;
    int count = 1;
    printArray(arr, n);
    while(true) {
        i=n-1;
        while(i>0 && arr[i-1] > arr[i]) i--;
        if (i==0) break;

        for(j=i, k=n-1; j<k; j++, k--) swap(arr, j, k);
        for(j=i; j<n; j++) {
            if(arr[j] > arr[i-1]) break;
        }

        swap(arr, i-1, j);
        count ++;
        printArray(arr, n);
    }
    printf("Total permutations: %d\n", count);
}

其中，输入参数是1...N的有序数组；如果无序的话，可以用快排进行排序。

由于排列的问题能够很好的考查对递归的掌握程度，并且实现也非常的简单，因此经常会出现在面试之中。

下面就是某著名互联网公司的一道关于排列的面试题：
题目：输入一个字符串S和一个整数N，其中S中的各个字符均不相等，并且N小于等于S的长度，请输出由S中字符组成的长度为N的所有的排列。
如：字符串是"abc", N=2, 则输出：ab, ac, bc, ba, ca, cb