0

假设我有一个数组 {1,2,3}，我必须添加这些元素才能像这样设置

Pass 1: {1}, {2}, {3} (Adding sets of size 1 )
Pass 2: Pass1 + {1,2}, {1,3} , {2,3} (Combination of sets of previous pass and sets of size 2)
Pass 3: Pass2 + {1,2,3}

最后我的套装应该有{1},{2},{3}, {2,3},{1,3},{1,2},{1,2,3}

我试图编码这个

void generateSets(int arr[], int size, int sum)
{
    set<set<int> > mySet;
    for(int i=0;i< size ; i++)
    {
        set< set<int> >::iterator iter;
        **for (iter = mySet.begin(); iter != mySet.end(); ++iter) 
            {**
            set<int> s(*iter);
            for(int k=0;k<size; k++)
                    {
                s.insert(arr[k]);
                }
            mySet.insert(s);
        }
    }
}

我无法像我提到的那样生成集合。请有人可以帮助我！

4

1 回答 1

1

这样做的方法通常涉及递归或类似的东西。
这个想法是“让递归处理”不包含 1 个元素的子集，一旦拥有它，您需要添加包含该元素的子集。

它应该看起来像这样：（这是一个类似 c++ 的伪代码，而不是工作代码！）

//extend(set<set<int>>, int) is an auxilary function used by the main logic function
set<set<int>> extend(set<set<int>> original, int e) { 
   set<set<int>> result = new set<set<int>>();
   for each set<int> s in original { 
       tempSet = s.clone();  
       tempSet.add(e);
       result.add(tempSet);
   }
   return result;
}

//this is the main logic function
set<set<int> > findSets(int[] arr, int size) { 
   if (size == 0) return new set<set<int>>(new set<int>()); //return a set containing only an empty set
   set<set<int>> results = new set<set<int>>(); //result set
   results = findSets(arr,size-1); //all subsets without element arr[n-1], using recursion.
   results.union(extend(results,arr[size-1]); //add all subsets containing arr[n-1]
   return results;
}
于 2013-08-09T12:30:11.273 回答