排列：
LC31 Next Permutation[找到一个大于，不能是大于等于]
LC46 Permutations[别忘了排序]
LC60 Permutation Sequence

子集：
LC78 子集

组合：
LC77 组合

排列

下一排列/上一排列

STL中的排列操作

std::is_permutation: 判断一个序列是否为另一个序列的排列
std::next_permutation: 变换范围 [first, last) 为来自所有按相对于 operator< 或 comp 的字典序的下个排列。若这种排列存在则返回 true ，否则变换范围为首个排列（如同用 std::sort(first, last) ）并返回 false 。
std::prev_permutation: 变换范围 [first, last) 为来自于相对于 operator< 或 comp 的字典序的所有排列集合的上个排列。若这种排列存在则返回 true ，否则变换范围为末排列（如同用 std::sort(first, last); std::reverse(first, last); ）并返回 false 。

简单实现

下一排列
- 找到序列a的最长不增后缀，即从后往前遍历序列，找到i, 使得a[i - 1] < a[i], 该后缀记为a[i:]。如果找不到这样的i，说明当前排列已经是最大的排列了。比如[5,4,3,2,1]，可以看到该序列中不存在这样一个元素a[i]使得a[i - 1] < a[i]。最大排列为排序的逆序。
- a[i:]已经是不增的序列了。换句话说，a[i:]已经是自己的最大排列了。我们不能靠交换a[i:]中的元素来获得更大的排列。我们尝试交换a[i:]中的元素和a[:i]中的元素来获得更大的排列。
- 为了让修改后的序列是下一排列，我们不能让a[i - 1]变得太大。我们考虑更改a[i:]前一个元素a[i - 1]。我们找到a[i:]中第一个比a[i - 1]大的元素，用它和a[i - 1]交换。[注意此处必须是大于，不能是大于等于]
- ❓交换后的后缀a[i:]仍然是一个不增的后缀。为了获得最小的，有新的前缀的序列，我们把a[i:]逆序即可。[对于最后两步的原理还不是很明白]
例子[1,3,5,4,2]:
- 找到最长不增后缀:[5,4,2] —> i = 2, a[i] = 5
- 找到该后缀中第一个大于后缀前一个元素(a[1])的元素 —> a[3] = 4。
- 交换a[4]和a[1] —> [1,4,5,3,2]
- 逆序后缀 —> [1,4,2,3,5]

详细解释见: Next lexicographical permutation algorithm, Project Nayuki

Feb/20/2020 code

class Solution {
public:
    void nextPermutation(vector<int>& nums) {
        if(nums.size() < 2) return;
        auto i = --nums.end();

        while(i != nums.begin())
        {
            auto ii = i;
            --i;

            if(*i < *ii)
            {
                auto j = --nums.end();
                // must be the greater, cannot be equal
                while(!(*j > *i))
                {
                    --j;
                }
                iter_swap(i, j);
                reverse(ii, nums.end());
                return;
            }
        }
        reverse(nums.begin(), nums.end());
    }
};

next_permutation

class Solution {
public:
    void nextPermutation(vector<int>& nums) {
        if (nums.size() < 2) return;
        
        auto i = nums.end();
        --i;
        while(true)
        {
            auto ii = i;
            --i;
            
            if(*i < *ii)
            {
                auto j = nums.end();
                --j;
                while(!(*i < *j)) --j;
                iter_swap(i,j);
                reverse(ii, nums.end());
                return;
            }
            
            if (i == nums.begin())
            {
                reverse(nums.begin(), nums.end());
                return;
            }
            
        }
    }
};

产生所有排列

递归法

一个序列$S = \{1, 2, 3, \cdots , n\}$的所有排列为
固定$1$, $S - \{1\}$的所有排列
固定$2$, $S - \{2\}$的所有排列
$\cdots$
固定$n$, $S - \{n\}$的所有排列

code

class Solution {
public:
    vector<vector<int>> permute(vector<int>& nums) {
        vector<vector<int>> permutations{};
        permute(nums, 0, permutations);
        return permutations;
    }

    void permute(vector<int>& nums, size_t k, vector<vector<int> >& permutations)
    {
        if (k == nums.size())
        {
            permutations.push_back(nums);
            return;
        }

        for (size_t i = k; i < nums.size(); ++i)
        {
            swap(nums[i], nums[k]);
            permute(nums, k + 1, permutations);
            swap(nums[i], nums[k]);
        }
    }
};

