欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

子集生成算法

程序员文章站 2024-03-21 14:53:16
...

子集生成算法属于暴力法中一类非常重要的算法.

题目描述

给定一个集合,请写一个算法,得到其所有的子集.这里假定该集合不存在重复的元素.

举个栗子,给定集合[1, 2, 3], 你返回这样一堆子集:

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

位向量法

根据离散数学的知识,我们可以知道,一个长度为 n 的集合的子集有 2n 个,集合的元素其实可以对应到一个长度为 n 个二进制数上.该二进制数的第 i 位如果为 1,表示取集合的第 i 个元素,否则表示不取.

举个例子 [1, 2, 3] 可以对应到一个长度为 3 的二进制数上. 111 表示 [1, 2, 3], 011 表示 [2, 3].

二进制数 000...00 ~ 111...11 ,每个数都对应了一个子集,首先这些数各不相同,其次这些数的总数为 2n ,所以这些数对应的子集正好对应了该集合的全部子集.

下面是这种方法的一个简易实现:

#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;

/**
 * 位向量法.
 *   假定set的元素个数为n,那么用一个长度为n的bool数组来模拟位向量,数组的第i个元素为true,表示选择set
 *   的第i个元素, 否则表示不选择.假定我们从二进制的 000....00 (n个0) 开始数数, 一直数到 111...11
 *   (n个1)的话, 我们会发现我们数的每一个数,都对应了set的一个子集.利用这点,可以很快地写出子集寻找算法.
 *   举个例子,假定set为[1, 2, 3], 位向量001表示选择第3个元素,即[3]是set的一个子集.
 *   位向量111表示[1, 2, 3]为set的一个子集.
 */

/**
 * @brief 寻找所有的子集
 * @param[in] set 集合
 * @param[in] mask 位标记
 * @param[in] pos 当前已经处理到了第pos个位置了.
 * @param[in, out] subsets 用于记录结果的数组.
 */
void findSubSets(vector<int>& set, bool mask[], int pos, vector<vector<int>>& subsets)
{
    if (pos == set.size()) { /* 递归终止条件 */
        vector<int> subset;
        for (int i = 0; i < set.size(); i++) {
            if (mask[i]) subset.push_back(set[i]);
        }
        subsets.push_back(subset);
        return;
    }
    mask[pos] = true;
    findSubSets(set, mask, pos + 1, subsets);
    mask[pos] = false;
    findSubSets(set, mask, pos + 1, subsets);
}

/**
 * @brief 寻找set的所有子集.
 * @param[in] set 包含了所有元素的集合
 * @return 所有子集构成的数组
 */
vector<vector<int>> subSets(vector<int>& set)
{
    bool mask[1024];
    vector<vector<int>> subsets;  /* 用于记录所有的子集 */
    findSubSets(set, mask, 0, subsets);
    return subsets;
}

int main()
{
    vector<int> nums = { 1, 2, 3 };
    auto subsets = subSets(nums);
    for (auto &subset : subsets) {
        for (auto elem : subset) {
            cout << elem << " ";
        }
        cout << endl;
    }
    getchar();
}

增量构造法

这种方法比上面的位向量法稍微难以理解一点,不过做法也相当有意思.

  • 假定我们已经有了一个子集,长度为 i,且这个子集由集合的前 k 个元素组合产生,显然 k <= i, 那么我们经由这个子集生成长度为 i + 1 的子集呢?

很简单,自然是遍历集合的后 n - k个元素,将每一个元素添加到该子集后面即可.

  • 假定我们已经有了由集合前 k 个元素组合而成的所有的子集,长度为 2k , 我们如何生成由集合前 k + 1 个元素组成而成的所有的子集呢?

很简单,对于集合的第 k + 1 个元素,我们可以选择添加进有前 k 个元素构成的子集,这样可以生成 2k 个子集. 也可以选择不添加,可以生成 2k 个子集,恰好是前 k 个元素构成的子集.

增量构造法结合了这两点.

这种方法的简单实现如下:

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

/**
 * 增量构造法
 *  这种方法比位向量法稍微要复杂一些.事实上,我并不推荐这种方法,它并没有比位向量法效率更高或者
 *  更容易理解.
 */

/**
 * @brief 寻找所有长度为subsetIdx + 1的子集
 * @param[in] set 要求子集的集合
 * @param[in] setIdx 用于表示集合的下标从0~setIdx-1的元素即前setIdx个元素在这轮迭代中不能再取.
 * @param[in] subset 由集合的前setIdx元素组合而成的长度为subsetIdx的子集.
 * @param[in] subsetIdx 子集的长度.
 * @param[in/out] subsets 用于记录所有的子集的数组
 * @return 无
 */
void findSubsets(vector<int>& set, int setIdx, int* subset, int subsetIdx, vector<vector<int>>& subsets)
{
    /**
     * 前一个子集长度为subsetIdx,且该子集由集合的前setIdx个元素组合而成,如何经由该子集生成长度为
     * subsetIdx+1的子集呢?
     */  
    for (int i = setIdx; i < set.size(); i++) {
        /* 此时的subset是由集合前i个元素构成的一个子集,如何生成由集合的前i+1个元素构成的子集呢? */
        /* 选择set的第i+1个元素作为subset的subsetIdx位置上的元素 */
        subset[subsetIdx] = set[i];
        /* 将新生成的,长度为subsetIdx+1的子集加入subsets */
        subsets.push_back(vector<int>(subset, subset + subsetIdx + 1));
        /* 如果不取第i个元素, 那么subset的长度为subsetIdx,它已经在subsets中了 */
        /**
         * 正如前面所见,我们已经生成了一个由前i+1个元素组合而成的,长度为subsetIdx+1的子集,
         * 接下来的递归要在这个已经生成的子集的基础上继续生成.i+1表示对于后面的位来说,set从
         * 0~i位置的元素都不能取了.
         * subsetIdx+1表示第subsetIdx位置的元素已经取好,然后要往下一个位置填充元素.
         */
        findSubsets(set, i + 1, subset, subsetIdx + 1, subsets);
    }
}

/**
* @brief 寻找set的所有子集.
* @param[in] set 包含了所有元素的集合
* @return 所有子集构成的数组
*/
vector<vector<int>> subSets(vector<int>& set) {
    vector<vector<int>> subsets;
    int subset[1024];
    findSubsets(set, 0, subset, 0, subsets);
    return subsets;
}


int main()
{
    vector<int> nums = { 1, 2, 3 };
    auto subsets = subSets(nums);
    for (auto &subset : subsets) {
        for (auto elem : subset) {
            cout << elem << " ";
        }
        cout << endl;
    }
    getchar();
}