CPP优雅的生成全排列

发表于 阅读次数： Changyan： 本文字数： 2.8k 阅读时长 ≈ 3 分钟

为何会有这个问题？

网易笔试很悲催的遇到这个问题，然后脑子生锈用很蠢的循环去写，而且还没写出来，这里我整理了一些其他的办法来优化，争取做到 高效，简洁，优美。

方法一 ：STL的next_permutation

使用简洁，优美，但是不够高效，生成全部排列的复杂度大概为 $ O(n!*n) $,每次生成的复杂度为O(n). next_permutation

注意，生成前需要排序，按照$ < \(的顺序排序。或者自定义comp对象。\) (fisrt, last, comp) $

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;

void cout_nums(const vector<int> &nums){ //打印数组
    for(int i=0;i<nums.size();i++)
        cout <<nums[i]<<" ";
    cout <<endl;
}

int main(){
    vector<int> nums; //数组
    vector<vector<int>> permutations;//存储所有排列
    for(int i=0;i<5;i++) //初始化数组
        nums.push_back(i);

    sort(nums.begin(),nums.end()); //按照从小到大的顺序排序
    permutations.push_back(vector<int>(nums.begin(),nums.end())); 
    while(next_permutation(nums.begin(),nums.end()))//生成下一个排列
        permutations.push_back(vector<int>(nums.begin(), nums.end()));

    for(int i=0;i<permutations.size();i++) //打印所有排列
        cout_nums(permutations[i]);

    return 0;
}

方法二 DFS 递归生成

速度理论最优\(O(n!)\),但实际和方法一速度差不多，都很慢。使用更简洁，不过实现时需要注意trick。

DFS就是模仿挑选的过程，值得注意的是这里采用交换来实现的挑选。

而为了保证生成不会重复，需要在额外进行一次交换来进行复位。

证明如下： 交换， 递归调用，再交换序列会恢复原状。

对于长度为1的情况: 只有一次循环，且只和本身交换一次，显然成立

​ c == 第一次交换 ==> c => 递归调用(生成结果) == 第二次交换 ==> c 显然符合

假设长度为n是会恢复原状,则长度n+1时

​ \(x, (n_1,..,n_n)\) == 第一次交换(与元素\(n_k\)交换) ==> \(n_x， (n_1,n_2,...,n_{k-1},x,n_{k+1},...,n_n)\)

==> 递归调用，长度为n的情况，结束后序列显然不变 == 第二次交换(将元素\(n_k\) 放回) ==> 得到原序列 \(x, (n_1,..,n_n)\)

数列每次打乱都会恢复原状，因此每一次挑选都不会重复，不过结果是无序的

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
void perm(int depth, vector<int> &nums, vector<vector<int>> &perms){
    if (depth >= nums.size()){
        perms.push_back(vector<int>(nums.begin(), nums.end()));
        return;
    }
    for (int i = depth; i < nums.size(); i++){
    	//注意这里是两次交换，第一次交换挑选，第二次交换复位
        swap(nums[depth], nums[i]);
        perm(depth + 1, nums, perms);
        swap(nums[depth], nums[i]);
    }
}
void perm(vector<int> &nums, vector<vector<int>> &perms){
    //对nums内的数字生成全排列
    perm(0, nums, perms);
}

使用方法如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;

void cout_nums(const vector<int> &nums){
    for(int i=0;i<nums.size();i++)
        cout <<nums[i]<<" ";
    cout <<endl;
}

void perm(int depth, vector<int> &nums, vector<vector<int>> &perms)
{
    if (depth >= nums.size())
    {
        perms.push_back(vector<int>(nums.begin(), nums.end()));
        return;
    }
    for (int i = depth; i < nums.size(); i++)
    {
        swap(nums[depth], nums[i]);
        perm(depth + 1, nums, perms);
        swap(nums[depth], nums[i]);
    }
}

void perm(vector<int> &nums, vector<vector<int>> &perms)
{
    perm(0, nums, perms);
}

int main(){

    vector<int> nums;
    vector<vector<int>> permutations;
    for(int i=0;i<4;i++)
        nums.push_back(i);

    perm(nums,permutations);

    for(int i=0;i<permutations.size();i++)
        cout_nums(permutations[i]);

    return 0;
}

结语

内置next_permutation或着采用 递归(DFS)+两次交换 实现。