c++ - 递归查找子集

Question

这是我尝试创建的一个递归函数，用于查找在 STL 集中传递的所有子集。这两个参数是一个用于搜索主题的 STL 集，以及一个数字 i >= 0，它指定子集应该有多大。如果整数大于集合，则返回空子集

我不认为我这样做是正确的。有时是对的，有时不是。 STL 集顺利通过。

list<set<int> > findSub(set<int>& inset, int i)
{
    list<set<int> > the_list;

    list<set<int> >::iterator el = the_list.begin();
    if(inset.size()>i)
    {

        set<int> tmp_set;
        for(int j(0); j<=i;j++)
        {
            set<int>::iterator first = inset.begin();
            tmp_set.insert(*(first));
            the_list.push_back(tmp_set);
            inset.erase(first);
        }

        the_list.splice(el,findSub(inset,i));
    }

    return the_list;
}

Answer 1

据我了解，您实际上是在尝试从给定的集合中生成“i”元素的所有子集，对吗？

修改输入集会给你带来麻烦，你最好不要修改它。

我认为这个想法很简单，尽管我会说你把它倒过来了。因为它看起来像作业，所以我不会给你一个 C++ 算法；)

generate_subsets(set, sizeOfSubsets) # I assume sizeOfSubsets cannot be negative
                                     # use a type that enforces this for god's sake!
  if sizeOfSubsets is 0 then return {}
  else if sizeOfSubsets is 1 then
    result = []
    for each element in set do result <- result + {element}
    return result
  else
    result = []
    baseSubsets = generate_subsets(set, sizeOfSubsets - 1)
    for each subset in baseSubssets
      for each element in set
        if no element in subset then result <- result + { subset + element }
    return result

关键点是:

• 首先生成排名较低的子集，因为您必须对它们进行迭代
• 不要尝试在子集中插入一个元素，如果它已经存在，它会给你一个不正确大小的子集

现在，您必须理解这一点并将其转换为“真实”代码。