C/C++递归实现全排列

前言

本文介绍如何用递归实现全排列。

全排列

参考题目：递归实现排列型枚举

两种方法，一是枚举每个位置，看每个位置能放哪些数。以A33为例，同是第一个位置，可以放1、2、3，三种元素。

二是枚举每个数，看每个数能放在哪些位置。即同是元素1，可以放在第一、第二、第三的位置上。

两种方法的思维和代码极其相似，本文展示第一种方法。

首先，我们创建一个数组arr，用来保存每个位置的数。

int arr[10] = { 0 };//保存已被固定的数

对于第一个位置arr【0】来说，有三种选择，分别是1、2、3，在每种选择的前提下，进行第二个位置的选择。

因为我们在固定第一个位置时已经用掉了一个数，所以在固定第二个位置arr【1】时，就不能再次使用这个数。

于是，我们创建一个数组used，利用哈希表的思想，保存每个数是否被用过。

int used[10] = { 0 };// 判断一个数是否被用过，用过则为1，没用过则为0

比如说，当我们arr【0】被固定为数字1，那么就让used【1】++，当我们进行第二、三个位置的固定时，先检测used【要固定的数】是否为0，是0才可以使用。

为了没有遗漏，我们要保证每一个位置都要对三个数进行遍历，一旦某个数可以用，就马上固定它，且每个位置的遍历顺序必须一致。

以上也是博主理解的为什么递归算法又叫深度优先搜索的原因。

深度，在本题中是代表遍历的顺序必须一致，要么从前往后，要么从后往前，只有这样才可以从一开始就一条路走到最深，才可以没有遗漏情况。

优先，在本题中是代表在每个位置对数据进行遍历的时候，只要这个数能用，就马上使用，以保证没有遗漏。

详细代码及注释如下：

//枚举每个位置放不同的数
int arr[10] = { 0 };//保存已被固定的数
int used[10] = { 0 };// 判断一个数是否被用过，用过则为1，没用过则为0
void f(int n,int h)
{
    if (n == h)//如果三个数都被固定好了，则打印,可以先略过打印部分
    {
        int i = 0;
        for (i = 0; i < h; i++)
        {
            printf("%d ", arr[i]);
        }
        printf("\n");
        return;
    }


    int i = 0;
    for (i = 0; i < h; i++)
    {
        if (used[i + 1] == 0)//此语句代表i+1这个数还没被用过
        {
            used[i + 1]++;//没被用过就马上使用它
            arr[n] = i + 1;
            f(n + 1,h);
            used[i + 1]--;//在一种情况下的分支结束后，到另一种情况时，需要恢复原样
        }
    }
}
int main()
{
    int h = 0;
    scanf("%d", &h);
    f(0,h);
    return 0;
}

感谢您的阅读与耐心~