Prev: Sat solver game
Next: SMV Help
From: Gene on 29 May 2010 17:17
On May 29, 3:56 pm, pac...(a)kosh.dhis.org (Alan Curry) wrote:
> In article <htp4d4$qf...(a)surz18.uni-marburg.de>,
>
> ar0 <no...(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

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[i]) {
next[prev[i]] = next[i];
prev[next[i]] = prev[i];
in[i] = 0;
}
else {
prev[next[0]] = i;
next[i] = next[0];
prev[i] = 0;
next[0] = i;
in[i] = 1;
}
// print the new set or whatever...
printf("{ ");
for (i = next[0]; i != 0; i = next[i])
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 }
From: Virgil on 29 May 2010 17:48
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.

For an array with n entries, consider the binary numbers from 1 to 2^n,
and for each such number, pick only those binary numbers which have at
least two non-zero bits, then include the kth position in a sum if and
only if that binary number has the kth bit equal to 1, and exclude it if
the kth bit is equal to to 0.

Example with [a,b,c]
binary 2 bits? sum
------ ------- ---
000 no
001 no
010 no
011 yes a + b
100 no
101 yes a + c
110 yes b + c
111 yes a + b + c
From: Virgil on 29 May 2010 18:29
In article <Virgil-CAE0DF.15481429052010(a)bignews.usenetmonster.com>,
Virgil <Virgil(a)home.esc> wrote:

> 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.
>
> For an array with n entries, consider the binary numbers from 1 to 2^n,
> and for each such number, pick only those binary numbers which have at
> least two non-zero bits, then include the kth position in a sum if and
> only if that binary number has the kth bit equal to 1, and exclude it if
> the kth bit is equal to to 0.
>
> Example with [a,b,c]
> binary 2 bits? sum
> ------ ------- ---
> 000 no
> 001 no
> 010 no
> 011 yes a + b
> 100 no
> 101 yes a + c
> 110 yes b + c
> 111 yes a + b + c

NOTE: for any powerset operation on a finite set of n objects, there are
2^n subsets, and if the original set is formatted is an n-tuple, the
binary integers from 0 to 2^n can easily be used to represent its
subsets with the binary 1's representing members of the subset and 0's
representing non-members.
First  |  Prev  | 
Pages: 1 2
Prev: Sat solver game
Next: SMV Help