递归查找子集 [英] recursively find subsets

问题描述

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

Here is a recursive function that I'm trying to create that finds all the subsets passed in an STL set. the two params are an STL set to search for subjects, and a number i >= 0 which specifies how big the subsets should be. If the integer is bigger then the set, return empty subset

我不认为我这样做正确。有时它是正确的，有时它不是。 stl集得到通过。

I don't think I'm doing this correctly. Sometimes it's right, sometimes its not. The stl set gets passed in fine.

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;
}

推荐答案

实际上试图从给定的集合中生成'i'元素的所有子集？

From what I understand you are actually trying to generate all subsets of 'i' elements from a given set right ?

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

Modifying the input set is going to get you into trouble, you'd be better off not modifying it.

我认为这个想法很简单，虽然我会说你倒退了。由于它看起来像作业，我不会给你一个C ++算法;）

I think that the idea is simple enough, though I would say that you got it backwards. Since it looks like homework, i won't give you a C++ algorithm ;)

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

b $ b

关键点是：

The key points are:

• 首先生成较低级别的子集，因为您必须迭代它们


• 不要尝试在子集中插入元素（如果元素已经存在），则会给您一个不正确大小的子集。

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

Now, you'll have to understand this and transpose it to 'real' code.

这篇关于递归查找子集的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！