C++ 幂集算法

2024 年 8 月 28 日 | 阅读 6 分钟

幂集是所有子集的集合，包括空集和原始集。可以使用递归方法或涉及位操作的迭代方法来构建一个集合的幂集。集合是一组独特的元素。空集是没有元素的集合；幂集是给定集合所有可能子集的集合。

理解问题

我们得到一个包含 'N' 个元素的数组，具体为 [a, b, c]。我们需要为这个数组创建一个幂集，其中幂集的每个子集都按升序排序。必须返回子集数组。每个子集的成员应按升序排列。子集在答案数组中的顺序无关紧要。

示例：[a, b, c]

假设我们从集合 [a, b, c] 开始。该集合的不同子集如下：

[ ]

[a]

[b]

[a, b]

[c]

[a, c]

[b, c]

[a, b, c]

现在，幂集就是所有这些子集的集合。

[ [], [a], [b], [a, b], [c], [a, c], [b, c], [a, b, c] ]

方法 1：暴力枚举法

我们将从空子集开始，并以 'N' 步遍历它们，其中 'N' 是初始数组大小 [a, b, c]。每一步我们都有两种可能性：包含或排除当前选定的元素。

让我们使用一个例子来演示这种方法，其中 'N' 设置为 3，输入数组的内容为 [a, b, c]。

步骤 0： 从空集 [[]] 开始。
步骤 1： 复制上一步的子集。在一个副本中，向每个子集添加 'a'；在另一个副本中，保持子集不变。结果是 [[], [a]]。
步骤 2： 再复制上一步的子集两份。在一个副本中，向每个子集添加 'b'；在另一个副本中，保持子集不变。子集现在加倍：[[], [a], [b], [a, b]]。
步骤 3： 复制上一步的子集两份。在一个副本中，向每个子集添加 'c'；在另一个副本中，保持子集不变。它生成以下幂集：[[], [a], [b], [a, b], [c], [a, c], [b, c], [a, b, c]]。

如果我们想生成幂集，此方法仔细检查在数组 [a, b, c] 中包含和排除每个元素（a、b 和 c）的所有可能排列。每一步都有效地使幂集中的子集总数加倍，从而产生所有可能子集的完整集合。

示例

我们来看一个例子来说明 C++ 中的幂集算法。

#include <iostream>
#include <vector>

using namespace std;

vector<vector<char>> powerSet(vector<char> &array) 
{
    int l = array.size();

    // array for storing the result
    vector<vector<char>> answer = {{}};

    // iterating over the array
    for (int i = 0; i < l; i++) 
    {
        char element = array[i];
        int len = answer.size();

        // traverse through the array answer
        for (int j = 0; j < len; j++) 
        {
            vector<char> tem = answer[j];

            // element included
            tem.push_back(element);
            answer.push_back(tem);
        }
    }

    // Return the array ?answer?.
    return answer;
}

int main()
{
    // user input
    int number;
    cin >> number;
    vector<char> array(number);
    for(int i = 0; i < number; i++)
       cin >> array[i];

    // function calling
    vector<vector<char>> answer = powerSet(array);

    // displaying the result
    for(int i = 0; i < answer.size(); i++){
        for(int j = 0; j < answer[i].size(); j++)
            cout << answer[i][j] << " ";
   
        cout << endl;
    }

    return 0;
}

输入

3
a
b
c

输出

a 
b 
a b 
c 
a c 
b c 
a b c

复杂度

时间复杂度

O(N * (2^N))，其中 'N' 是数组 'ARRAY' 的元素数量。

外层循环迭代 'N' 次，对于外层循环的每次迭代 'i'，内层循环迭代 2^i 次，在该范围内，我们在每个子集末尾复制长度至多为 N 的列表。

因此，总时间复杂度为 N * (2⁰ + 2¹ + ... + 2^N-2 + 2^N-1) = O(N * 2^N)。

空间复杂度： O(1)。

不需要额外的空间。

方法 2：递归方法

我们将编写一个递归函数 (solve) 来在此策略中生成子集。

将向递归函数提供以下四个参数：

我们必须找到名为 'ARRAY' 的数组的幂集。
当前元素在 ARRAY 数组中的索引是 'IDX'（最初为零）。
当前数组被指定为 'CURRENT'，并将包含一个子集。
'ANSWER' 是一个存储我们最终响应的数组的数组。

每一步我们都有两个选项：将元素添加到选定的子集。此外，如果当前选定元素的索引大于或等于给定数组的大小，则递归函数将终止。

终止条件

如果 IDX >= ANSWER.size()，则将 'CURRENT' 推入 'ANSWER' 并返回。

递归调用

通过将 'IDX' 值增加 1 并用排除当前元素的数组 'ARRAY' 替换来执行递归函数。
将 'ARRAY[IDX]' 推入 'CURRENT'。
调用递归函数，该函数将 'IDX' 值增加 1 并用当前选定元素填充数组 'ARRAY'。

现在，让我们研究算法的源代码。

文件名：Power_set.c

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

void solve(int idx, vector<int> &array, vector<int> current, vector<vector<int>> &answer) 
{
    //condition
    if (idx >= array.size()) 
    {
        answer.push_back(current);
        return;
    }
    
    //The recursive function call
    solve(idx + 1, array, current, answer);

    
    current.push_back(array[idx]);
    solve(idx + 1, array, current, answer);
}

