递归查找子集

这是一个递归函数，我试图创建一个查找所有在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; 
}

来源

2009-10-20 Stanislav Palatnik

在附注中，作为提示，使用typedef。它会使你的代码更具可读性，并且更易于调试：'typedef std :: set int_set; typedef std :: list int_set_list;'即使在你的函数中：'typedef int_set :: iterator iterator'。然后使用它们;你的代码会更小，更清晰。 – GManNickG 2009-10-20 01:51:58

注意：splice需要一个左值作为第二个参数，但是你给它一个右值。如果你可以编译它，这是由于一个（愚蠢的）编译器扩展。 – sellibitze 2009-10-20 08:09:40

尝试给你的函数一个更具描述性的名字和/或解释这个函数应该做什么。findSub听起来很无辜，但它实际上修改了给定的集合。另外inset.size（）>我似乎不符合你的描述。你的意思是inset.size（）> = i？ – sellibitze 2009-10-20 08:12:35

从我的理解你实际上试图从一个给定的集合生成'我'元素的所有子集？

修改输入集会让你陷入麻烦，你最好不要修改它。

我认为这个想法很简单，尽管我会说你把它弄倒了。因为它看起来像功课，我不会给你一个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

的关键点是：

产生较低等级的子集，第一，因为你必须遍历在他们
不要试图在一个子集插入元素，如果它已经是，它会给你不正确大小的子集，现在

，你必须明白这一点，并置为'真正的'代码。

来源

2009-10-20 09:34:19

感谢您的伪代码:)清除了一些逻辑问题 – 2009-10-21 15:24:51

不客气。 – 2009-10-21 15:38:52

我在这个一直盯着几分钟，我想不出你的思路是认为它会工作。在探索可能参与的每个可能子集之前，您将永久删除输入列表的几个成员。

尝试解决您打算使用伪代码的解决方案，并查看是否可以在没有stl干扰的情况下看到问题。

来源

2009-10-20 02:40:59 PeterAllenWebb

我也看不到这应该达到什么。

如果这不是作业有特定的限制，我只是建议测试临时std::set与std::includes()。

来源

2009-10-20 02:50:13

看起来（我不是英语母语），你可以做的是计算功率集（所有子集的集合），然后选择只匹配条件的子集。

你可以找到如何计算在Wikipedia Power set page和Math Is Fun上设置的功率的方法（链接在维基百科页面上的外部链接部分，名为Power Set from Math Is Fun，因为垃圾邮件阻止机制我不能直接在这里发布）。在数学上很有趣，主要部分它是二元的。

来源

2009-10-20 11:35:40 oold

递归查找子集

回答

相关问题