Subset sum problem
Implement a function/procedure/method/subroutine that takes a set/array/list/stream/table/collection of words with integer weights, and identifies a non-empty subset of them whose weights sum to zero (cf. the Dropbox Diet candidate screening exercise and the Subset sum problem Wikipedia article).
For example, for this set of weighted words, one solution would be the set of words {elysee, efferent, deploy, departure, centipede, bonnet, balm, archbishop}, because their respective weights of -326, 54, 44, 952, -658, 452, 397, and -915 sum to zero.
| word | weight |
|---|---|
| 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 |
Another solution would be the set of words {flatworm, gestapo, infra, isis, lindholm, plugging, smokescreen, speakeasy}, because their respective weights of 503, 915, -847, -982, 999, -266, 423, and -745 also sum to zero.
You may assume the weights range from -1000 to 1000. If there are multiple solutions, only one needs to be found. Use any algorithm you want and demonstrate it on a set of at least 30 weighted words with the results shown in a human readable form. Note that an implementation that depends on enumerating all possible subsets is likely to be infeasible.
C
<lang c>#include <stdio.h>
- include <stdlib.h>
- include <limits.h>
- include <string.h>
- define INTBITS (sizeof(int) * CHAR_BIT)
- define MAX_WEIGHT 1024
typedef struct { void* data; int weight; } item;
inline void setbit(int *x, int n) { x[n/INTBITS] |= (1 << (n % INTBITS)); }
inline int hasbit(int *x, int n) { return x[n/INTBITS] & (1 << (n % INTBITS)); }
int* subsum(item *x, int n) { int *buf, *from, *to, sums, alloc, i; int len = 1 + (n + (INTBITS - 1)) / INTBITS; /* 1 weight, rest bit field */ int rlen = len * sizeof(int); int *seen = calloc(sizeof(int), 2 * n * (MAX_WEIGHT / INTBITS) + 2);
buf = calloc(len, sizeof(int)); alloc = sums = 1;
for (i = 0; i < n; i++) { if (alloc < sums * 2) { alloc = sums * 2; buf = realloc(buf, rlen * alloc); }
for (from = to = buf + len * sums; from > buf; ) { from -= len; if (hasbit(seen, from[0] + x[i].weight + MAX_WEIGHT * n)) continue;
setbit(seen, from[0] + x[i].weight + MAX_WEIGHT * n);
memcpy(to, from, rlen); setbit(to + 1, i); sums++;
if (to[0] += x[i].weight) { to += len; continue; }
/* found it */ memcpy(buf, to, rlen); free(seen); return realloc(buf, rlen); } }
/* no solution */ free(seen); free(buf); return 0; }
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} };
int *ret, n = sizeof(em)/sizeof(em[0]);
if (!(ret = subsum(em, n))) { puts("no zero sums\n"); return 1; }
while (n--) if (hasbit(ret + 1, n)) printf("%2d| %5d %s\n", n, em[n].weight, (char*)em[n].data);
free(ret);
return 0; }</lang> output<lang>12| -326 elysee 11| 54 efferent
9| 44 deploy 7| 590 covariate 6| 362 cobol 5| -658 centipede 3| 452 bonnet 2| 397 balm 1| -915 archbishop</lang>
D
A very simple brute-force solution.
<lang d>import std.stdio, std.algorithm, std.string, std.typecons;
T[][] combinations(T)(T[] arr, int k) {
if (k == 0) return [[]];
T[][] result;
foreach (i, x; arr)
foreach (suffix; combinations(arr[i+1 .. $], k-1))
result ~= x ~ suffix;
return result;
}
void main() {
alias tuple T; /*immutable*/ auto items = [
T("alliance", -624), T("archbishop", -915), T("balm", 397), T("bonnet", 452), T("brute", 870), T("centipede", -658), T("cobol", 362), T("covariate", 590), T("departure", 952), T("deploy", 44), T("diophantine", 645), T("efferent", 54), T("elysee", -326), T("eradicate", 376), T("escritoire", 856), T("exorcism", -983), T("fiat", 170), T("filmy", -874), T("flatworm", 503), T("gestapo", 915), T("infra", -847), T("isis", -982), T("lindholm", 999), T("markham", 475), T("mincemeat", -880), T("moresby", 756), T("mycenae", 183), T("plugging", -266), T("smokescreen", 423), T("speakeasy", -745), T("vein", 813)];
foreach (n; 1 .. items.length)
foreach (comb; combinations(items, n))
if (reduce!q{ a + b[1] }(0, comb) == 0) {
const solution = map!q{ a[0] }(comb).join(", ");
writefln("A subset of length %d: %s", n, solution);
return;
}
writefln("No solution found.");
}</lang> Output:
A subset of length 2: archbishop, gestapo
Go
<lang go>package main
import "fmt"
type ww struct {
word string weight int
}
var input = []*ww{
{"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},
}
type sss struct {
subset []*ww sum int
}
func main() {
ps := []sssTemplate:Nil, 0 for _, i := range input { pl := len(ps) for j := 0; j < pl; j++ { subset := append([]*ww{i}, ps[j].subset...) sum := i.weight + ps[j].sum if sum == 0 { fmt.Println("this subset sums to 0:") for _, i := range subset { fmt.Println(*i) } return } ps = append(ps, sss{subset, sum}) } } fmt.Println("no subset sums to 0")
}</lang>
- Output:
this subset sums to 0:
{elysee -326}
{efferent 54}
{deploy 44}
{covariate 590}
{cobol 362}
{centipede -658}
{bonnet 452}
{balm 397}
{archbishop -915}
Icon and Unicon
<lang Icon>link printf,lists
procedure main()
BruteZeroSubset(string2table(
"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/"))
end
procedure BruteZeroSubset(words) # brute force 1 of each length
every n := 1 to *words do {
every t := tcomb(words,n) do { # generate combination
every (sum := 0) +:= words[!t] # sum combination
if sum = 0 then {
printf("A zero-sum subset of length %d : %s\n",n,list2string(sort(t)))
break next # found one
}
}
printf("No zero-sum subsets of length %d\n",n)
}
end
- helper procedures
procedure tcomb(T, i) #: Table (key) combinations
local K every put(K := [],key(T)) # list of keys every suspend lcomb(K,i) # return list combs
end
procedure list2string(L) #: format list as a string
every (s := "[ ") ||:= !L || " " # reformat as string return s || "]"
end
procedure string2table(s,d) #: format string "k1/v1/.../kn/vn" as table
T := table()
/d := "/"
s ? until pos(0) do
T[1(tab(find(d)),=d)] := numeric(1(tab(find(d)),=d))
return T
end</lang>
printf.icn provides formatting lists.icn provides lcomb for list combinations
Output:
No zero-sum subsets of length 1 A zero-sum subset of length 2 : [ archbishop gestapo ] A zero-sum subset of length 3 : [ centipede markham mycenae ] A zero-sum subset of length 4 : [ alliance balm deploy mycenae ] A zero-sum subset of length 5 : [ balm eradicate isis markham plugging ] A zero-sum subset of length 6 : [ archbishop balm escritoire exorcism fiat markham ] A zero-sum subset of length 7 : [ balm bonnet cobol fiat filmy isis markham ] A zero-sum subset of length 8 : [ balm bonnet cobol filmy markham mincemeat speakeasy vein ] A zero-sum subset of length 9 : [ alliance archbishop balm bonnet cobol lindholm markham mincemeat plugging ] A zero-sum subset of length 10 : [ archbishop balm bonnet cobol filmy gestapo markham mincemeat speakeasy vein ] A zero-sum subset of length 11 : [ alliance archbishop balm bonnet cobol deploy gestapo isis markham mincemeat moresby ] A zero-sum subset of length 12 : [ alliance archbishop balm bonnet cobol exorcism fiat lindholm markham mincemeat plugging vein ] A zero-sum subset of length 13 : [ alliance archbishop balm bonnet brute cobol deploy diophantine exorcism markham mincemeat plugging smokescreen ] A zero-sum subset of length 14 : [ alliance archbishop balm bonnet centipede cobol diophantine exorcism lindholm markham mincemeat mycenae plugging vein ] A zero-sum subset of length 15 : [ alliance archbishop balm bonnet cobol diophantine fiat gestapo isis markham mincemeat mycenae plugging speakeasy vein ] A zero-sum subset of length 16 : [ alliance archbishop balm bonnet brute cobol diophantine eradicate exorcism filmy infra lindholm markham mincemeat plugging vein ] A zero-sum subset of length 17 : [ alliance archbishop balm bonnet centipede cobol covariate deploy diophantine exorcism filmy lindholm markham mincemeat plugging smokescreen vein ] A zero-sum subset of length 18 : [ alliance archbishop balm bonnet centipede cobol diophantine eradicate escritoire exorcism filmy gestapo infra markham mincemeat moresby plugging vein ] A zero-sum subset of length 19 : [ alliance archbishop balm bonnet cobol diophantine efferent exorcism filmy flatworm gestapo infra isis lindholm markham mincemeat moresby plugging vein ] A zero-sum subset of length 20 : [ alliance archbishop balm bonnet centipede cobol deploy diophantine efferent escritoire exorcism fiat filmy gestapo isis lindholm markham mincemeat plugging vein ] A zero-sum subset of length 21 : [ alliance archbishop balm bonnet brute centipede cobol covariate deploy diophantine efferent elysee exorcism filmy gestapo infra markham mincemeat moresby plugging vein ] A zero-sum subset of length 22 : [ alliance archbishop balm bonnet centipede cobol deploy diophantine eradicate escritoire exorcism fiat filmy gestapo isis lindholm markham mincemeat plugging smokescreen speakeasy vein ] A zero-sum subset of length 23 : [ alliance archbishop balm bonnet brute centipede cobol covariate departure deploy diophantine exorcism filmy flatworm gestapo infra isis markham mincemeat moresby plugging speakeasy vein ] A zero-sum subset of length 24 : [ alliance archbishop balm bonnet brute centipede cobol departure deploy diophantine efferent escritoire exorcism filmy gestapo infra isis markham mincemeat moresby mycenae plugging speakeasy vein ] A zero-sum subset of length 25 : [ alliance archbishop balm bonnet brute centipede cobol covariate deploy diophantine efferent elysee eradicate exorcism filmy gestapo infra isis markham mincemeat moresby mycenae plugging smokescreen vein ] A zero-sum subset of length 26 : [ alliance archbishop balm bonnet centipede cobol covariate departure deploy diophantine efferent elysee eradicate escritoire exorcism fiat filmy gestapo infra isis lindholm markham mincemeat plugging speakeasy vein ] A zero-sum subset of length 27 : [ alliance archbishop balm bonnet brute centipede covariate departure deploy efferent elysee eradicate escritoire exorcism fiat filmy flatworm infra isis lindholm markham mincemeat moresby mycenae plugging smokescreen speakeasy ] No zero-sum subsets of length 28 No zero-sum subsets of length 29 No zero-sum subsets of length 30 No zero-sum subsets of length 31
Mathematica
<lang Mathematica>a = {{"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}};
result = Rest@Select[ Subsets[a, 7], (Total[#;; , 2] == 0) &]; Map[ (Print["A zero-sum subset of length ", Length[#], " : ", #;; , 1])& , result ]</lang>
A zero-sum subset of length 2 : {archbishop,gestapo}
A zero-sum subset of length 3 : {centipede,markham,mycenae}
A zero-sum subset of length 3 : {exorcism,fiat,vein}
A zero-sum subset of length 4 : {alliance,balm,deploy,mycenae}
A zero-sum subset of length 4 : {balm,efferent,filmy,smokescreen}
A zero-sum subset of length 4 : {bonnet,elysee,escritoire,isis}
A zero-sum subset of length 4 : {brute,centipede,efferent,plugging}
....
PicoLisp
<lang PicoLisp>(de *Words
(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) )</lang>
Minimal brute force solution: <lang PicoLisp>(load "@lib/simul.l") # For 'subsets'
(pick
'((N)
(find '((L) (=0 (sum cdr L)))
(subsets N *Words) ) )
(range 1 (length *Words)) )</lang>
Output:
-> ((archbishop . -915) (gestapo . 915))
Python
A brute force solution is enough.
<lang python>from itertools import combinations
words = [ ("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)]
for n in xrange(1, len(words)):
for comb in combinations(words, n):
if sum(c[1] for c in comb) == 0:
sol = ", ".join(r[0] for r in comb)
print "A subset of length %d: %s" % (n, sol)
break
else:
print "No subsets of length", n, "sum to zero."</lang>
Output:
No subsets of length 1 sum to zero. A subset of length 2: archbishop, gestapo A subset of length 3: centipede, markham, mycenae A subset of length 4: alliance, balm, deploy, mycenae A subset of length 5: alliance, brute, covariate, deploy, mincemeat A subset of length 6: alliance, archbishop, balm, deploy, gestapo, mycenae A subset of length 7: alliance, archbishop, bonnet, cobol, departure, exorcism, moresby A subset of length 8: alliance, archbishop, balm, bonnet, fiat, flatworm, isis, lindholm A subset of length 9: alliance, archbishop, balm, bonnet, brute, covariate, eradicate, mincemeat, plugging A subset of length 10: alliance, archbishop, balm, bonnet, brute, centipede, cobol, departure, deploy, mincemeat A subset of length 11: alliance, archbishop, balm, bonnet, brute, centipede, cobol, departure, infra, moresby, speakeasy A subset of length 12: alliance, archbishop, balm, bonnet, brute, centipede, cobol, covariate, diophantine, efferent, elysee, infra A subset of length 13: alliance, archbishop, balm, bonnet, brute, centipede, cobol, covariate, departure, efferent, eradicate, filmy, isis A subset of length 14: alliance, archbishop, balm, bonnet, brute, centipede, cobol, covariate, departure, deploy, elysee, filmy, markham, speakeasy A subset of length 15: alliance, archbishop, balm, bonnet, brute, centipede, cobol, covariate, departure, deploy, elysee, exorcism, flatworm, infra, mycenae A subset of length 16: alliance, archbishop, balm, bonnet, brute, centipede, cobol, covariate, departure, deploy, diophantine, elysee, exorcism, filmy, gestapo, infra A subset of length 17: alliance, archbishop, balm, bonnet, brute, centipede, cobol, covariate, departure, deploy, diophantine, exorcism, isis, mincemeat, mycenae, plugging, vein A subset of length 18: alliance, archbishop, balm, bonnet, brute, centipede, cobol, covariate, departure, deploy, diophantine, efferent, elysee, exorcism, filmy, isis, mycenae, vein A subset of length 19: alliance, archbishop, balm, bonnet, brute, centipede, cobol, covariate, departure, deploy, diophantine, efferent, elysee, eradicate, exorcism, fiat, infra, isis, smokescreen A subset of length 20: alliance, archbishop, balm, bonnet, brute, centipede, cobol, covariate, departure, deploy, diophantine, efferent, elysee, eradicate, exorcism, gestapo, infra, isis, smokescreen, speakeasy A subset of length 21: alliance, archbishop, balm, bonnet, brute, centipede, cobol, covariate, departure, deploy, diophantine, efferent, elysee, eradicate, exorcism, flatworm, infra, lindholm, mincemeat, plugging, speakeasy A subset of length 22: alliance, archbishop, balm, bonnet, brute, centipede, cobol, covariate, departure, deploy, diophantine, efferent, elysee, eradicate, escritoire, exorcism, fiat, filmy, flatworm, mincemeat, plugging, speakeasy A subset of length 23: alliance, archbishop, balm, bonnet, brute, centipede, cobol, covariate, departure, deploy, diophantine, efferent, elysee, eradicate, escritoire, exorcism, infra, isis, mincemeat, moresby, mycenae, smokescreen, speakeasy A subset of length 24: alliance, archbishop, balm, bonnet, brute, centipede, cobol, covariate, departure, deploy, diophantine, efferent, elysee, exorcism, filmy, gestapo, infra, markham, mincemeat, moresby, mycenae, plugging, smokescreen, speakeasy A subset of length 25: alliance, archbishop, balm, bonnet, brute, centipede, cobol, covariate, departure, deploy, diophantine, eradicate, exorcism, fiat, filmy, flatworm, infra, isis, lindholm, markham, mincemeat, moresby, mycenae, plugging, speakeasy A subset of length 26: alliance, archbishop, balm, bonnet, brute, centipede, cobol, covariate, departure, deploy, diophantine, elysee, eradicate, escritoire, exorcism, fiat, filmy, gestapo, infra, isis, markham, mincemeat, mycenae, plugging, speakeasy, vein A subset of length 27: alliance, archbishop, balm, bonnet, brute, centipede, covariate, departure, deploy, efferent, elysee, eradicate, escritoire, exorcism, fiat, filmy, flatworm, infra, isis, lindholm, markham, mincemeat, moresby, mycenae, plugging, smokescreen, speakeasy No subsets of length 28 sum to zero. No subsets of length 29 sum to zero. No subsets of length 30 sum to zero.
Ruby
a brute force solution: <lang ruby>weights = {
'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,
}
words = weights.keys 1.upto(words.length) do |n|
zerosum = words.combination(n).find do |subset|
subset.reduce(0) {|sum, word| sum += weights[word]} == 0
end
if zerosum.nil?
puts "no subsets of length #{n} sum to zero"
else
puts "a subset of length #{n} that sums to zero: #{zerosum}"
end
end</lang>
output:
no subsets of length 1 sum to zero a subset of length 2 that sums to zero: ["archbishop", "gestapo"] a subset of length 3 that sums to zero: ["centipede", "markham", "mycenae"] a subset of length 4 that sums to zero: ["alliance", "balm", "deploy", "mycenae"] a subset of length 5 that sums to zero: ["alliance", "brute", "covariate", "deploy", "mincemeat"] a subset of length 6 that sums to zero: ["alliance", "archbishop", "balm", "deploy", "gestapo", "mycenae"] a subset of length 7 that sums to zero: ["alliance", "archbishop", "bonnet", "cobol", "departure", "exorcism", "moresby"] a subset of length 8 that sums to zero: ["alliance", "archbishop", "balm", "bonnet", "fiat", "flatworm", "isis", "lindholm"] a subset of length 9 that sums to zero: ["alliance", "archbishop", "balm", "bonnet", "brute", "covariate", "eradicate", "mincemeat", "plugging"] a subset of length 10 that sums to zero: ["alliance", "archbishop", "balm", "bonnet", "brute", "centipede", "cobol", "departure", "deploy", "mincemeat"] a subset of length 11 that sums to zero: ["alliance", "archbishop", "balm", "bonnet", "brute", "centipede", "cobol", "departure", "infra", "moresby", "speakeasy"] a subset of length 12 that sums to zero: ["alliance", "archbishop", "balm", "bonnet", "brute", "centipede", "cobol", "covariate", "diophantine", "efferent", "elysee", "infra"] a subset of length 13 that sums to zero: ["alliance", "archbishop", "balm", "bonnet", "brute", "centipede", "cobol", "covariate", "departure", "efferent", "eradicate", "filmy", "isis"] a subset of length 14 that sums to zero: ["alliance", "archbishop", "balm", "bonnet", "brute", "centipede", "cobol", "covariate", "departure", "deploy", "elysee", "filmy", "markham", "speakeasy"] a subset of length 15 that sums to zero: ["alliance", "archbishop", "balm", "bonnet", "brute", "centipede", "cobol", "covariate", "departure", "deploy", "elysee", "exorcism", "flatworm", "infra", "mycenae"] a subset of length 16 that sums to zero: ["alliance", "archbishop", "balm", "bonnet", "brute", "centipede", "cobol", "covariate", "departure", "deploy", "diophantine", "elysee", "exorcism", "filmy", "gestapo", "infra"] a subset of length 17 that sums to zero: ["alliance", "archbishop", "balm", "bonnet", "brute", "centipede", "cobol", "covariate", "departure", "deploy", "diophantine", "exorcism", "isis", "mincemeat", "mycenae", "plugging", "vein"] a subset of length 18 that sums to zero: ["alliance", "archbishop", "balm", "bonnet", "brute", "centipede", "cobol", "covariate", "departure", "deploy", "diophantine", "efferent", "elysee", "exorcism", "filmy", "isis", "mycenae", "vein"] a subset of length 19 that sums to zero: ["alliance", "archbishop", "balm", "bonnet", "brute", "centipede", "cobol", "covariate", "departure", "deploy", "diophantine", "efferent", "elysee", "eradicate", "exorcism", "fiat", "infra", "isis", "smokescreen"] a subset of length 20 that sums to zero: ["alliance", "archbishop", "balm", "bonnet", "brute", "centipede", "cobol", "covariate", "departure", "deploy", "diophantine", "efferent", "elysee", "eradicate", "exorcism", "gestapo", "infra", "isis", "smokescreen", "speakeasy"] a subset of length 21 that sums to zero: ["alliance", "archbishop", "balm", "bonnet", "brute", "centipede", "cobol", "covariate", "departure", "deploy", "diophantine", "efferent", "elysee", "eradicate", "exorcism", "flatworm", "infra", "lindholm", "mincemeat", "plugging", "speakeasy"] a subset of length 22 that sums to zero: ["alliance", "archbishop", "balm", "bonnet", "brute", "centipede", "cobol", "covariate", "departure", "deploy", "diophantine", "efferent", "elysee", "eradicate", "escritoire", "exorcism", "fiat", "filmy", "flatworm", "mincemeat", "plugging", "speakeasy"] a subset of length 23 that sums to zero: ["alliance", "archbishop", "balm", "bonnet", "brute", "centipede", "cobol", "covariate", "departure", "deploy", "diophantine", "efferent", "elysee", "eradicate", "escritoire", "exorcism", "infra", "isis", "mincemeat", "moresby", "mycenae", "smokescreen", "speakeasy"] a subset of length 24 that sums to zero: ["alliance", "archbishop", "balm", "bonnet", "brute", "centipede", "cobol", "covariate", "departure", "deploy", "diophantine", "efferent", "elysee", "exorcism", "filmy", "gestapo", "infra", "markham", "mincemeat", "moresby", "mycenae", "plugging", "smokescreen", "speakeasy"] a subset of length 25 that sums to zero: ["alliance", "archbishop", "balm", "bonnet", "brute", "centipede", "cobol", "covariate", "departure", "deploy", "diophantine", "eradicate", "exorcism", "fiat", "filmy", "flatworm", "infra", "isis", "lindholm", "markham", "mincemeat", "moresby", "mycenae", "plugging", "speakeasy"] a subset of length 26 that sums to zero: ["alliance", "archbishop", "balm", "bonnet", "brute", "centipede", "cobol", "covariate", "departure", "deploy", "diophantine", "elysee", "eradicate", "escritoire", "exorcism", "fiat", "filmy", "gestapo", "infra", "isis", "markham", "mincemeat", "mycenae", "plugging", "speakeasy", "vein"] a subset of length 27 that sums to zero: ["alliance", "archbishop", "balm", "bonnet", "brute", "centipede", "covariate", "departure", "deploy", "efferent", "elysee", "eradicate", "escritoire", "exorcism", "fiat", "filmy", "flatworm", "infra", "isis", "lindholm", "markham", "mincemeat", "moresby", "mycenae", "plugging", "smokescreen", "speakeasy"] no subsets of length 28 sum to zero no subsets of length 29 sum to zero no subsets of length 30 sum to zero no subsets of length 31 sum to zero
Tcl
As it turns out that the problem space has small subsets that sum to zero, it is more efficient to enumerate subsets in order of their size rather than doing a simple combination search. This is not true of all possible input data sets though; the problem is known to be NP-complete after all. <lang tcl>proc subsetsOfSize {set size} {
if {$size <= 0} {
return
} elseif {$size == 1} {
foreach elem $set {lappend result [list $elem]}
} else {
incr size [set i -1] foreach elem $set { foreach sub [subsetsOfSize [lreplace $set [incr i] $i] $size] { lappend result [lappend sub $elem] } }
} return $result
} proc searchForSubset {wordweights {minsize 1}} {
set words [dict keys $wordweights]
for {set i $minsize} {$i < [llength $words]} {incr i} {
foreach subset [subsetsOfSize $words $i] { set w 0 foreach elem $subset {incr w [dict get $wordweights $elem]} if {!$w} {return $subset} }
} # Nothing was found return -code error "no subset sums to zero"
}</lang> Demonstrating: <lang tcl>set wordweights {
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
} set zsss [searchForSubset $wordweights] puts "Found zero-summing subset: [join [lsort $zsss] {, }]"</lang> Output:
Found zero-summing subset: archbishop, gestapo
Ursala
This solution scans the set sequentially while maintaining a record of all distinct sums obtainable by words encountered thus far, and stops when a zero sum is found. <lang Ursala>#import std
- import int
weights =
{
'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}
nullset = ~&nZFihmPB+ =><> ~&ng?r\~&r ^TnK2hS\~&r ^C/~&lmPlNCX *D ^A/sum@lmPrnPX ~&lrmPC
- cast %zm
main = nullset weights</lang>
The name of the function that takes the weighted set is nullset. It manipulates a partial result represented as a list of pairs, each containing a subset of weighted words and the sum of their weights. Here is a rough translation:
=><>fold right combinator with the empty list as the vacuuous case~&ng?r\~&rIf the partial result contains a zero sum, return it.^TnK2hS\~&rConcatenate the partial result with the new list of subsets (computed as follows) and delete duplicate sums.^C/~&lmPlNCXCons a singleton subset containing the next word to the partial results.*DDistribute the next word in the set to the partial results and do the following to each.sum@lmPrnPXAdd the weight of the new word to the existing sum.~&lrmPCCons the new word to the list of existing ones.~&nZFihmPB+To conclude, search for a result with a zero sum, if any, and return its associated subset of weighted words.
output:
< 'flatworm': 503, 'gestapo': 915, 'infra': -847, 'isis': -982, 'lindholm': 999, 'plugging': -266, 'smokescreen': 423, 'speakeasy': -745>