//------------------// Returns the power set //------------------Set * Set::operator ~ (void){ // gets the new size of 2^n and adds one to // account for the element that stores the size int nPowSize = (2 << (this->m_nSize-1)) + 1; Set *Pow = new Set[nPowSize]; // store size in the first element of the first // set in the array Set cSet; cSet.Add(nPowSize); Pow[0] = cSet; // go through the size of the power set // and add the element in position j to the // current set if its bit is 1 for(int i=0; i < nPowSize; ++i) { for(int j=0; j < this->m_nSize; ++j) { if(i & (1<<j)) { Pow[i+1].Add(this->GetElement(j)); } } } return Pow;} // operator ~We had to write our own set for this, and I know the set implementation isn't the best. The size of the powerset is 2^n, but I had to add the size in there, so that takes up the extra element. Remember that Pow[] returns a set, since it is a set of sets. Then you can go through those subsets in the Pow[] and add up the sum of the elements to check if it is within a reasonable tolerance to an integer.
[edit]
A little more explaination. What this basically does is count in binary up to the size of the set. Say you have a set of size 3, which is {2,3,4}. The size of the powerset is 8;
000 - {}
001 - {4}
010 - {3}
100 - {2}
011 - {3,4}
101 - {2,4}
110 - {2,3}
111 - {2,3,4}
although in the code, the actual algorithm adds it in this order.
000 - {}
100 - {2}
010 - {3}
110 - {2,3}
001 - {4}
101 - {2,4}
011 - {3,4}
111 - {2,3,4}
[Edited by - njpaul on July 1, 2005 2:37:36 PM]
