如何在不使用左移位的情况下找到给定集合的幂集？

Question

我正在尝试找出如何实现一种算法来找到给定集合的幂集，但我遇到了一些麻烦。这些集合实际上是向量，所以例如我得到 Set<char> set1{ 'a','b','c' }; 我会做 PowerSet(set1); 我会得到所有的集合但如果我这样做 Set<char> set2{ 'a','b','c', 'd' }; 我会做 PowerSet(set2)，但我会错过其中的几组。

Set<Set<char>> PowerSet(const Set<char>& set1)
{
    Set<Set<char>> result;
    Set<char> temp;
    result.insertElement({});
    int card = set1.cardinality();
    int powSize = pow(2, card);
    
    for (int i = 0; i < powSize; ++i)
    {
        for (int j = 0; j < card; ++j)
        {
            if (i % static_cast<int> ((pow(2, j)) + 1))
            {
                temp.insertElement(set1[j]);
                result.insertElement(temp);
            }
        }
        temp.clear();
    }
    return result;
}

供参考：

cardinality() 是我的 .h 中的一个函数，它 returns 集合的大小。
insertElement() 将元素插入到集合中，同时忽略重复项。
我之所以先 temp.insertElement(s[j]) 然后 result.insertElement(temp) 是因为 result 是 set 的 set 所以我需要创建一个临时设置以将元素插入然后将其插入结果。
clear()是清空集合的函数
我还有 removeElem() 删除指定的元素（如果它存在），否则它会忽略它。

Answer 1

您的 if 测试是胡说八道 -- 它应该类似于

if ((i / static_cast<int>(pow(2,j))) % 2)

您还需要在内循环之后（就在 temp.clear() 之前）将 temp 插入到结果中。

通过这些更改，只要 pow(2, card) 不溢出 int 就应该可以工作——在大多数机器上大约 card == 30。

如何在不使用左移位的情况下找到给定集合的幂集？

How to find the power set of a given set without using left shift bit?

c++

powerset