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 に答える