search all subsets?

P

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
 
V

Victor Bazarov

Patrick said:
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
 
F

fred.l.kleinschmidt

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.
 
R

red floyd

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 :)
 
K

Kira Yamato

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.
 

Ask a Question

Want to reply to this thread or ask your own question?

You'll need to choose a username for the site, which only take a couple of moments. After that, you can post your question and our members will help you out.

Ask a Question

Members online

Forum statistics

Threads
473,744
Messages
2,569,482
Members
44,901
Latest member
Noble71S45

Latest Threads

Top