算法基础：使用STL实现全排列

太过爱你忘了你带给我的痛 2022-12-18 02:56 162阅读 0赞

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2xpdW1pYW9jbg_size_16_color_FFFFFF_t_70_pic_center]  
STL是标准模版库的缩写，是泛化编程的实现，基本观念是将数据和操作进行分离，数据使用容器进行管理，操作由算法进行实现，迭代器在两者之间进行沟通，使得任何算法和任何容器都有可能进行交互运作。这篇文章以一个简单的例子进行介绍STL使用上的便利之处。

### 目录 ###

*  临位对换实现全排列
 *  STL的next\_permutation
 *  总结

--------------------

# 临位对换实现全排列 #

比如通过临位对换方式实现的全排列，代码可能如下：

#include <iostream>
    using namespace std;
    
    void swap(int* x, int* y) {
        int tmp = *x; *x = *y; *y = tmp;
    }
    
    void permutation(int *list, int k, int n) {
        if (k == n-1) {
            for (int i=0; i<n; i++) cout << list[i] << " ";
            cout<<endl;
            return;
        }
        for (int i=k; i<n; i++) {
            swap(&list[k],&list[i]);
            permutation(list,k+1,n);
            swap(&list[k],&list[i]);
        }
    }
    int main() {
        int n = 0;
        while (scanf("%d",&n) != EOF) {
            int list[n];
            for (int i=0; i<n; i++) {
                scanf("%d",&list[i]);
            }
            permutation(list, 0, n);
        }
        return 0;
    }

# STL的next\_permutation #

而使用STL的next\_permutation，则非常简单，比如如下即可：

while (next_permutation(list,list+n)){
                for (int i=0; i<n; i++) cout << list[i] << " ";
                cout << endl;
            }

唯一需要注意的是next\_permutation默认输出的是按照字典序排序的下一个排列，比如1 2 3的输入，next\_permutation的结果为1 3 2，上述代码的执行结果为，因为第一个1 2 3就是输入本身

1 3 2 
    2 1 3 
    2 3 1 
    3 1 2 
    3 2 1

这种情况下把while循环倒过来写，用do-while的方式就可以了（注意next\_permutation本身是获取下一个，这种写法只能将本身也输出了而已）

do {
                for (int i = 0; i < n; i++) cout << list[i] << " ";
                cout << endl;
            } while (next_permutation(list,list+n));

--------------------

# 总结 #

所以看到实现相同的功能，只需要调用即可，另外除此之外，还提供了pre\_permutation提供上一个排序的方式，当然还有很多其他的功能。另外对于不同类型，比如char或者其他类型，pre\_permutation无需在重复实现permutation和交换函数，这也是使用STL的优势所在，集中力量关注算法本身，对于常见的一些功能直接调用即可。

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2xpdW1pYW9jbg_size_16_color_FFFFFF_t_70_pic_center]: /images/20221122/414517358f7a464b9a473307f07de313.png