Power set implementation

[ar0]

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.

 

[Ben Bacarisse]

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.

 

[ar0]

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.

 

[Gene]

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:\>

 

[Alan Curry]

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.

 

[Gene]

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.

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 }