|
<lang c>#include <stdio.h>
#include <stdlib.h>
#include <stdint.h>
#include <string.h>
typedef struct { void* data; int weight; } item;
char *word;
int weight;
} item_t;
item_t items[] = {
uint64_t subsum(item *x, int n)
{"alliance", -624},
{
{"archbishop", -915},
int i, j, w, from, to, step, pos = 0, neg = 0;
{"balm", 397},
uint64_t bit, *buf;
{"bonnet", 452},
{"brute", 870},
for (i = 0; i < n; i++)
{"centipede", -658},
if (x[i].weight >= 0) pos += x[i].weight;
{"cobol", 362},
else neg += x[i].weight;
{"covariate", 590},
{"departure", 952},
buf = calloc(pos - neg + 1, sizeof(uint64_t));
{"deploy", 44},
buf -= neg;
{"diophantine", 645},
{"efferent", 54},
for (i = 0; i < n; i++) {
{"elysee", -326},
w = x[i].weight;
{"eradicate", 376},
bit = (uint64_t)1 << i;
{"escritoire", 856},
{"exorcism", -983},
if (w < 0) from = neg, to = pos + 1, step = 1;
else from = pos {"fiat", to = neg - 1, step = -1; 170},
{"filmy", -874},
{"flatworm", 503},
for (j = from; j != to; j += step)
{"gestapo", 915},
if (buf[j]) buf[j + w] = buf[j] | bit;
{"infra", -847},
buf[w] = bit;
{"isis", -982},
{"lindholm", 999},
if (buf[0]) break;
{"markham", 475},
}
{"mincemeat", -880},
{"moresby", 756},
bit = buf[0];
{"mycenae", 183},
free(buf + neg);
{"plugging", -266},
{"smokescreen", 423},
return bit;
{"speakeasy", -745},
}
{"vein", 813},
int main(void)
{
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}
};
uint64_t i, v, ret = subsum(em, sizeof(em)/sizeof(em[0]));
if (!ret) {
puts("no zero sums\n");
return 1;
}
puts("Found zero sum:");
for (i = 0; i < 64; i++) {
v = (uint64_t)1 << i;
if (ret & v)
printf("%2llu | %5d %s\n", i, em[i].weight, (char*)em[i].data);
}
return 0;
}</lang>{{out}}
Found zero sum:
1 | -915 archbishop
2 | 397 balm
3 | 452 bonnet
5 | -658 centipede
8 | 952 departure
9 | 44 deploy
11 | 54 efferent
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 { const 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 n = sizeof (items) / sizeof (item_t);
int cmp_sums(const void *a, const void *b)
int *path;
{
return ((const sum_t*)a)->sum - ((const sum_t*)b)->sum;
}
sum_tvoid subsum *mksums(const item *p, int ni, int shiftweight) {
int j;
{
if (i && !weight) {
sum_t *r = malloc(sizeof(*r) * (1 << n));
for (j = 0; j < i; j++) {
int i;
item_t item = items[path[j]];
for (i = 0; i < n; i++)
printf("%s%s", j ? " " : "", items[path[j]].word);
r[1<<i].sum = p[i].weight;
}
printf("\n");
r[0].mask = 0, r[0].sum = 0;
}
for (ij = 1;i ? path[i <- 1] + 1: 0; j << n; ij++) {
unsigned int b = i & -(int) path[i] = j;
subsum(i + 1, weight + items[j].weight);
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) {
path = malloc(n * sizeof (int));
{
subsum(0, 0);
int n1 = N / 2, n2 = N - n1, i, j, i1, j1, sols = 0;
return 0;
#define SHOW_ALL 1
}</lang>
#define N1 (1 << n1)
#define N2 (1 << n2)
sum_t *l = mksums(em, n1, 0),
*r = mksums(em + n1, n2, n1);
{{output}}<pre>alliance archbishop balm bonnet brute centipede cobol covariate departure deploy diophantine efferent elysee eradicate escritoire exorcism fiat filmy flatworm mincemeat plugging speakeasy
void showmask(unsigned int mask)
...</pre>
{
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}}==
|