如果现在有六个数字1 2 3 4 5 6，请列举出其所有的排列可能。

从n个不同元素中任取m（m≤n）个元素，按照一定的顺序排列起来，叫做从n个不同元素中取出m个元素的一个排列。当m=n时所有的排列情况叫全排列。显然，这是一个全排列问题。

全排列问题是递归的代表题型。

递归思想

如果我想对从1到6的六个数字做全排列，我可以：

首先，我固定第一个数字是1，然后对后面的数字做全排列。
然后，我固定第一个数字是2，然后对后面的数字做全排列。
以此类推，第一个数字再固定3、4......一直到6。

当我固定第一个数字是1的时候，还剩下2、3、4、5、6，我只需要对剩下的这5个数字做全排列，就可以解决“当第一个数字是1的时候，所有的全排列可能性”的问题了，显然，第一个数字依次从1到6遍历一遍，可以求解这六个数的全排列所有可能性。

那么再思考，第一个数字被固定了，后面的数字是不是又是一个新的全排列问题呢？
第一个数字如果固定了1，后面还剩下2、3、4、5、6，把后面的2、3、4、5、6单独拿出来看，我再次固定后面那部分的第一个数字（也就是固定整体的第二个数字）是2，对3、4、5、6进行全排列，我再固定这四个数字这一部分的第一个数字（也就是整体的第三部分）是3，对4、5、6进行全排列......

递归的思想显而易见，如果想求解全排列问题，步骤很简单：

固定好第一个数字
对后面的数字进行全排列
重新固定第一个数字，并重复第二个步骤，直到所有的数字都在第一个位置上走过一遍了。

代码实现

递归思想有了以后，实现起来并不难，关键点有：

把一个数放在第一个位置，就是将其与第一个位置上的数交换

假如现在我有六个数1、2、3、4、5、6，现在做全排列，第一步是当1开头时，很显然，1本来就是第一个数字，看第二步，当2是开头时......诶？怎么写呢？

我们可以理解成，把2与第一个位置上的数字换一换，变成2,1,3,4,5,6，现在我们就不用看第一个位置了，从第二个位置开始看进行新的全排列即可。

关键点在于，每次换完并且求解出所有“子全排列问题”以后，一定要换回来！

代码实现

#include<cstdio>

//交换两个位置上的数字
void swap(int num[666], int i, int j) {
    int t = num[j];
    num[j] = num[i];
    num[i] = t;
}

//输出一个数组
void disp(int num[666], int length) {
    for (int i = 0; i < length; ++i) {
        printf("%d ", num[i]);
    }
    printf("\n");
}

//全排列的实现
void qpl(int num[666], int length, int startLoc) {
    for (int i = startLoc; i < length; ++i) {
        swap(num, startLoc, i);

        //如果发现当前要解决的子问题只有一个数字，
        //就不用再往下开子问题了
        if (startLoc < length - 1)
            qpl(num, length, startLoc + 1);
        else //如果要是只有一个数字，输出当前的数组，当前数组就是当前的全排列可能性
            disp(num, length);

        swap(num, startLoc, i);
    }
}

int main() {
    int num[666] = {1, 2, 3, 4, 5, 6};
    qpl(num, 6, 0);
    return 0;
}