search all subsets?

Discussion in 'C++' started by Patrick, Dec 21, 2007.

  1. Patrick

    Patrick Guest

    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
    Patrick, Dec 21, 2007
    #1
    1. Advertising

  2. 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
    Victor Bazarov, Dec 21, 2007
    #2
    1. Advertising

  3. Patrick

    Guest

    On Dec 21, 9:16 am, Patrick <> wrote:
    > 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
    , Dec 21, 2007
    #3
  4. Patrick

    red floyd Guest

    wrote:
    > On Dec 21, 9:16 am, Patrick <> wrote:
    >> 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 :)
    red floyd, Dec 21, 2007
    #4
  5. Patrick

    Kira Yamato Guest

    On 2007-12-21 12:16:08 -0500, Patrick <> said:

    > 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
    Kira Yamato, Dec 22, 2007
    #5
    1. Advertising

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

It takes just 2 minutes to sign up (and it's free!). Just click the sign up button to choose a username and then you can ask your own questions on the forum.
Similar Threads
  1. Roger Varley
    Replies:
    20
    Views:
    889
    jan V
    Aug 14, 2005
  2. will

    xsl subsets of nodesets

    will, Jul 7, 2003, in forum: XML
    Replies:
    3
    Views:
    845
    Marrow
    Jul 8, 2003
  3. Gaijinco

    Generate All Subsets

    Gaijinco, Sep 26, 2005, in forum: C Programming
    Replies:
    7
    Views:
    551
    Emmanuel Delahaye
    Sep 26, 2005
  4. Gaijinco

    Generate All Subsets

    Gaijinco, Sep 26, 2005, in forum: C++
    Replies:
    7
    Views:
    531
  5. joe chesak

    All contiguous subsets

    joe chesak, Mar 25, 2010, in forum: Ruby
    Replies:
    4
    Views:
    143
    joe chesak
    Mar 26, 2010
Loading...

Share This Page