全排列讲解

递归的精髓很难理解，一旦理解，算法之路就会轻松很多
下面记录一下递归的一种——全排列问题
通常的全排列问题一般是通过交换函数实现的，但是之后学习中，发现dfs也可以实现全排列因为dfs的本质就是递归，还有一种十分简单的代码，一般在做全排列的题目都是用的这种方法——它就是STL内置的全排列函数next_permutation，如果后面还有比它大的排列，那么它就会返回true，如果没有了，那就返回false；

• 首先我们要知道递归的概念，递归就是直接或间接调用自身，这个很重要，因为我们把大问题化成一个比一个小的问题的时候，发现小问题也是一个递归，这时候我们就找到递归的终止条件，然后逐一返回
• 递归一定要满足两个条件，递归表达式与递归结束条件
  前面我们说到把递归分解成小问题，由小问题的解推出大问题的解
  

交换函数实现全排列

初始碰到的就是这种交换函数，也是这种交换函数理解起来非常的难，这也就是为什么一旦掌握递归的精髓就能更好更快的理解其他的算法，因为后序有一部分算法的核心代码就是用递归实现的

下面这段代码就是交换函数实现全排列的核心代码，也是最难理解的代码

 void dfs(int now)
    {
   
        if (now == 10)
        {
   
            int a = g[1] * 100 + g[2] * 10 + g[3];
            int b = g[4] * 100 + g[5] * 10 + g[6];
            int c = g[7] * 100 + g[8] * 10 + g[9];
            if (a + b == c)
                w[++cnt].a = a, w[cnt].b = b, w[cnt].c = c;
            return;
        }
        for (int i = now; i <= 9; ++i)
        {
   
            swap(g[now], g[i]);
            dfs(now + 1);
            swap(g[now], g[i]);
        }
    }

• 首先now==9就代表只有一个数了，参与全排列的只有一个数那就输出一个解
• 9不是代表已经结束所有的递归了，它是一个下标，也就是数组最后一个元素，最后一个元素是什么是不知道，一旦执行到最后一个元素，也就代表所有的元素都已经参与全排列了，那么就可以输出了一组数据
• 当执行到 dfs(now + 1);这句代码的时候，我们并不会立刻执行后面的而是继续执行递归的子递归，直到所有的数都被用尽
• 举个例子1,2，3,4实现全排列，首先我们固定第一个数，其次固定第二个,第三个，当固定第四个数的时候就可以输出一个排列，只是这里的1234恰巧与数组下标元素一致所以就会混淆概念，我们是递归到最后一个数才输出全排列，dfs（now+1）里面又是一个dfs函数，函数里面有循环有递归，递归里面又有一个子dfs函数…直到遇到程序终止条件，也就是选取的数还有最后一个就结束输出，输出完一个之后我们就执行一次交换函数，因为输出1234之后我们交换一下就可以继续递归输出1243，恰巧交换之后也是只剩下一个数，也就是固定1，2位置的数，后序数字轮流来做第三个，继续递归输出，交换函数就是回到上一个层次。
  
• 在递归的过程中，我们轮流来做第一个，n个数也就有n中可能，剩下n-1个数，再从n-1个数中选取一个数来做第二个数…以此类推一共有n(n-1)!种方案
  
  
• 到现在就应该可以明白一个故事：从前有座山，山里有个庙，庙里有两个和尚，大和尚正在给小和尚讲故事，讲的就是从前有座山…,也就是说递归里面还有子递归，子递归里面还有子子递归，直到遇到递归结束条件

题目描述
用1, 2, 3…9 这九个数字组成一个数学公式，满足：ABC + DEF = GHI，每个数字只能出现一次，编写程序输出所有的组合。

输入
无

输出
输出所有的 ABC + DEF = GHI，
每行一条数据，格式为ABC+DEF=GHI
输出结果按照ABC升序排列，如果ABC相同，则按照DEF升序排列。
AC代码

#include <bits/stdc++.h>
#define ll long long
using namespace std;
const int maxn = 1e5 + 5;
const int inf = 0x3f3f3f3f;
int g[maxn];
struct node
{
   
