Power set implementation

Discussion in 'C Programming' started by ar0, May 28, 2010.

  1. ar0

    ar0 Guest

    Hi,
    I'm crossposting this to comp.lang.c and comp.theory, because I'm coding
    in c, but at the same time it's a general algorithm problem.
    If it doesn't fit in either of those, please inform me.


    Now my problem: I have an integer array of length N and I want to calculate
    all possible sums of elements from that array. For example, if my array were
    of length 3 and it would look like: [1, 4, 2], I would want to calculate:
    1+4
    1+2
    1+4+2
    4+2

    Now, I imagine I could do this somehow if I could generate the "power set" of
    an array containing the numbers from 0 to N-1 and using those "subsets" as indices.


    So I'm asking: is there a "reasonable" (<300 lines of code) algorithm for getting
    the "powerset" (ie every single "subset" as an extra array) of the array [0, 1, ..., N-1]?

    Or perhaps there's a better way of approaching my problem. I would certainly be open to suggestions.

    best regards.

    --
    Sick nature.
     
    ar0, May 28, 2010
    #1
    1. Advertising

  2. lid (ar0) writes:

    > I'm crossposting this to comp.lang.c and comp.theory, because I'm coding
    > in c, but at the same time it's a general algorithm problem.
    > If it doesn't fit in either of those, please inform me.


    There's no C but I am going to fix that. comp.programming is often the
    best place place for algorithm. comp.theory is not quite the right place.

    > Now my problem: I have an integer array of length N and I want to calculate
    > all possible sums of elements from that array. For example, if my array were
    > of length 3 and it would look like: [1, 4, 2], I would want to calculate:
    > 1+4
    > 1+2
    > 1+4+2
    > 4+2


    Why would you exclude 0, 1, 2 and 4?

    > Now, I imagine I could do this somehow if I could generate the "power
    > set" of an array containing the numbers from 0 to N-1 and using those
    > "subsets" as indices.


    Yup, that's one way.

    > So I'm asking: is there a "reasonable" (<300 lines of code) algorithm
    > for getting the "powerset" (ie every single "subset" as an extra
    > array) of the array [0, 1, ..., N-1]?


    long unsigned npower = 1UL << N;
    for (unsigned long ps = 0; ps < npower; ps++)
    /* use ps here */

    In the body of the loop ps represents, in turn, each element of the
    power set of {0... N-1}. Can you see why?

    > Or perhaps there's a better way of approaching my problem. I would
    > certainly be open to suggestions.


    This solution is fine if you really want to list all the possible subset
    sums because this task will be impractical for large N. If your problem
    is really something else that you are not letting on, then there may
    well be superior methods. If so, re-post with the full story in
    comp.programming.

    --
    Ben.
     
    Ben Bacarisse, May 28, 2010
    #2
    1. Advertising

  3. ar0

    ar0 Guest

    In comp.lang.c Ben Bacarisse <> wrote:
    > Why would you exclude 0, 1, 2 and 4?

    Oh well, they're not so hard to calculate, so I just didn't mention them explicitly :)

    > long unsigned npower = 1UL << N;
    > for (unsigned long ps = 0; ps < npower; ps++)
    > /* use ps here */
    >
    > In the body of the loop ps represents, in turn, each element of the
    > power set of {0... N-1}. Can you see why?


    Wow, that's *exactly* why I asked this question. I didn't want to start malloc()ing 2^N
    seperate arrays (and I would also have had to store their respective lengths somewhere).

    So every number in the range from 0 to 2^N - 1 represents in its bit representation
    the "state" of the subset. Meaning if (2^k & ps) is true, then the k-th element of my
    set is in the subset represented by ps.

    I can't even describe how awesome I find this approach. Thank you very much for this
    line of code. It also provides a quick proof of why the powerset has exactly 2^N elements.

    > This solution is fine if you really want to list all the possible subset
    > sums because this task will be impractical for large N. If your problem
    > is really something else that you are not letting on, then there may
    > well be superior methods. If so, re-post with the full story in
    > comp.programming.


    My problem really is sheer bruteforce, and I don't think I'm gonna repost, since I think your
    code already solves my problem.
    But if I have a similar question in the future I'll know where to post it. :)

    best regards.

    --
    Sick nature.
     
    ar0, May 28, 2010
    #3
  4. ar0

    Gene Guest

    On May 28, 3:09 pm, (ar0) wrote:
    > Hi,
    > I'm crossposting this to comp.lang.c and comp.theory, because I'm coding
    > in c, but at the same time it's a general algorithm problem.
    > If it doesn't fit in either of those, please inform me.
    >
    > Now my problem: I have an integer array of length N and I want to calculate
    > all possible sums of elements from that array. For example, if my array were
    > of length 3 and it would look like: [1, 4, 2], I would want to calculate:
    > 1+4
    > 1+2
    > 1+4+2
    > 4+2
    >
    > Now, I imagine I could do this somehow if I could generate the "power set" of
    > an array containing the numbers from 0 to N-1 and using those "subsets" as indices.
    >
    > So I'm asking: is there a "reasonable" (<300 lines of code) algorithm for getting
    > the "powerset" (ie every single "subset" as an extra array) of the array [0, 1, ..., N-1]?
    >
    > Or perhaps there's a better way of approaching my problem. I would certainly be open to suggestions.
    >
    > best regards.


    Yes the bit mask way of thinking is fine. You can also reason
    recursively. If I am part way through constructing one of the subsets
    -- call it P -- and I still have a set S of items to decide whether to
    add to P or not, then the algorithm would be

    void enumerate_powerset(SET S, SET P)
    {
    if S is empty {
    output P
    }
    else {
    Let e be any element drawn from S
    // enumerate all subsets of S-e
    // that do and don't include e
    enumerate_powerset(S - e, P + e);
    enumerate_powerset(S - e, P);
    }
    }

    The trick is to picking a simple way to represent the sets. A Java
    programmer might reach for a heavyweight library. C encourages you to
    think a little harder but get a leaner result.

    Here are a couple of ideas for strings and arrays of ints:

    #include <stdio.h>

    static void epss(char *s, char *p)
    {
    if (*s == '\0') {
    printf("{%s}\n", p);
    }
    else {
    p[-1] = s[0]; // s_0 is e
    epss(s + 1, &p[-1]);
    epss(s + 1, p);
    }
    }

    #define BUF_SIZE 100

    void enumerate_powerset_of_string(char *s)
    {
    char buf[BUF_SIZE]; // buffer for partial sets
    buf[BUF_SIZE - 1] = '\0';
    epss(s, &buf[BUF_SIZE - 1]);
    }

    static void epsi(int *s, int ns, int *p, int np)
    {
    if (ns == 0) {
    int i;
    printf("{ ");
    for (i = 0; i < np; i++) printf("%d ", p);
    printf("}\n");
    }
    else {
    p[np] = s[0];
    epsi(s + 1, ns - 1, p, np + 1);
    epsi(s + 1, ns - 1, p, np);
    }
    }

    void enumerate_powerset_of_ints(int *s, int ns)
    {
    int buf[BUF_SIZE]; // buffer for partial sets
    epsi(s, ns, buf, 0);
    }

    int main(void)
    {
    int a[] = {1, 2, 3, 4};
    enumerate_powerset_of_string("ABCD");
    enumerate_powerset_of_ints(a, sizeof a / sizeof a[0]);
    return 0;
    }

    C:\>gcc ps.

    C:\>a
    {DCBA}
    {CBA}
    {DBA}
    {BA}
    {DCA}
    {CA}
    {DA}
    {A}
    {DCB}
    {CB}
    {DB}
    {B}
    {DC}
    {C}
    {D}
    {}
    { 1 2 3 4 }
    { 1 2 3 }
    { 1 2 4 }
    { 1 2 }
    { 1 3 4 }
    { 1 3 }
    { 1 4 }
    { 1 }
    { 2 3 4 }
    { 2 3 }
    { 2 4 }
    { 2 }
    { 3 4 }
    { 3 }
    { 4 }
    { }

    C:\>
     
    Gene, May 29, 2010
    #4
  5. ar0

    Alan Curry Guest

    In article <htp4d4$qff$-marburg.de>,
    ar0 <> wrote:
    >Now my problem: I have an integer array of length N and I want to calculate
    >all possible sums of elements from that array. For example, if my array were
    >of length 3 and it would look like: [1, 4, 2], I would want to calculate:
    >1+4
    >1+2
    >1+4+2
    >4+2
    >
    >Now, I imagine I could do this somehow if I could generate the "power set" of
    >an array containing the numbers from 0 to N-1 and using those "subsets"
    >as indices.


    It would be interesting to try a Gray code. Each sum corresponds to a a
    number and each number has only 1 bit changed from the previous number, so
    you can keep the sum as you go, adding or subtracting only 1 element each
    time. All you need is a quick way to determine which bit changes from Gray
    code x to Gray code x+1, and whether it changed from 0 to 1 or 1 to 0.

    --
    Alan Curry
     
    Alan Curry, May 29, 2010
    #5
  6. ar0

    Gene Guest

    On May 29, 3:56 pm, (Alan Curry) wrote:
    > In article <htp4d4$-marburg.de>,
    >
    > ar0 <> wrote:
    > >Now my problem: I have an integer array of length N and I want to calculate
    > >all possible sums of elements from that array. For example, if my array were
    > >of length 3 and it would look like: [1, 4, 2], I would want to calculate:
    > >1+4
    > >1+2
    > >1+4+2
    > >4+2

    >
    > >Now, I imagine I could do this somehow if I could generate the "power set" of
    > >an array containing the numbers from 0 to N-1 and using those "subsets"
    > >as indices.

    >
    > It would be interesting to try a Gray code. Each sum corresponds to a a
    > number and each number has only 1 bit changed from the previous number, so
    > you can keep the sum as you go, adding or subtracting only 1 element each
    > time. All you need is a quick way to determine which bit changes from Gray
    > code x to Gray code x+1, and whether it changed from 0 to 1 or 1 to 0.
    >
    > --
    > Alan Curry


    Sure. This has recursive structure, too. You can construct a n+1 bit
    gray code by starting with two copies A and B of the n-bit code.
    Prepend 0's to each bitstring in A to get 0A. In the same manner
    construct 1B. Then the n+1 bit code is the concatenation 0A +
    reverse(1B).

    It does not take much to figure out the bit position that flips in the
    resulting patterns is as follows:

    1-bit code: 0
    2-bit code: 0 1 0
    3-bit code: 0 1 0 2 0 1 0

    You can generate this sequence for the n-bit code with

    void gen(int n)
    {
    if (n == 0)
    printf("0 ");
    else {
    gen(n - 1);
    printf("%d ", n);
    gen(n - 1);
    }
    }

    Here is a toy program using this idea for powersets with an
    efficiently maintained "current set". Note this code skips printing
    of the empty set.

    #include <stdio.h>

    // Subset of the consecutive integers from 1 as doubly linked list.
    // Index 0 is the list header.
    #define N 100
    int prev[N + 1], next[N + 1], in[N + 1];

    // Flip one element into or out of the set
    void flip(int i)
    {
    if (in) {
    next[prev] = next;
    prev[next] = prev;
    in = 0;
    }
    else {
    prev[next[0]] = i;
    next = next[0];
    prev = 0;
    next[0] = i;
    in = 1;
    }
    // print the new set or whatever...
    printf("{ ");
    for (i = next[0]; i != 0; i = next)
    printf("%d ", i);
    printf("}\n");
    }

    void gen(int n)
    {
    if (n == 1)
    flip(1);
    else {
    gen(n - 1);
    flip(n);
    gen(n - 1);
    }
    }

    int main(void)
    {
    gen(4);
    return 0;
    }

    C:\>a
    { 1 }
    { 2 1 }
    { 2 }
    { 3 2 }
    { 1 3 2 }
    { 1 3 }
    { 3 }
    { 4 3 }
    { 1 4 3 }
    { 2 1 4 3 }
    { 2 4 3 }
    { 2 4 }
    { 1 2 4 }
    { 1 4 }
    { 4 }
     
    Gene, May 29, 2010
    #6
    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. Replies:
    8
    Views:
    373
    Mark Dickinson
    Apr 17, 2008
  2. Sean
    Replies:
    8
    Views:
    1,790
    Antoninus Twink
    Dec 9, 2009
  3. Michael Tsang
    Replies:
    32
    Views:
    1,127
    Richard Bos
    Mar 1, 2010
  4. Michael Tsang
    Replies:
    54
    Views:
    1,208
    Phil Carmody
    Mar 30, 2010
  5. sanket
    Replies:
    7
    Views:
    1,023
    Tsung
    Nov 3, 2011
Loading...

Share This Page