一起学习交流~

全子集

算法 laomuji 9个月前 (12-21) 659次浏览 已收录 0个评论

一、什么是全子集

子集概念

子集是一个数学概念:如果集合A的任意一个元素都是集合B的元素,那么集合A称为集合B的子集

全子集概念

全,顾名思义就是一个集合的所有子集

应用

全子集是DFS的经典应用
但也可以用BFS等其它算法解决

二、全子集有哪些

比如有一个数组 [1,2,3,4]
全子集如下

 []
 [1] [2] [3] [4]
 [1,2] [1,3] [1,4] [2,3] [2,4] [3,4]
 [1,2,3] [1,2,4] [1,3,4] [2,3,4]
 [1,2,3,4]

三、全子集分类

3.1 无重复数字

无重复数字,比如数组里 都是唯一的数字,如[1,3,5,6]之类的

3.2 有重复数字

有重复数字,比如[1,2,2,3]之类的

四、二进制实现全子集

原理

比如[1,2,3,4]

0 0 0 0 = []
0 0 0 1 = [4]
0 0 1 0 = [3]
0 0 1 1 = [3,4]
0 1 0 0 = [2]
0 1 0 1 = [2,4]
0 1 1 0 = [2,3]
0 1 1 1 = [2,3,4]
1 0 0 0 = [1]
1 0 0 1 = [1,4]
1 0 1 0 = [1,3]
1 0 1 1 = [1,3,4]
1 1 0 0 = [1,2]
1 1 0 1 = [1,2,4]
1 1 1 0 = [1,2,3]
1 1 1 1 = [1,2,3,4]

从N个0到N个1(n表示数组的元素个数)
恰好是全子集的所有情况,即2^n次方
但只能解决无重复元素的情况

代码

    //二进制的方法
    vector>binarySubset(vector& vec) {
        vector>result;
        result.push_back(vector());//首先有一个空子集
        if (vec.size() == 0)return result;//空集的子集也是空集
        //1 0-1 2^1
        //2 00-11 2^2
        //3 000-111 2^3
        //4 0000-1111 2^4
        int length = 1;
        //2的n次方是出现情况的次数
        for (int i = 1; i <= vec.size(); i++)length = length * 2;
        for (int i = 1; i < length; i++)
        {
            int tempNum = i;
            vectortempVec;
            for (int j = 0; j < vec.size(); j++)
            {
                if ((tempNum & 1) == 1) tempVec.push_back(vec[j]);
                tempNum = tempNum >> 1;
            }
            result.push_back(tempVec);
        }
        return result;
    }

五、DFS实现全子集

无重复元素

此时 dfs顺序应该为:

1
12
123
1234
124(回到123,把3扔出去,再加入4,与123同级)
13
134
14
2
23
234
24
3
34
4
    vector> DFSSubset(vector& nums) {
        vector> result;
        result.push_back(vector());//空集,任何时间都存在
        DFSFunc(result, nums, 0);
        return result;
    }
        void DFSFunc(vector>& result, vector& nums, int startPos, vectorprefix = vector()) {
        if (startPos == nums.size())return;
        for (size_t i = startPos; i < nums.size(); i++)
        {
            vectortempVec;
            //先把前缀加进去
            for (size_t j = 0; j < prefix.size(); j++)tempVec.push_back(prefix[j]);
            //再把当前数字加进去
            tempVec.push_back(nums[i]);
            result.push_back(tempVec);
            //通过当前数字进行递归
            //先把当前数字作为前缀,再把当前数字递归后移除
            prefix.push_back(nums[i]);
            DFSFunc(result, nums, i + 1, prefix);
            prefix.pop_back();
        }
    }

有重复元素情况

有重复元素,如:[1,2,2,3]
需要对情况进行筛选
如果执行上面的代码,会得到下面的结果

[]
[1]
[1,2]
[1,2,2]
[1,2,2,3]
[1,2,3]
[1,2]
[1,2,3]
[1,3]
[2]
[2,2]
[2,2,3]
[2,3]
[2]
[2,3]
[3]

可以发现,有重复的情况发生
如果想去掉重复,明显有两种方法

1. 全部生成后删除重复数据

这种情况太暴力,就不写例子了

2. 根据条件跳过重复的数据

首先对数组进行排序,保证数组是有序的
此时 重复的数据是相邻的
只需要判断上一个数据和当前数据是否相同
相同时 就是重复的,可以跳过
但当前数据作为第一个数据时,仍然需要加入进去

    //存在重复子集的情况
    vector> DFSSubset2(vector& nums) {
        sort(nums.begin(), nums.end());
        vector> result;
        result.push_back(vector());
        DFSFunc2(result, nums, 0);
        return result;
    }
    void DFSFunc2(vector>& result, vector& nums, int startPos, vectorprefix = vector()) {
        if (startPos == nums.size())return;
        for (size_t i = startPos; i < nums.size(); i++)
        {
            //若i为startPos时,仍然需要把当前值添加进去 
            if (i != 0 && nums[i] == nums[i - 1] && i != startPos) {
                continue;
            }
            vectortempVec;
            //先把前缀加进去
            for (size_t j = 0; j < prefix.size(); j++)tempVec.push_back(prefix[j]);
            //再把当前数字加进去
            tempVec.push_back(nums[i]);
            result.push_back(tempVec);
            //通过当前数字进行递归
            //先把当前数字作为前缀,再把当前数字递归后移除
            prefix.push_back(nums[i]);
            DFSFunc2(result, nums, i + 1, prefix);
            prefix.pop_back();
        }
    }

