Subset sum problem: Difference between revisions
Content deleted Content added
Updated D entry |
→{{header|C}}: for listing all combos |
||
Line 242: | Line 242: | ||
11 | 54 efferent |
11 | 54 efferent |
||
12 | -326 elysee |
12 | -326 elysee |
||
Code for listing ''all'' zero sum sets. It's pretty fast for this example, takes seconds even if printing all 300k+ combinations is enabled. |
|||
<lang c>#include <stdio.h> |
|||
#include <stdlib.h> |
|||
typedef struct { char* data; int weight; } item; |
|||
typedef struct { int sum; unsigned int mask; } sum_t; |
|||
item em[] = { |
|||
{"alliance", -624}, {"archbishop", -915}, {"balm", 397}, |
|||
{"bonnet", 452}, {"brute", 870}, {"centipede", -658}, |
|||
{"cobol", 362}, {"covariate", 590}, {"departure", 952}, |
|||
{"deploy", 44}, {"diophantine", 645}, {"efferent", 54}, |
|||
{"elysee", -326}, {"eradicate", 376}, {"escritoire", 856}, |
|||
{"exorcism", -983}, {"fiat", 170}, {"filmy", -874}, |
|||
{"flatworm", 503}, {"gestapo", 915}, {"infra", -847}, |
|||
{"isis", -982}, {"lindholm", 999}, {"markham", 475}, |
|||
{"mincemeat", -880}, {"moresby", 756}, {"mycenae", 183}, |
|||
{"plugging", -266}, {"smokescreen", 423}, {"speakeasy", -745}, |
|||
{"vein", 813} |
|||
}; |
|||
#define N (sizeof(em)/sizeof(em[0])) |
|||
int cmp_sums(const void *a, const void *b) |
|||
{ |
|||
return ((sum_t*)a)->sum - ((sum_t*)b)->sum; |
|||
} |
|||
sum_t *mksums(item *p, int n, int shift) |
|||
{ |
|||
sum_t *r = malloc(sizeof(*r) * (1 << n)); |
|||
int i; |
|||
for (i = 0; i < n; i++) |
|||
r[1<<i].sum = p[i].weight; |
|||
r[0].mask = 0, r[0].sum = 0; |
|||
for (i = 1; i < 1<<n; i++) { |
|||
unsigned int b = i & -(int)i; |
|||
r[i].mask = i << shift; |
|||
r[i].sum = r[i & ~b].sum + r[b].sum; |
|||
} |
|||
qsort(r, 1<<n, sizeof(*r), cmp_sums); |
|||
return r; |
|||
} |
|||
int main(void) |
|||
{ |
|||
int n1 = N / 2, n2 = N - n1, i, j, i1, j1, sols = 0; |
|||
#define SHOW_ALL 1 |
|||
#define N1 (1 << n1) |
|||
#define N2 (1 << n2) |
|||
sum_t *l = mksums(em, n1, 0), |
|||
*r = mksums(em + n1, n2, n1); |
|||
void showmask(unsigned int mask) |
|||
{ |
|||
unsigned int m; |
|||
for (m = 0; (1<<m) <= mask; m++) { |
|||
if (mask & (1<<m)) |
|||
printf("(%s,%d) ", em[m].data, em[m].weight); |
|||
} |
|||
if (mask) puts(""); |
|||
} |
|||
int printlist() { |
|||
int x, y, s = (i1 - i) * (j - j1); |
|||
if (!l[i].sum) s--; |
|||
if (SHOW_ALL) |
|||
for (x = i; x < i1; x++) |
|||
for (y = j; y > j1; y--) |
|||
showmask(l[x].mask | r[y].mask); |
|||
return s; |
|||
} |
|||
i = 0, j = N2 - 1; |
|||
while (1) { |
|||
while (l[i].sum + r[j].sum) { |
|||
while (i < N1 && l[i].sum + r[j].sum < 0) i++; |
|||
while (j >= 0 && l[i].sum + r[j].sum > 0) j--; |
|||
if (i >= N1 || j < 0) break; |
|||
} |
|||
if (i >= N1 || j < 0) break; |
|||
for (i1 = i + 1; i1 < N1 && l[i1].sum == l[i].sum; i1++); |
|||
for (j1 = j - 1; j1 >= 0 && r[j1].sum == r[j].sum; j1--); |
|||
sols += printlist(); |
|||
i = i1, j = j1; |
|||
} |
|||
printf("zero sums: %d\n", sols); |
|||
return 0; |
|||
}</lang> |
|||
=={{header|D}}== |
=={{header|D}}== |