前言

最近在数据结构的作业题中，出现了这样一道题目：

7-2 输出全排列 (20 分)

请编写程序输出前n个正整数的全排列（n<10），并通过9个测试用例（即n从1到9）观察n逐步增大时程序的运行时间。

输入格式:

输入给出正整数n（n<10）。

输出格式:

输出1到n的全排列。每种排列占一行，数字间无空格。排列的输出顺序为字典序。

输入样例:

3

输出样例:

123
132
213
231
312
321

在网上搜索了一下，网上的思路要么很复杂，要么不能得出正确结果，要么没有使用递归。

经过一番思考后，我发现了一种新方法。

先给出此种方法的优缺点，以供参考：

• 优点：代码极短，核心代码的长度仅有13行，容易阅读与理解。
• 缺点：存在费时费力的操作，整个算法的时间复杂度较高，执行过程麻烦。

思路

如何将问题转化为递归

输出全排列实际上可以看做一个递归问题。
假设有一个由0~n组成的数组arr，其元素为0， 1， 2， ... ， n。那么这个数组本身其实就是全排列的第一项。
如果要得到全排列的第二项，就需要把第n个元素和第n - 1个元素进行互换，并在互换后输出。
如果要得到第三项，就要先得到第n - 2、n - 1、n项的全排列。
……以此类推，得到n个数的全排列就可以归结为得到n - 1个数的全排列，最终归结为得到2个数的全排列。而得到2个数的全排列的方法就是：先将两个数输出，再将两个数交换后输出。

这很显然可以用递归来求解，因为问题规模是逐渐减小的，最终总能减小到一个特定的情况（递归边界），而且后一次的问题规模严格小于前一次，这也是递归类问题的典型思路。

如何减小问题规模

前面提到了，需要让问题的规模逐渐减小。这里我们以输出4的全排列为例，来谈谈如何逐步减小问题规模，以及如何用代码来描述这个过程。

按字典序输出4的全排列，应该为：

1234
1243
1324
1342
1423
1432
2134
2143
2314
2341
2413
2431
3124
3142
3214
3241
3412
3421
4123
4132
4213
4231
4312
4321

从中我们不难看出如下规律：

• 1~4轮流出现在排列的首位
• 排列的第二位从小到大，由1~4中除了首位的数轮流出现
• 排列的第三位和第四位相当于对两个数进行交换输出（递归边界）

所以我们可以用以下方法逐步减小这个问题的规模：

1. 循环扫描一个由1~n组成的数组（计数变量为i），每次把第i个数放入数组的最前面，并保证其他元素的位置相对不变（如：1234=>3124）
2. 对i + 1~n的部分进行递归，在递归中再次扫描这个数组，仍然进行上述变换（如3124=>3214）
3. 当i + 1 == n时只剩两个数，达到递归边界，输出这个数组
4. 交换最后两个数的位置，再输出一次，再交换回来
5. 递归结束，返回上一层递归，将变动过的数字放回去（3214=>3124，3124=>1234）
6. 扫描完从1~n的部分后，全排列输出完成，问题解决

伪代码如下：

void Perm(int ground, int sky) {
    if (ground + 1 == sky) {
        输出数组
        交换最后两数
        输出数组
        交换最后两数
    } else {
        for (int i = ground; i <= sky; i++) {
                对数组进行变换
                Perm(ground + 1, sky);
                将变换后的数组还原
        } // for
    } // if
} // Perm

因为这个数组要一直被使用、一直被变换，所以可以定义成全局变量。

完整代码

完整代码如下，如果gcc编译不通过可以把对循环变量的初始化放在for括号的外面：

#include <stdio.h>


int arr[15] = {0, 1, 2, 3, 4, 5, 6, 7, 8, 9};


void Perm(int, int);
void Swap(int*, int*);
void PrintArr(int);
void GetArr(int, int);
void BackArr(int, int);


int main() {
    int n;

    scanf("%d", &n);
    Perm(1, n);

    return 0;
} // main


/**
 * 本程序的核心函数：递归函数Perm()
 *
 * @param ground 要处理的数组元素下标的下界
 * @param sky    要处理的数组元素下标的上界
 */
void Perm(int ground, int sky) {
    if (ground + 1 == sky) {    // 递归边界，将最后两数先输出，再交换后输出，得到一组解
        PrintArr(sky);
        Swap(&arr[ground], &arr[sky]);
        PrintArr(sky);
        Swap(&arr[ground], &arr[sky]);
    } else {                    // 其他情况，遍历、变换数组，并继续递归求解
        for (int i = ground; i <= sky; i++) {
            GetArr(i, ground);
            Perm(ground + 1, sky);  // 递归
            BackArr(ground, i);
        }
    }
} // Perm


// 利用地址交换两个元素的值
void Swap(int* x, int* y) {
    int temp;
    temp = *x;
    *x = *y;
    *y = temp;
} // Swap


void PrintArr(int pos) {
    for (int i = 1; i <= pos; i++) {
        printf("%d", arr[i]);
    }
    putchar('\n');
} // PrintArr


// 对数组进行变换：把位置为nowPos的元素放到targetPos上
void GetArr(int nowPos, int targetPos) {    // nowPos > targetPos
    int elem = arr[nowPos];
    for (int i = nowPos; i >= targetPos; i--) {
        arr[i] = arr[i - 1];
    }
    arr[targetPos] = elem;
} // GetArr


// 将变换后的数组还原：把位置为nowPos的元素放回targetPos
void BackArr(int nowPos, int targetPos) {   // targetPos > nowPos
    int elem = arr[nowPos];
    for (int i = nowPos; i < targetPos; i++) {
        arr[i] = arr[i + 1];
    }
    arr[targetPos] = elem;
} // BackArr