Permutation

发表于   |   分类于 ，   |  

在Leetcode上刷到几道排列的算法题， 总结一下。

Next permutation

问题描述

就是求给定序列下一个排列组合，具体见
Leetcode题目地址

算法描述

  1. 从序列右端到左端找到降序的第一个数（partition number）， 例如： ”5684“ 中从右到左第一个降序的数为”6“；
  2. 从右到左找到第一个比partition number大的数（change number）；
  3. 交换partition number 和 change number；
  4. reverse partition number右边的序列；

具体c++实现

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
class Solution {
public:
    void nextPermutation(vector<int>& nums) {
        next_permutation(nums.begin(), nums.end());
    }
    
    template<typename BidiIt>
    bool next_permutation(BidiIt first, BidiIt last) {
        const auto rfirst = reverse_iterator<BidiIt>(last);
        const auto rlast = reverse_iterator<BidiIt>(first);
        
        auto pivot = next(rfirst);
        
        while (pivot != rlast && *prev(pivot) <= *pivot) ++pivot;
        
        if (pivot == rlast) {
            reverse(rfirst, rlast);
            return false;
        }
        
        auto change = find_if(rfirst, pivot, bind1st(less<int>(), *pivot));
        
        swap(*change, *pivot);
        reverse(rfirst, pivot);
        
        return true;
    }
};

PS: STL 标准库中 algorithm 头文件中已经实现 next_permutation 函数

Permutation Sequence

问题描述

求序列第k个排列组合，具体见
Leetcode题目地址。

求解思路

枚举

运行 k-1 次 next_permutation

康托编码

主要利用康拓展开逆过程的思想，首先解释一下康拓展开。

  • 康拓展开
    康拓展开就是一种特殊的哈希函数，把一个整数$x$展开成如下形式：
    $$ x = an*n! + a{n-1}(n-1)! + … + a_11! $$
    其中$a_i$为整数，并且$0 <= a_1 < a_2 < … < a_n$。
    例如， 取序列$a_i$为{1,2,3}，其全排列：123,132,213,231,312,321，分别代表数字0,1,2,3,4,5。
    从全排列到对应的数字可以通过康拓展开得到，具体如下思考：
    以321为例， 第一位为3，小于3的数有2个，除去第一位剩下两位共有$2!$种排列组合，所以共有$2\times 2!$种排列可能；
    再看第二位为2，小于2的数有1个，除去第一位和第二位剩下一位共有$1!$种排列组合， 所以共有$1\times 1!$种排列可能；
    以此类推，小于321的排列组合共有$22!+11!+0*0!=5$个，所有321是第5个大排列组合（从0开始）。
  • 康拓展开逆过程
    举例说明，要得到序列{1,2,3}第5个大的排列组合，首先确定第一个数为第$5/2! = 2$大的数，为3;
    确定第二个数，$5\%2!=1$，为第$1/1!= 1$大的数， 为2；
    以此类推。。。
    具体公式如下：
    $$ ki = k{i-1}\%(n-i+1)!$$
    $$ a_i = k_i/(n-i)! $$

具体c++实现

康拓展开逆过程求解第k个全排列组合

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
class Solution {
public:
    string getPermutation(int n, int k) {
        string s(n, '0');
        for (int i = 0; i < n; ++i) s[i] += i+1;
        return kth_permutation(s, k);
    }
private:
    int factorial(int n) {
        int result = 1;
        for (int i = 1; i <=n; ++i) result *= i;
        return result;
    }
    
    template<typename Sequence>
    Sequence kth_permutation(const Sequence& seq, int k) {
        const int n = seq.size();
        Sequence S(seq);
        Sequence result;
        
        --k;
        int base = factorial(n-1);
        
        for (int i = n-1; i > 0; k %= base, base /= i, --i) {
            auto a = next(S.begin(), k/base);
            result.push_back(*a);
            S.erase(a);
        }
        result.push_back(S[0]);
        return result;
    }
};

Permutations

问题描述

列出所给不重复序列的全排列，具体见Leetcode题目地址

求解思路

枚举

通过next_permutation

递归

具体c++实现

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
class Solution {
public:
    vector<vector<int>> permute(vector<int>& nums) {
        sort(nums.begin(), nums.end());
        
        vector<vector<int>> result;
        vector<int> path; // 中间结果
        
        dfs(nums, path, result);
        return result;
    }
private:
    void dfs(const vector<int>& nums, vector<int>& path,
            vector<vector<int>>& result) {
        if (path.size() == nums.size()) { // 收敛条件
            result.push_back(path);
            return;
        }
        // 扩展状态
        for (auto i : nums) {
            auto pos = find(path.begin(), path.end(), i);
            
            if (pos == path.end()) {
                path.push_back(i);
                dfs(nums, path, result);
                path.pop_back();
            }
        }
    }
};

Permutations II

问题描述

列出所给序列（含重复值）的全排列，具体见Leetcode题目地址

求解思路

同 Permutation 类似

具体c++实现

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
class Solution {
public:
    vector<vector<int>> permuteUnique(vector<int>& nums) {
        sort(nums.begin(), nums.end());
        
        unordered_map<int, int> count_map; // 记录每个元素出现次数
        for_each(nums.begin(), nums.end(), [&count_map](int e) { // lambda函数引用捕获count_map
            if (count_map.find(e) != count_map.end())
                count_map[e]++;
            else
                count_map[e] = 1;
        });

        vector<int> path;
        vector<vector<int>> result;
        dfs(nums, count_map, path, result);
        return result;
    }
private:
    void dfs(const vector<int>& nums, unordered_map<int, int>& count_map,
            vector<int>& path, vector<vector<int>>& result) {
        if (path.size() == nums.size()) { // 收敛条件
            result.push_back(path);
            return;
        }
        // 扩展状态
        for (auto i : count_map) {
            int count = 0; // 统计出现次数
            for (auto j = path.begin(); j != path.end(); j++) {
                if (i.first == *j) count++;
            }
            if (count < i.second) {
                path.push_back(i.first);
                dfs(nums, count_map, path, result);
                path.pop_back();
            }
        }
    }
};

Combinations

问题描述

Given two integers n and k, return all possible combinations of k numbers out of 1 … n. 具体见Leetcode题目地址

具体c++实现

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
// 递归
class Solution {
public:
    vector<vector<int>> combine(int n, int k) {
        vector<vector<int>> res;
        vector<int> p;
        dfs(n, k, 1, 0, p, res);
        return res;
    }
private:
    void dfs(int n, int k, int start, int cur,
            vector<int>& p, vector<vector<int>>& res) {
        if (cur == k) {
            res.push_back(p);
            return;
        }
        for (int i = start; i <= n; ++i) {
            p.push_back(i);
            dfs(n, k, i+1, cur+1, p, res);
            p.pop_back();
        }
    }
};

// 迭代
class Solution {
public:
    vector<vector<int> > combine(int n, int k) {
        vector<int> values(n);
        iota(values.begin(), values.end(), 1);
    
        vector<bool> select(n, false);
        fill_n(select.begin(), k, true);
    
        vector<vector<int> > result;
        do{
            vector<int> one(k);
            for (int i = 0, index = 0; i < n; ++i)
                if (select[i])
                    one[index++] = values[i];
            result.push_back(one);
        } while(prev_permutation(select.begin(), select.end()));
        return result;
    }
};