聚合元素的排列与子集

集合元素的排列与子集

一、集合的排列

       给定一个集合S，含有n个不重复的元素，输出该集合元素的所有排列，leetcode对应题目为：http://oj.leetcode.com/problems/permutations/。打印所有排列的复杂度为O(n*n!)，因为共有n！个不同的排列，打印每个排列的复杂度为O(n)。打印所有的排列一般采用深搜策略，先给出一个常规的方法：

图1排列树形式的解空间
排列树形式的解空间有个规律，就是随着递归深度的增加，每个节点的子节点个数都逐次减一，这也是为什么排列算法的复杂度是O(n!)。
此外，还有一种生成排列的方法，思想不太好懂，下面只给出代码：
图2 子集树形式的解空间
根据上面的分析，我们可以知道求k个元素的子集，我们只需要判断当前已经选择的元素个数，如果已经选择了k个元素，则找到一个符合的子集，无需再遍历子节点。如果尚未选择k个元素，但是已经达到叶节点（n个元素已经判断一遍），我们可以直接返回，这说明此次的遍历没有找到符合的子集。按照这个思路，代码如下：
vector<vector<int> > subsets(vector<int> &S) {sort(S.begin(),S.end());//给定的集合可能未排序                vector<vector<int>> result;                for(int i=0;i<1<<S.size();i++)//每一个二进制数都是一个子集        {            vector<int> r;            for(int j=0;j<S.size();j++)//获得为1的位置            {                if(i>>j&1)                {                    r.push_back(S[j]);                }            }                        result.push_back(r);        }                return result;}
上述三个问题都可以通过深搜完美解决，后两个问题还可以通过位运算解决，不管是深搜还是位运算都有比较相似的模式，希望通过上面的分析，大家能深刻理解深搜和位运算。