On 2007-12-21 12:16:08 -0500, Patrick <natbrowne@gmail.comsaid:
Quote:
Hi,
I want to write a programs that checks if a set of numbers in a list
obey a condition, the problem is that i have say "n" numbers and i
need to check all subsets of the n numbers for the condition.
How do i go about asking c++ to find the subsets and then check??
Usually, statements that say something about the set of *all* subsets
of a set can be restated as one that just say something about the
original set. So, you might want to try to restate the condition first.
If that doesn't work, then you can try to see if the condition is
stable under some set operations. By "stable under set operations," I
mean this:
(1) "If subsets A and B satisfy the condition, then so does A union B."
or
(2) "If subsets A and B satisfy the condition, then so does A intersect B."
or any other set operations. If so, then it is easy. Suppose it
satisfies (1), then you just need to check the condition for subsets of
cardinality 1 (there will be n of them). And if those checks out, then
you can use (1) to conclude that *all* subsets satisfy it. Similarly,
you can work out the equivalent tricks for (2) or any other set
operations.
However, if even that doesn't work, then I don't have any more
suggestion to give you other than just writing code to iterate through
all the subsets. As far as I know, standard C++ has no ready-to-roll
facility to do this. You just have to write the code. It's not really
that hard anyway. Just use an array of bits, use its bit pattern to
determine membership, then increment the array to iterate to the next
subset.
--
-kira
