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.
Ada
<lang Ada>with Ada.Text_IO; use Ada.Text_IO; with Ada.Strings.Unbounded; use Ada.Strings.Unbounded; procedure SubsetSum is
function "+"(S:String) return Unbounded_String renames To_Unbounded_String;
type Point is record
str : Unbounded_String;
num : Integer;
end record;
type Points is array (Natural range <>) of Point;
type Indices is array (Natural range <>) of Natural;
procedure Print (data : Points; list : Indices; len : Positive) is begin
Put (len'Img & ":");
for i in 0..len-1 loop
Put (" "& To_String(data(list(i)).str));
end loop; New_Line;
end Print;
function Check (data : Points; list : Indices; len : Positive) return Boolean is
sum : Integer := 0;
begin
for i in 0..len-1 loop sum := sum + data(list(i)).num; end loop;
return sum = 0;
end Check;
procedure Next (list : in out Indices; n, r : Positive ) is begin
for i in reverse 0..r-1 loop
if list(i)/=i+n-r then list(i):=list(i)+1;
for j in i+1..r-1 loop list(j):=list(j-1)+1; end loop; exit;
end if;
end loop;
end Next;
data : constant Points := ((+"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));
list, last : Indices (data'Range);
begin
for len in 2..data'Length loop
for i in 0..len-1 loop list(i):=i; end loop;
loop
if Check(data, list, len) then Print(data, list, len); exit; end if;
last := list;
Next(list, data'Length, len);
exit when last=list;
end loop;
end loop;
end SubsetSum;</lang>
- Output:
2: archbishop gestapo 3: centipede markham mycenae 4: alliance balm deploy mycenae 5: alliance brute covariate deploy mincemeat 6: alliance archbishop balm deploy gestapo mycenae 7: alliance archbishop bonnet cobol departure exorcism moresby 8: alliance archbishop balm bonnet fiat flatworm isis lindholm 9: alliance archbishop balm bonnet brute covariate eradicate mincemeat plugging 10: alliance archbishop balm bonnet brute centipede cobol departure deploy mincemeat 11: alliance archbishop balm bonnet brute centipede cobol departure infra moresby speakeasy 12: alliance archbishop balm bonnet brute centipede cobol covariate diophantine efferent elysee infra 13: alliance archbishop balm bonnet brute centipede cobol covariate departure efferent eradicate filmy isis 14: alliance archbishop balm bonnet brute centipede cobol covariate departure deploy elysee filmy markham speakeasy 15: alliance archbishop balm bonnet brute centipede cobol covariate departure deploy elysee exorcism flatworm infra mycenae 16: alliance archbishop balm bonnet brute centipede cobol covariate departure deploy diophantine elysee exorcism filmy gestapo infra 17: alliance archbishop balm bonnet brute centipede cobol covariate departure deploy diophantine exorcism isis mincemeat mycenae plugging vein 18: alliance archbishop balm bonnet brute centipede cobol covariate departure deploy diophantine efferent elysee exorcism filmy isis mycenae vein 19: alliance archbishop balm bonnet brute centipede cobol covariate departure deploy diophantine efferent elysee eradicate exorcism fiat infra isis smokescreen 20: alliance archbishop balm bonnet brute centipede cobol covariate departure deploy diophantine efferent elysee eradicate exorcism gestapo infra isis smokescreen speakeasy 21: alliance archbishop balm bonnet brute centipede cobol covariate departure deploy diophantine efferent elysee eradicate exorcism flatworm infra lindholm mincemeat plugging speakeasy 22: alliance archbishop balm bonnet brute centipede cobol covariate departure deploy diophantine efferent elysee eradicate escritoire exorcism fiat filmy flatworm mincemeat plugging speakeasy 23: alliance archbishop balm bonnet brute centipede cobol covariate departure deploy diophantine efferent elysee eradicate escritoire exorcism infra isis mincemeat moresby mycenae smokescreen speakeasy 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 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 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 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
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 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 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) {
writefln("A subset of length %d: %s", n,
//comb.map!q{ a[0] }.join(", "));
comb.map!q{ cast()a[0] }.join(", "));
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.
REXX
This REXX solution isn't limited to integers. <lang rexx>/*REXX pgm finds some non-null subsets of a weighted list whose sum=0. */
arg target stop . /*get arguments from command line*/ if target== then target=0 /*No TARGET given? Use default.*/ if stop== then stop=1 /*No max sols given? Use default.*/
pairs= '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'
solutions=0; do size=1 until pairs=
parse var pairs @.size #.size pairs
end /*size*/; #.0=target
do chunk=1 for size
list=combN(size,chunk)
do j=1 for words(list)
call tell translate(word(list,j),,',')
end /*j*/
end /*chunk*/
if solutions==0 then solutions='no' call sayr 'Found' solutions "subsets whose summed weights =" target exit
/*─────────────────────────────────────tell subroutine──────────────────*/ tell: arg indices,names,weights; solutions=solutions+1; w=words(indices) header='found a subset whose summed weights =' target", the names are:" if solutions==1 then call sayr center(header,79,'-')
do i=1 for w
_=word(indices,i)
names=names @._
/*weights in this one───> */ /* names=names @._ '{'#._"}" ¬¬¬¬¬¬ */
end
call sayr '['w" names]" space(names) if solutions>=stop &,
stop\==0 then do
call sayr 'Stopped after finding' solutions "subsets."
exit
end
return
sayr: say arg(1); call lineout 'OUTPUT.TXT',arg(1) /*write to file*/; return
/*─────────────────────────────────────combN subroutine─────────────────*/ combN: procedure expose #.; parse arg x,y,L /*X items taken Y at a time.*/
do k=1 for y; z.k=k; end /*build combination table. */
do j=1
if j\==1 then if .comb.(y) then iterate
if z.1>x then leave
k1=z.1; s=#.k1
do k=2 for y-1; _=z.k; s=s+#._; end /*sum the weights.*/
if s\==#.0 then iterate /*element #.0 is the target sum.*/
c=k1
do k=2 for y-1; c=c','z.k; end /*build name list.*/
L=L c
end /*j*/
return L
.comb.: parse arg q; if q==0 then return 1; z.q=z.q+1 if z.1>x then return 0 if z.q>x then if .comb.(q-1) then return 1
else do m=q+1 to y
_=m-1; z.m=z._+1; if z.m>x then return 1
end /*m*/
return 0</lang>
Output when using the input of: 0 100
(The above arguments set the target sum to zero and limits finding the solutions to one hundred.)
This output was produced with a version of the REXX program that included the weights with the name.
The REXX statement used was: /*weights in this one───> */ names=names @._ '{'#._"}"
------------found a subset whose sum of weights = 0, the names are:------------
[2 names] archbishop {-915} gestapo {915}
[3 names] centipede {-658} markham {475} mycenae {183}
[3 names] exorcism {-983} fiat {170} vein {813}
[4 names] alliance {-624} balm {397} deploy {44} mycenae {183}
[4 names] balm {397} efferent {54} filmy {-874} smokescreen {423}
[4 names] bonnet {452} elysee {-326} escritoire {856} isis {-982}
[4 names] brute {870} centipede {-658} efferent {54} plugging {-266}
[4 names] centipede {-658} covariate {590} gestapo {915} infra {-847}
[4 names] centipede {-658} covariate {590} speakeasy {-745} vein {813}
[4 names] deploy {44} exorcism {-983} moresby {756} mycenae {183}
[4 names] eradicate {376} isis {-982} mycenae {183} smokescreen {423}
[4 names] exorcism {-983} gestapo {915} speakeasy {-745} vein {813}
[5 names] alliance {-624} brute {870} covariate {590} deploy {44} mincemeat {-880}
[5 names] alliance {-624} departure {952} deploy {44} infra {-847} markham {475}
[5 names] alliance {-624} departure {952} eradicate {376} fiat {170} filmy {-874}
[5 names] alliance {-624} eradicate {376} exorcism {-983} markham {475} moresby {756}
... the majority of the output has been deleted ...
Stopped after finding 100 subsets.
Output when using the input of: 0 100
(The above arguments set the target sum to zero and limits finding the solutions to one hundred.)
------------found a subset whose sum of weights = 0, the names are:------------ [2 names] archbishop gestapo [3 names] centipede markham mycenae [3 names] exorcism fiat vein [4 names] alliance balm deploy mycenae [4 names] balm efferent filmy smokescreen [4 names] bonnet elysee escritoire isis [4 names] brute centipede efferent plugging [4 names] centipede covariate gestapo infra [4 names] centipede covariate speakeasy vein [4 names] deploy exorcism moresby mycenae [4 names] eradicate isis mycenae smokescreen [4 names] exorcism gestapo speakeasy vein [5 names] alliance brute covariate deploy mincemeat [5 names] alliance departure deploy infra markham [5 names] alliance departure eradicate fiat filmy [5 names] alliance eradicate exorcism markham moresby [5 names] alliance infra markham mycenae vein [5 names] archbishop balm diophantine escritoire exorcism [5 names] archbishop bonnet covariate escritoire exorcism [5 names] archbishop centipede covariate fiat vein [5 names] archbishop centipede gestapo markham mycenae [5 names] archbishop cobol departure filmy markham [5 names] archbishop cobol elysee eradicate flatworm [5 names] archbishop departure efferent infra moresby [5 names] archbishop escritoire mincemeat moresby mycenae [5 names] archbishop exorcism fiat gestapo vein [5 names] archbishop isis lindholm markham smokescreen [5 names] balm brute covariate exorcism filmy [5 names] balm centipede departure efferent speakeasy [5 names] balm centipede departure filmy mycenae [5 names] balm cobol efferent exorcism fiat [5 names] balm eradicate isis markham plugging [5 names] balm escritoire exorcism markham speakeasy [5 names] bonnet brute centipede infra mycenae [5 names] bonnet centipede cobol elysee fiat [5 names] bonnet centipede efferent infra lindholm [5 names] bonnet centipede eradicate exorcism vein [5 names] bonnet deploy elysee exorcism vein [5 names] bonnet eradicate mycenae plugging speakeasy [5 names] brute deploy gestapo infra isis [5 names] brute deploy infra mincemeat vein [5 names] brute deploy isis speakeasy vein [5 names] brute eradicate filmy infra markham [5 names] centipede cobol escritoire exorcism smokescreen [5 names] centipede departure deploy diophantine exorcism [5 names] centipede deploy escritoire flatworm speakeasy [5 names] centipede diophantine exorcism mycenae vein [5 names] centipede escritoire gestapo infra plugging [5 names] centipede escritoire plugging speakeasy vein [5 names] cobol diophantine escritoire exorcism mincemeat [5 names] cobol escritoire filmy flatworm infra [5 names] covariate departure exorcism isis smokescreen [5 names] covariate eradicate exorcism isis lindholm [5 names] covariate isis markham mycenae plugging [5 names] departure efferent escritoire isis mincemeat [5 names] departure elysee lindholm mincemeat speakeasy [5 names] departure fiat flatworm mincemeat speakeasy [5 names] deploy filmy isis lindholm vein [5 names] escritoire filmy markham mincemeat smokescreen [5 names] fiat infra lindholm smokescreen speakeasy [6 names] alliance archbishop balm deploy gestapo mycenae [6 names] alliance archbishop departure isis moresby vein [6 names] alliance balm bonnet filmy gestapo plugging [6 names] alliance balm brute efferent mincemeat mycenae [6 names] alliance balm brute flatworm mincemeat plugging [6 names] alliance balm centipede departure gestapo isis [6 names] alliance balm centipede departure mincemeat vein [6 names] alliance balm departure elysee filmy markham [6 names] alliance balm escritoire fiat isis mycenae [6 names] alliance bonnet brute elysee infra markham [6 names] alliance bonnet centipede isis lindholm vein [6 names] alliance brute centipede cobol elysee eradicate [6 names] alliance brute centipede flatworm infra moresby [6 names] alliance brute covariate infra moresby speakeasy [6 names] alliance brute deploy efferent flatworm infra [6 names] alliance brute deploy escritoire mincemeat plugging [6 names] alliance brute efferent infra plugging vein [6 names] alliance centipede deploy diophantine fiat smokescreen [6 names] alliance cobol covariate deploy infra markham [6 names] alliance cobol covariate eradicate fiat filmy [6 names] alliance cobol departure infra plugging smokescreen [6 names] alliance cobol deploy gestapo mincemeat mycenae [6 names] alliance cobol eradicate infra lindholm plugging [6 names] alliance cobol fiat infra moresby mycenae [6 names] alliance cobol flatworm infra mycenae smokescreen [6 names] alliance covariate filmy infra lindholm moresby [6 names] alliance departure diophantine escritoire infra isis [6 names] alliance departure eradicate filmy gestapo speakeasy [6 names] alliance departure exorcism flatworm infra lindholm [6 names] alliance diophantine efferent eradicate filmy smokescreen [6 names] alliance diophantine elysee exorcism markham vein [6 names] alliance diophantine elysee filmy moresby smokescreen [6 names] alliance efferent eradicate moresby mycenae speakeasy [6 names] alliance eradicate flatworm moresby plugging speakeasy [6 names] archbishop balm centipede departure efferent fiat [6 names] archbishop balm centipede deploy eradicate moresby [6 names] archbishop balm centipede elysee flatworm lindholm [6 names] archbishop balm covariate efferent escritoire isis [6 names] archbishop balm covariate elysee lindholm speakeasy [6 names] archbishop balm covariate fiat flatworm speakeasy Stopped after finding 100 subsets.
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>