六、BFS

无重复元素

比如[1,2,3,4] ,无重复元素的情况
此时顺序应该为

[1,2,3,4]
入:进入队列
出:进入结果
入:[1,2,3,4]
出:[1],入[2,3,4](前缀为1)
出:[2],入[3,4](前缀为2)
出:[3],入[4](前缀为3)
出:[4],入空
此时:
结果:[[1],[2],[3],[4]]
队列:[[2,3,4],[3,4],[4]](前缀分别为1,2,3)

出:2,入[3,4](前缀为12)
出:3,入[4](前缀为13)
出:4,入空
出:3,入[4](前缀为23)
出:4,入空
出:4,入空
此时:
结果:[[1],[2],[3],[4],[1,2],[1,3],[1,4],[2,3],[2,4],[3,4]]
队列:[[3,4],[4],[4]](前缀分别为12,13,23)

出:3,入[4](前缀为123)
出:4,入空
出:4,入空
出:4,入空
此时:
结果:[[1],[2],[3],[4],[1,2],[1,3],[1,4],[2,3],[2,4],[3,4],[1,2,3],[1,2,4],[1,3,4],[2,3,4]]
队列:[[4]](前缀分别为123)

出:4,入空
此时:
结果:[[1],[2],[3],[4],[1,2],[1,3],[1,4],[2,3],[2,4],[3,4],[1,2,3],[1,2,4],[1,3,4],[2,3,4],[1,2,3,4]]
队列:[]

代码如下:

//BFS无重复子集
    vector> BFSSubset(vector& nums) {
        vector>result;
        result.push_back(vector());
        if (nums.size() == 0)return result;
        sort(nums.begin(), nums.end());
        queue, vector>>que;
        //循环存入值和前缀数组
        for (size_t i = 0; i < nums.size(); i++) {
            pairnum(i,nums[i]);//数字不是单纯的数字,还要带着自己的下标
            que.push(pair, vector>(num, vector()));
        }
        //循环出队
        while (que.size())
        {
            auto currentData = que.front();
            que.pop();
            //因为没有重复,也可以使用find在nums里查找出现的下标
            size_t beginPos = currentData.first.first;
            for (size_t i = beginPos + 1; i < nums.size(); i++)
            {
                int pushValue = nums[i];
                vectorprefix(currentData.second);
                prefix.push_back(currentData.first.second);//增加一个前缀
                que.push(pair, vector>(pair(i,pushValue), vector(prefix)));
            }
            vectortempVec;//存放出栈的结果
            //先压入前缀再压入当前数字
            for (size_t i = 0; i < currentData.second.size(); i++)tempVec.push_back(currentData.second[i]);
            tempVec.push_back(currentData.first.second);
            result.push_back(tempVec);
        }
        return result;
    }

有重复元素

有重复元素的情况用BFS不太好解决
我用的是暴力解法
如有有更好的解法欢迎留言

//BFS有重复子集
    vector> BFSSubset2(vector& nums) {
        vector>result;
        result.push_back(vector());
        if (nums.size() == 0)return result;
        sort(nums.begin(), nums.end());
        queue, vector>>que;
        //循环存入值和前缀数组
        for (size_t i = 0; i < nums.size(); i++) {
            pairnum(i, nums[i]);//数字不是单纯的数字,还要带着自己的下标
            que.push(pair, vector>(num, vector()));
        }
        //循环出队
        while (que.size())
        {
            auto currentData = que.front();
            que.pop();
            size_t beginPos = currentData.first.first;
            vectortempVec;//存放出栈的结果
            for (size_t i = beginPos + 1; i < nums.size(); i++)
            {
                int pushValue = nums[i];
                vectorprefix(currentData.second);
                prefix.push_back(currentData.first.second);//增加一个前缀
                que.push(pair, vector>(pair(i, pushValue), vector(prefix)));
            }
            //先压入前缀再压入当前数字
            for (size_t i = 0; i < currentData.second.size(); i++)tempVec.push_back(currentData.second[i]);
            tempVec.push_back(currentData.first.second);
            result.push_back(tempVec);
        }
        //暴力去重
        vector>res;
        for (size_t i = 0; i < result.size(); i++)
        {
            //查找是否存在
            if (find(res.begin(),res.end(),result[i])!=res.end()) {
                continue;
            }
            res.push_back(result[i]);
        }
        return res;
    }

七、总结

虽然全子集用其它办法也能解决,但是最简单最容易理解的还是DFS

喜欢 (0)
订阅评论
提醒
guest
0 评论
内联反馈
查看所有评论