递归查找子集
这是一个递归函数,我试图创建一个查找所有在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;
}
从我的理解你实际上试图从一个给定的集合生成'我'元素的所有子集?
修改输入集会让你陷入麻烦,你最好不要修改它。
我认为这个想法很简单,尽管我会说你把它弄倒了。因为它看起来像功课,我不会给你一个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-21 15:24:51
不客气。 – 2009-10-21 15:38:52
我在这个一直盯着几分钟,我想不出你的思路是认为它会工作。在探索可能参与的每个可能子集之前,您将永久删除输入列表的几个成员。
尝试解决您打算使用伪代码的解决方案,并查看是否可以在没有stl干扰的情况下看到问题。
看起来(我不是英语母语),你可以做的是计算功率集(所有子集的集合),然后选择只匹配条件的子集。
你可以找到如何计算在Wikipedia Power set page和Math Is Fun上设置的功率的方法(链接在*页面上的外部链接部分,名为Power Set from Math Is Fun,因为垃圾邮件阻止机制我不能直接在这里发布) 。在数学上很有趣,主要部分它是二元的。
在附注中,作为提示,使用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