STL：全排列算法

旧城等待， 2022-05-21 00:19 191阅读 0赞

## 字典法非递归全排列 ##

> 这里解析的是《STL源码剖析》中全排列的算法，属于非递归算法；  
> 下面我用尽可能简单的语言让读者明白什么是字典法全排列，额外插一句：  
> `我也很讨厌看全是字的解析，但是我保证这篇解析已经很白话了，稍稍耐心看完，保证能懂`

## 思路： ##

> 这里我们以字符串”1234”为例，因为它更容易看出大小关系  
> ①首先，先理解我这句话  
> “`一个序列的所有排列情况（即全排列），一定能按照从小到大的顺序依次全部列举出来`”  
> 如果不是很好理解，请看下图：  
> ![这里写图片描述][70]  
> 如图所示，字符串“1234”全排列的情况全部列举出来了，并且可以按照从小到大的顺序列举出来，如1234<1243<1324<1423<…<4312<4321；  
> 现在再回过头理解这句话，  
> “`一个序列的所有排列情况（即全排列），一定能按照从小到大的顺序依次全部列举出来`”  
> 是不是就能明白了，如果不信，可以自己再选个字符串，把它的所有排列情况列举出来，看看是否满足一个从小到大的顺序。  
> ②在理解第①步里的内容后，我们再看下一步，仍然是先理解我另外一句话，  
> “`按照这个从小到大的顺序依次走一遍，刚好就是一次全排列`”  
> 有人可能看到这句话会想，“废话！所有排列情况都走一遍，肯定是全排列啊！用得着你说？”  
> 很好，不过有一个细节是“`按照从小到大的顺序走`”，而不是随意走一遍。  
> 至于“为什么非要按照从小到大的顺序走”，在第③步解释，现在还请先接受第②步的“无理要求”。  
> ③有了上面的铺垫，现在直接进行字典法全排列的算法演示，只有先看到算法的效果，才能更好的解释算法的原理：  
> 基本循环步骤如下：  
> 1.从右往左遍历该序列，寻找到第一对满足“左边的值小于右边的值”的字符对；  
> 2.再次从右往左遍历该序列，寻找到第一个大于字符对左边的字符，然后交换这两个字符；  
> 3.交换完毕，将“从字符对右边的字符开始到最后一个字符为止”这个序列逆置；  
> 4.重复上面123步骤，直到遍历到第一个字符，即再没有字符对出现。  
> 如图：  
> ![这里写图片描述][70 1]  
> ![这里写图片描述][70 2]  
> 不难发现，上图显示的过程，刚好就是从字符串“1234”->“1243”->“1324”的顺序  
> 恰恰好就是“按从小到大顺序列举的全排列”情况中的前三种，如果有兴趣，你可以尝试继续往下走，一个转换出来的一定是“1342”，再下一个一定是“1423”，依此类推。。。  
> ④看了上面的过程，可以知道，如果按照第③步里的基本循环步骤，能把所有的排列情况按照从小到大的顺序走完，从而也就达到了全排列的目的  
> 那么，现在就来解释一下为什么按照上面的循环步骤就能“恰好是按照从小到大的顺序走完”  
> 1.我们最开始的字符串“1234”是递增的字符串，即使所有情况中最小的字符串  
> 2.我们第一次遍历寻找到的字符对是满足“`左边的值大于右边`”的字符对；  
> 3.找到字符对后又从右往左遍历一次，寻找到要交换的值是`第一个大于字符对左边的值的字符`  
> 4.有了上面三点的基础，那么就能实现`每次交换一定是把大的值换到前面，小的值换到后面`；  
> 并且，交完完毕之后的逆置，保证了`交换的位置的后面的部分保持一个递增状态`，即最小状态；  
> 因此，就能保证，每一次转换，一定是转换成刚好比该字符串大一个顺序位的字符串，  
> 如，“1243”转换后一定是恰好转成“1324”而不是“1342”或其他情况

## 总结： ##

> **其实上面一大堆文字描述，不如你按照第③步的基本循环步骤在纸上多画几遍来的效果好**

## 代码如下： ##

> 说那么多，最后还是把代码放上来吧，下面是《STL源码剖析》提供的全排列算法源码

#include <iostream>
    #include <vector>
    using namespace std;
    
    bool perm(vector<int>& v)//全排列
    {
        if (v.size() <= 1)
        {
            return false;
        }
        vector<int>::iterator i = v.end();
        --i;
        while (1)
        {
            vector<int>::iterator ii = i;
            --i;
            if (*i < *ii)
            {
                vector<int>::iterator j = v.end()-1;
                while (*j <= *i)
                {
                    --j;
                }
                int tmp = *i;
                *i = *j;
                *j = tmp;
                reverse(ii, v.end());
                return true;
            }
            if (i == v.begin())
            {
                reverse(v.begin(), v.end());
                return false;
            }
        }
    }
    
    void Print(const vector<int>& v)//打印vector数组
    {
        for (int i = 0; i < v.size(); ++i)
        {
            printf("%d ", v[i]);
        }
        printf("\n");
    }
    
    void test()
    {
        vector<int> v;
        //全重复情况
        v.push_back(1);
        v.push_back(1);
        v.push_back(1);
        v.push_back(1);
    
        //普通情况
        //v.push_back(1);
        //v.push_back(2);
        //v.push_back(3);
        //v.push_back(4);
    
        do
        {
            Print(v);
        } while (perm(v));
    }
    
    int main()
    {
        test();
    
        system("pause");
        return 0;
    }

> **普通情况：**  
> ![这里写图片描述][70 3]  
> **全重复情况：**  
> ![这里写图片描述][70 4]

[70]: /images/20220521/8bf7e62ba8864bdba67016139bdf9895.png
[70 1]: /images/20220521/2a3b75e088634d20982a22f34068f60b.png
[70 2]: /images/20220521/3c110ca4ee834a339b910110509fc0f8.png
[70 3]: /images/20220521/743b713e5b554701b18a20d2bea79208.png
[70 4]: /images/20220521/4908c62849c44cb9b12c4acd2816a8aa.png