使用下一排列产生所有排列：

该方法较采用递归法效率较高。但是如果要产生所有排列，需要先把序列排序称为最小排列。

code

class Solution {
public:
    vector<vector<int>> permute(vector<int>& nums) {
        sort(nums.begin(), nums.end());
        auto res = vector<vector<int>>{};
        res.push_back(nums);
        while(next_permutation_(nums.begin(), nums.end()))
        {
            res.push_back(nums);
        }
        return res;
    }
    template<typename It>
    bool next_permutation_(It first, It last)
    {
        if(last - first < 2) return false;
        // find the head of the reverse increasing subarray
        auto i = last - 1;
        
        while(i != first)
        {
            auto ii = i;
            --i;
            if(*i < *ii)
            {
                // find the first element j in the reverse increasing
                // subarray, such that *j > *i
                auto j = last - 1;
                while(!(*j > *i)) --j;
                // swap i and j
                iter_swap(i, j);
                // reverse the subarray
                reverse(ii, last);
                return true;
            }
        }

        // the last permutation
        reverse(first, last);
        return false;
    }
};

code

class Solution {
public:
    vector<vector<int>> permute(vector<int>& nums) {
        if (nums.size() < 2) return {nums};
        sort(nums.begin(), nums.end());
        vector<vector<int> > permutations;
        permutations.push_back(nums);
        while(next_permutation(nums.begin(), nums.end()))
            permutations.push_back(nums);
        return permutations;
    }
};

第k个排列

LC60, Permutation Sequence
详细解法见:全排列生成算法：next_permutation, 程序控, cnblogs

code

class Solution {
public:
    string getPermutation(int n, int k) {
        --k;
        // prepare the factorials
        array<int, 11> fs{};
        fs[0] = 1;
        for(int i = 1; i < fs.size(); ++i)
        {
            fs[i] = i * fs[i - 1];
        }

        // prepare the num list
        list<int> nums(n);
        iota(nums.begin(), nums.end(), 1);

        // prepare the stringBuilder
        stringstream ss{};

        // start
        while(n > 0)
        {
            int num = k / fs[--n];
            auto it = nums.begin();
            while(num > 0) {++it; --num;}
            ss << *it;
            nums.erase(it);
            k = k % fs[n];
        }

        return ss.str();
    }
};

子集

LC78 子集

$\varnothing$的幂集为$\{\varnothing\}$
$\{a\}$的幂集为$\{\varnothing, \{a\}\}$ = 空集的幂集并空集的幂集中所有的集合并a产生的集合
同理：$\{a,b\}$的幂集为$\{\varnothing, \{a\}, \{b\}, \{a,b\}\}$

推论：求一个集合A的幂集，我们可以先从这个集合中去掉一个元素a。求去掉元素a的集合$A - {a}$的幂集P，然后将再将a和幂集P中所有集合求并得到集合Q。A的幂集为P+Q。

为了防止迭代器失效，我们先将结果幂集vector<vector<int>>初始化为我们想要的大小。
C++11中提供计算2的整数次幂的函数exp2，我们可以用它来计算幂集的大小。
此时幂集中的vector<int>全为空集，我们初始化一个迭代器last，让他指向第一个空集之后。
对于nums中的元素n，不断的将区间[begin, last)之间的vector拷贝，push_back(n)，之后再放回集合。可以通过transform实现。

设nums数组总元素个数为N，每次构造一个子集最坏需要$O(N)$的时间，一共有$\Theta(2^N)$个集合，因此复杂度为$O(N2^N)$

code

class Solution {
public:
    vector<vector<int>> subsets(vector<int>& nums) {
        // compute the size for the powerset
        size_t powerset_size = exp2(nums.size());
        // create and allocate the space for powerset
        auto powerset = vector<vector<int>>(powerset_size);
        auto last = ++powerset.begin();
        for(auto n : nums)
        {
            transform(powerset.begin(), last, last, 
            // we must copy the set here
            [n](auto set)
            {
                set.push_back(n);
                return set;
            });
            last += last - powerset.begin();
        }
        return powerset;
    }
};

组合

见回溯#组合

Xuanyi Fu Blog

排列、组合、子集

排列

下一排列/上一排列

STL中的排列操作

简单实现

产生所有排列

递归法

使用下一排列产生所有排列：

第k个排列

子集

组合