search all subsets?

[Patrick]

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??

Thanks:
Patrick

[Victor Bazarov]

Patrick wrote:

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??

AFAIK, C++ doesn't have "subset of M from N" kind of functionality.
You'd have to roll your own.

V
--
Please remove capital 'A's when replying by e-mail
I do not respond to top-posted replies, please don't ask

[fred.l.kleinschmidt]

On Dec 21, 9:16*am, Patrick <[e-mail]:

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??

Thanks:
Patrick

The algorithm you use will depend on what condition must be obeyed.
For example, if the condition is that the subset must not contain any
odd numbers, it is pretty easy. However, if the condition is that the
subset must contain as many of the original numbers as possible but no
three are allowed to sum up to 172, then it is a lot trickier.
--
Fred Kleinschmidt

[red floyd]

fr*****************@boeing.com wrote:

On Dec 21, 9:16 am, Patrick <[e-mail]:

>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??

Thanks:
Patrick

The algorithm you use will depend on what condition must be obeyed.
For example, if the condition is that the subset must not contain any
odd numbers, it is pretty easy. However, if the condition is that the
subset must contain as many of the original numbers as possible but no
three are allowed to sum up to 172, then it is a lot trickier.

I prefer to check for membership in the set of all sets that do not
contain themselves :-)

[Kira Yamato]

On 2007-12-21 12:16:08 -0500, Patrick <na*******@gmail.comsaid:

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