    int a, b, c;
    bool operator<(const node x)
    {
   
        if (a != x.a)
            return a < x.a;
        return b < x.b;
    }
} w[maxn];
int cnt = 0;
void dfs(int now)
{
   
    if (now == 9)
    {
   
        int a = g[1] * 100 + g[2] * 10 + g[3];
        int b = g[4] * 100 + g[5] * 10 + g[6];
        int c = g[7] * 100 + g[8] * 10 + g[9];
        if (a + b == c)
        {
   
            w[++cnt].a = a;
            w[cnt].b = b;
            w[cnt].c = c;
        }
        return;
    }
    for (int i = now; i <= 9; ++i)
    {
   
        swap(g[now], g[i]);
        dfs(now + 1);
        swap(g[now], g[i]);
    }
}
int main()
{
   
    for (int i = 1; i <= 9; ++i)
        g[i] = i;
    dfs(1);
    sort(w + 1, w + cnt + 1);
    for (int i = 1; i <= cnt; ++i)
        printf("%d+%d=%d\n", w[i].a, w[i].b, w[i].c);
    return 0;
}

STL内置函数实现全排列

函数next_permutation()是按照字典序产生排列的，并且是从数组中当前的字典序开始依次增大直至到最大字典序

next_permutation()会取得[first,last)所标示之序列的下一个排列组合，如果没有下一个排列组合，便返回false;否则返回true。

在不字符串的情况下

next_permutation(str.begin(),str.end());

在知道数组的情况下

next_permutation(a,a+n);

AC代码

#include <bits/stdc++.h>
#define ll long long
using namespace std;
const int maxn = 1e5 + 5;
const int inf = 0x3f3f3f3f;
int g[maxn];
struct node
{
   
    int a, b, c;
    bool operator<(const node x)
    {
   
        if (a != x.a)
            return a < x.a;
        return b < x.b;
    }
} w[maxn];
int cnt = 0;
int main()
{
   
    for (int i = 1; i <= 9; ++i)
        g[i] = i;
    do
    {
   
        int a = g[1] * 100 + g[2] * 10 + g[3];
        int b = g[4] * 100 + g[5] * 10 + g[6];
        int c = g[7] * 100 + g[8] * 10 + g[9];
        if (a + b == c)
        {
   
            w[++cnt].a = a;
            w[cnt].b = b;
            w[cnt].c = c;
        }
    } while (next_permutation(g + 1, g + 10));
    sort(w + 1, w + cnt + 1);
    for (int i = 1; i <= cnt; ++i)
        printf("%d+%d=%d\n", w[i].a, w[i].b, w[i].c);
    return 0;
}

dfs实现全排列

dfs与马的遍历思路有点类似，可以参考我的另一篇博客快速理解dfs算法——传送门

#include <bits/stdc++.h>
#define ll long long
using namespace std;
const int maxn = 1e5 + 5;
const int inf = 0x3f3f3f3f;
int g[maxn], vis[maxn];
struct node
{
   
    int a, b, c;
    bool operator<(const node x)
    {
   
        if (a != x.a)
            return a < x.a;
        return b < x.b;
    }
} w[maxn];
int cnt = 0;
void dfs(int now, int v)
{
   
    if (now == 9)
    {
   
        int a = v / 1000000;
        int b = v / 1000 % 1000;
        int c = v % 1000;
        if (a + b == c)
        {
   
            w[++cnt].a = a;
            w[cnt].b = b;
            w[cnt].c = c;
        }
        return;
    }
    for (int i = 1; i <= 9; ++i)
    {
   
        if (vis[i] == 0)
        {
   
            vis[i] = 1;
            dfs(now + 1, v * 10 + i);
            vis[i] = 0;
        }
    }
}
int main()
{
   
    dfs(0, 0);
    sort(w + 1, w + cnt + 1);
    for (int i = 1; i <= cnt; ++i)
        printf("%d+%d=%d\n", w[i].a, w[i].b, w[i].c);
    return 0;
}