vector<vector<int>> powerSet(vector<int> array) 
{
    //To hold all subsets, create a collection of arrays.
    vector<vector<int>> answer;
    
    vector <int> current;
    int idx = 0;

    solve(idx, array, current, answer);

    // returning the answer array
    return answer;
}

int main()
{
    // user input
    int number;
    cin>>number;
    vector<int> array(number, 0);
    for(int i = 0; i < number; i++)
       cin >> array[i];

    //Using the powerSet() function to construct the 'ARRAY' power set.
    vector<vector<int>> answer = powerSet(array);

    // displaying the power set
    for(int i = 0; i < answer.size(); i++){
        for(int j = 0; j < answer[i].size(); j++)
            cout << answer[i][j] << " ";
        cout << endl;
    }
}

输入

3
1 2 3

输出

复杂度

时间复杂度

O(2^N)，其中 'N' 是数组 'ARR' 的长度。

与递归函数一样，我们在每个阶段进行两次调用，共进行 2^N 次调用。因此，总时间复杂度为 O(2^N)。

空间复杂度

O(N)，其中 'N' 是数组的大小，'ARRAY' 是数组的长度。

在最坏的情况下，递归树的深度将为 'N'。因此，递归调用堆栈的总空间复杂度为 O(N)。

方法 3：位掩码方法

我们可以使用位来指示关联元素是否是当前子集的一部分，因为它可能是 0 或 1。因此，每个位模式都代表整个集合的一个子集。通过这种方式，我们可以获取所有子集，而无需占用任何额外的空间。

假设我们有 'ARRAY' 数组。

假设我们的响应是 'ANSWER' = [[]]。

迭代 0 <= I <= 2^N 次并执行以下操作：

考虑以下数组：TEMP = []
对于每个 0 <= j < N，遍历 ARRAY[j] 并执行以下操作：
如果 'i' 的第 'j' 位已设置，则将第 'j' 个值添加到 'TEMP'。
应将 'TEMP' 添加到 'ANSWER' 的末尾。

文件名：Powerset3.cpp

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

vector<vector<int>> powerSet(vector<int> &array) 
{
    int number = array.size();

    //an array for storing all the subsets
    vector<vector<int>> answer;
    for (int i = 0; i < (1<<number); i++)
    {
        vector<int> tem;

        // iterating over the array
        for (int j = 0; j < number; j++) 
        {
            // checking the jth bit
            if (i & (1 << j)) 
            {
                tem.push_back(array[j]);
            }
        }

        
        answer.push_back(tem);
    }

    // Return the ?ANSWER?.
    return answer;
}
int main()
{
    // user input
    int number;
    cin >> number;
    vector<int> array(number, 0);
    for(int i = 0; i < number; i++)
       cin >> array[i];

    // function calling.
    vector<vector<int>> answer = powerSet(array);

    //The display of the power set
    for (int i = 0; i < answer.size(); i++) {
        for (int j = 0; j < answer[i].size(); j++)
            cout << answer[i][j] << " ";
        cout << endl;
    }
}

输入

3
1 2 3

输出

下一个主题C++ 中检测到栈溢出

C++ 幂集算法

理解问题

方法 1：暴力枚举法

示例

方法 2：递归方法

方法 3：位掩码方法

联系信息

关注我们

教程

面试题

在线编译器

Python

Java

.Net Framework

AI, ML and Data Science

Cloud Technology

B.Tech and MCA

Web Technology

PHP

Software Testing

Technical Interview

Java Interview

Python

Web Interview

Database Interview

B.Tech / MCA

Important Interview

Software Testing Interview

Company Interviews

Online Compilers

Multiple Choice Questions

C++ 教程

C++ 控制语句

C++ 函数

C++ 数组

C++ 类和对象

C++ 构造函数

C++ 继承

C++ 多态

C++ 抽象

C++ 命名空间

C++ 模板

C++ 字符串

C++ 指针

信号处理

C++ 异常

C++ 文件与流

C++ STL 教程

面试题

选择题

C++ 程序

C++ STL Stack

C++ STL Bitset

C++ STL Deque

C++ STL List

C++ STL Map

C++ STL Math

C++ STL priority_queue

C++ STL Queue

C++ STL Multiset

C++ STL Multimap

C++ STL Set

C++ STD Strings

C++ STL Vector

C++ 操纵符

C++ STL Algorithms

C++ Algorithm

C++ Iterators

C++ 杂项

C++ 幂集算法

理解问题

方法 1：暴力枚举法

示例

方法 2：递归方法

方法 3：位掩码方法

相关帖子

C++ 吃豆人游戏

C 和 C++ 中的字符算术

C++ 并发

C++ 程序实现插值搜索算法

C++ 链式哈希程序

C++ 稳定婚配问题

C++ 字符数组转字符串

为什么（非 const）全局变量在 C++ 中是邪恶的

在 C++ 中按字典序打印所有排列

C++ STL 中的 beta(), betaf() 和 betal() 函数

订阅 Tpoint Tech

联系信息

关注我们

教程

面试题