in [Theory]

Prev: Sat solver game
Next: SMV Help
From: ar0 on 28 May 2010 15:09 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.
From: Ben Bacarisse on 28 May 2010 15:34 noone (a)nospam.invalid (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.
From: ar0 on 28 May 2010 16:12 In comp.lang.c Ben Bacarisse <ben.usenet (a)bsb.me.uk> 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.
From: Gene on 29 May 2010 15:34 On May 28, 3:09 pm, no... (a)nospam.invalid (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[i]); 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:\>
From: Alan Curry on 29 May 2010 15:56
In article <htp4d4$qff$1 (a)surz18.uni-marburg.de>,ar0 <noone (a)nospam.invalid> 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 |