Subset sum problem: Difference between revisions
m
→{{header|Wren}}: Minor tidy
m (→{{header|REXX}}: added/changed comments and whitespace, elide the timings.) |
m (→{{header|Wren}}: Minor tidy) |
||
(25 intermediate revisions by 15 users not shown) | |||
Line 1:
{{draft task|Discrete math}}
;Task:
Line 6 ⟶ 5:
;For example:
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.
:::::: {| style="text-align: left; width: 40%;" border="5" cellpadding="2" cellspacing="2"
|+ Table of weighted words
|- style="background-color: rgb(255, 204, 255);"
Line 87 ⟶ 91:
Note that an implementation that depends on enumerating all possible subsets is likely to be infeasible.
<br><br>
=={{header|11l}}==
{{trans|Python}}
<syntaxhighlight lang="11l">V words = [
‘alliance’ = -624, ‘archbishop’ = -925, ‘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
]
V neg = 0
V pos = 0
L(w, v) words
I v > 0
pos += v
E
neg += v
V sums = [[String]()] * (pos - neg + 1)
L(w, v) words
V s = copy(sums)
I s[v - neg].empty
s[v - neg] = [w]
L(w2) sums
V i = L.index
I !w2.empty & s[i + v].empty
s[i + v] = w2 [+] [w]
sums = s
I !s[-neg].empty
L(x) s[-neg]
print(x‘ ’words[x])
L.break</syntaxhighlight>
{{out}}
<pre>
alliance -624
archbishop -925
balm 397
bonnet 452
centipede -658
cobol 362
departure 952
deploy 44
</pre>
=={{header|Action!}}==
<syntaxhighlight lang="action!">DEFINE PTR="CARD"
DEFINE PAIR_SIZE="4"
TYPE Pair=[PTR word INT weight]
BYTE ARRAY pairs(200)
BYTE count=[0]
PTR FUNC GetPairAddr(INT index)
RETURN (pairs+index*PAIR_SIZE)
PROC PrintWords(BYTE ARRAY indices BYTE len)
Pair POINTER p
BYTE i
FOR i=0 TO len-1
DO
IF i>0 THEN Put(' ) FI
p=GetPairAddr(indices(i))
Print(p.word)
OD
PutE()
RETURN
PROC Append(CHAR ARRAY wrd INT wght)
Pair POINTER dst
dst=GetPairAddr(count)
dst.word=wrd
dst.weight=wght
count==+1
RETURN
PROC Init()
Append("alliance",-624) Append("archbishop",-915)
Append("balm",397) Append("bonnet",452)
Append("brute",870) Append("centipede",-658)
Append("cobol",362) Append("covariate",590)
Append("departure",952) Append("deploy",44)
Append("diophantine",645) Append("efferent",54)
Append("elysee",-326) Append("eradicate",376)
Append("escritoire",856) Append("exorcism",-983)
Append("fiat",170) Append("filmy",-874)
Append("flatworm",503) Append("gestapo",915)
Append("infra",-847) Append("isis",-982)
Append("lindholm",999) Append("markham",475)
Append("mincemeat",-880) Append("moresby",756)
Append("mycenae",183) Append("plugging",-266)
Append("smokescreen",423) Append("speakeasy",-745)
Append("vein",813)
RETURN
INT FUNC Sum(BYTE ARRAY indices BYTE len)
Pair POINTER p
INT sum
BYTE i
sum=0
FOR i=0 TO len-1
DO
p=GetPairAddr(indices(i))
sum==+p.weight
OD
RETURN (sum)
BYTE FUNC NextSubset(BYTE ARRAY indices BYTE len)
INT i,j
i=len-1
WHILE i>=0
DO
IF indices(i)#i+count-len THEN
indices(i)==+1
FOR j=i+1 TO len-1
DO
indices(j)=indices(j-1)+1
OD
RETURN (1)
FI
i==-1
OD
RETURN (0)
PROC Test(INT len)
BYTE ARRAY indices(100)
BYTE i
PrintF("%I: ",len)
FOR i=0 TO len-1
DO
indices(i)=i
OD
DO
IF Sum(indices,len)=0 THEN
PrintWords(indices,len) PutE()
RETURN
FI
IF NextSubset(indices,len)=0 THEN
PrintE("no subset") PutE()
RETURN
FI
OD
RETURN
PROC Main()
Init()
Test(2)
Test(3)
Test(4)
Test(5)
Test(10)
Test(27)
RETURN</syntaxhighlight>
{{out}}
[https://gitlab.com/amarok8bit/action-rosetta-code/-/raw/master/images/Subset_sum_problem.png Screenshot from Atari 8-bit computer]
<pre>
2: archbishop gestapo
3: centipede markham mycenae
4: alliance balm deploy mycenae
5: alliance brute covariate deploy mincemeat
10: alliance archbishop balm bonnet brute centipede cobol departure deploy mincemeat
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
</pre>
=={{header|Ada}}==
<
with Ada.Strings.Unbounded; use Ada.Strings.Unbounded;
procedure SubsetSum is
Line 144 ⟶ 333:
end loop;
end loop;
end SubsetSum;</
{{out}}
<pre>2: archbishop gestapo
Line 174 ⟶ 363:
=={{header|C}}==
<
#include <stdlib.h>
Line 238 ⟶ 427:
subsum(0, 0);
return 0;
}</
{{output}}<pre>alliance archbishop balm bonnet brute centipede cobol covariate departure deploy diophantine efferent elysee eradicate escritoire exorcism fiat filmy flatworm mincemeat plugging speakeasy
...</pre>
=={{header|C sharp|C#}}==
{{trans|Java}}
<syntaxhighlight lang="csharp">using System;
using System.Collections.Generic;
namespace SubsetSum {
class Item {
public Item(string word, int weight) {
Word = word;
Weight = weight;
}
public string Word { get; set; }
public int Weight { get; set; }
public override string ToString() {
return string.Format("({0}, {1})", Word, Weight);
}
}
class Program {
private static readonly List<Item> items = new List<Item>() {
new Item("alliance", -624),
new Item("archbishop", -915),
new Item("balm", 397),
new Item("bonnet", 452),
new Item("brute", 870),
new Item("centipede", -658),
new Item("cobol", 362),
new Item("covariate", 590),
new Item("departure", 952),
new Item("deploy", 44),
new Item("diophantine", 645),
new Item("efferent", 54),
new Item("elysee", -326),
new Item("eradicate", 376),
new Item("escritoire", 856),
new Item("exorcism", -983),
new Item("fiat", 170),
new Item("filmy", -874),
new Item("flatworm", 503),
new Item("gestapo", 915),
new Item("infra", -847),
new Item("isis", -982),
new Item("lindholm", 999),
new Item("markham", 475),
new Item("mincemeat", -880),
new Item("moresby", 756),
new Item("mycenae", 183),
new Item("plugging", -266),
new Item("smokescreen", 423),
new Item("speakeasy", -745),
new Item("vein", 813),
};
private static readonly int n = items.Count;
private static readonly int LIMIT = 5;
private static int[] indices = new int[n];
private static int count = 0;
private static void ZeroSum(int i, int w) {
if (i != 0 && w == 0) {
for (int j = 0; j < i; j++) {
Console.Write("{0} ", items[indices[j]]);
}
Console.WriteLine("\n");
if (count < LIMIT) count++;
else return;
}
int k = (i != 0) ? indices[i - 1] + 1 : 0;
for (int j = k; j < n; j++) {
indices[i] = j;
ZeroSum(i + 1, w + items[j].Weight);
if (count == LIMIT) return;
}
}
static void Main(string[] args) {
Console.WriteLine("The weights of the following {0} subsets add up to zero:\n", LIMIT);
ZeroSum(0, 0);
}
}
}</syntaxhighlight>
{{out}}
<pre>The weights of the following 5 subsets add up to zero:
(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) (mincemeat, -880) (plugging, -266) (speakeasy, -745)
(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) (infra, -847) (isis, -982) (mincemeat, -880) (moresby, 756) (mycenae, 183) (smokescreen, 423) (speakeasy, -745)
(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) (fiat, 170) (infra, -847) (isis, -982) (markham, 475) (mincemeat, -880) (plugging, -266) (speakeasy, -745)
(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) (exorcism, -983) (fiat, 170) (infra, -847) (isis, -982) (mincemeat, -880) (moresby, 756) (plugging, -266) (vein, 813)
(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) (exorcism, -983) (fiat, 170) (infra, -847) (isis, -982) (smokescreen, 423)</pre>
=={{header|C++}}==
{{trans|C#}}
<syntaxhighlight lang="cpp">#include <iostream>
#include <vector>
std::ostream& operator<<(std::ostream& out, const std::string& str) {
return out << str.c_str();
}
std::vector<std::pair<std::string, int>> items{
{"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},
};
std::vector<int> indices;
int count = 0;
const int LIMIT = 5;
void subsum(int i, int weight) {
if (i != 0 && weight == 0) {
for (int j = 0; j < i; ++j) {
auto item = items[indices[j]];
std::cout << (j ? " " : "") << item.first;
}
std::cout << '\n';
if (count < LIMIT) count++;
else return;
}
int k = (i != 0) ? indices[i - 1] + 1 : 0;
for (int j = k; j < items.size(); ++j) {
indices[i] = j;
subsum(i + 1, weight + items[j].second);
if (count == LIMIT) return;
}
}
int main() {
indices.resize(items.size());
subsum(0, 0);
return 0;
}</syntaxhighlight>
{{out}}
<pre>alliance archbishop balm bonnet brute centipede cobol covariate departure deploy diophantine efferent elysee eradicate escritoire exorcism fiat filmy flatworm mincemeat plugging speakeasy
alliance archbishop balm bonnet brute centipede cobol covariate departure deploy diophantine efferent elysee eradicate escritoire exorcism infra isis mincemeat moresby mycenae smokescreen speakeasy
alliance archbishop balm bonnet brute centipede cobol covariate departure deploy diophantine efferent elysee eradicate escritoire fiat infra isis markham mincemeat plugging speakeasy
alliance archbishop balm bonnet brute centipede cobol covariate departure deploy diophantine efferent elysee eradicate exorcism fiat infra isis mincemeat moresby plugging vein
alliance archbishop balm bonnet brute centipede cobol covariate departure deploy diophantine efferent elysee eradicate exorcism fiat infra isis smokescreen</pre>
=={{header|D}}==
A simple brute-force solution. This used the module of the third D solution of the Combinations Task.
{{trans|Ruby}}
<
import std.stdio, std.algorithm, std.typecons, combinations3;
Line 269 ⟶ 632:
comb.map!q{ a[0] });
"No solution found.".writeln;
}</
{{out}}
<pre>A subset of length 2: archbishop, gestapo</pre>
Line 276 ⟶ 639:
This version prints all the 349_167 solutions in about 1.8 seconds and counts them in about 0.05 seconds.
{{trans|C}}
<
enum showAllSolutions = true;
Line 372 ⟶ 735:
writeln("Zero sums: ", sols);
}</
{{out}}
<pre>Zero sums: 349167</pre>
Line 380 ⟶ 743:
We use the Pseudo-polynomial time dynamic programming solution, found in the [[wp:Subset sum problem|Subset sum problem]] Wikipedia article. If A and B are the min and max possible sums, the time and memory needed are '''O((B-A)*N)'''. '''Q''' is an array such as Q(i,s) = true if there is a nonempty subset of x0, ..., xi which sums to s.
<
;; 0 <= i < N , A <= s < B , -A = abs(A)
;; mapping two dims Q(i,s) to one-dim Q(qidx(i,s)) :
Line 427 ⟶ 790:
(map (lambda(i) (first (list-ref input i))) (fillQ (map rest input))))
</syntaxhighlight>
{{out}}
<pre>
Line 482 ⟶ 845:
===Brute force===
We use the '''powerset''' procrastinator which gives in sequence all subsets of the input list.
<
(lib 'sequences) ;; for powerset
Line 509 ⟶ 872:
("deploy" . 44) ("diophantine" . 645) ("efferent" . 54)
("elysee" . -326) ("eradicate" . 376))
</syntaxhighlight>
=={{header|FunL}}==
<
def sumset( a ) = foldl1( (+), map(w, a) )
Line 556 ⟶ 919:
for i <- 0..5
println( i, subsetSum(s, snd, i).get() )</
{{out}}
Line 570 ⟶ 933:
=={{header|Go}}==
<
import "fmt"
Line 636 ⟶ 999:
}
fmt.Println("no subset sums to 0")
}</
{{out}}
<pre>
Line 652 ⟶ 1,015:
=={{header|Haskell}}==
<
combinations 0 _ = [[]]
combinations _ [] = []
Line 683 ⟶ 1,046:
W "vein" 813]
main = print $ map word $ head $ solver items</
{{out}}
<pre>["archbishop","gestapo"]</pre>
<syntaxhighlight lang
subsum w =
where
s a x = merge a $ map f a
where
f (a, l) = (a + x, l ++ [x])
-- Keep list of sums sorted and unique.
merge [] a = a
merge a@((av, al):as) b@((bv, bl):bs)
| av < bv = (av, al) : merge as b
| av == bv = (bv, bl) : merge as bs
| otherwise = (bv, bl) : merge a bs
items :: [Int]
items = [-61, 1, 32, 373, 311, 249, 311, 32, -92, -185, -433,
-402, -247, 156, 125, 249, 32, -464, -278, 218, 32, -123,
-216, 373, -185, -402, 156, -402, -61, -31, 902
main :: IO ()
main = print $ subsum 0 items</syntaxhighlight>
{{out}}
<pre>[-61,32,373,311,249,311,32,-92,-185,-433,-402,-247,156,125,249,32,-464,-278,218,32,-123,-216,373,-185,-402,156,-402,-61,902]</pre>
=={{header|Icon}} and {{header|Unicon}}==
{{trans|Ruby}}
<
procedure main()
Line 757 ⟶ 1,124:
return T
end</
{{libheader|Icon Programming Library}}
Line 799 ⟶ 1,166:
Task data:
<
alliance -624
archbishop -915
Line 834 ⟶ 1,201:
words=:{.@;:;._2 text
numbs=:+/|:0&".;._2 text</
Implementation:
<
p=:(#~ 0&<)y
n=:(#~ 0&>)y
Line 847 ⟶ 1,214:
keep=: [ #~ #&2@#@[ #: choose i.~ ]
;:inv words #~y e. (p keep P),n keep N
)</
Task example:
<
centipede markham mycenae</
Note also that there are over 300,000 valid solutions here. More than can be comfortably displayed:
<
Ns=: </.~ /:~ (I.N e. P){N
+/#@,@{"1 Ps,.Ns
349168</
(One of those is the empty solution, but the rest of them are valid.)
Line 865 ⟶ 1,232:
=={{header|Java}}==
{{trans|Kotlin}}
<
private static class Item {
private String word;
Line 942 ⟶ 1,309:
zeroSum(0, 0);
}
}</
{{out}}
<pre>The weights of the following 5 subsets add up to zero:
Line 955 ⟶ 1,322:
(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) (exorcism, -983) (fiat, 170) (infra, -847) (isis, -982) (smokescreen, 423)</pre>
=={{header|jq}}==
{{works with|jq}}
'''Works with gojq, the Go implementation of jq''' (provided `keys_unsorted` is replaced by `keys`)
<syntaxhighlight lang="jq">
# Input: an array of n elements, each of which is either in or out
# Output: a stream of the 2^n possible selections
def selections:
# map( [null, .] ) | combinations | map(select(.));
if length == 0
then .
else .[0] as $x
| .[1:] | selections | ., ([$x] + .)
end ;
# input: a JSON object giving the weights
def zero_sums:
def sum($dict; $sum):
map( $dict[.] ) | add == $sum;
. as $dict
| keys_unsorted | selections | select( sum($dict; 0));
</syntaxhighlight>
'''An Example'''
<syntaxhighlight lang="jq">def 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
};
weights | first(zero_sums)</syntaxhighlight>
{{out}}
<pre>
[
"archbishop",
"balm",
"bonnet",
"centipede",
"cobol",
"covariate",
"deploy",
"efferent",
"elysee"
]
</pre>
=={{header|Julia}}==
<syntaxhighlight lang="julia">using Combinatorics
const 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]
const weights = [v for (k, v) in pairs]
const weightkeyed = Dict(Pair(v, k) for (k, v) in pairs)
function zerosums()
total = 0
for i in 1:length(weights)
print("\nFor length $i: ")
sets = [a for a in combinations(weights, i) if sum(a) == 0]
if (n = length(sets)) == 0
print("None")
else
total += n
print("$n sets, example: ", map(x -> weightkeyed[x], rand(sets)))
end
end
println("\n\nGrand total sets: $total")
end
zerosums()
</syntaxhighlight>{{out}}
<pre>
For length 1: None
For length 2: 1 sets, example: ["archbishop", "gestapo"]
For length 3: 2 sets, example: ["centipede", "markham", "mycenae"]
For length 4: 9 sets, example: ["balm", "efferent", "filmy", "smokescreen"]
For length 5: 48 sets, example: ["departure", "elysee", "lindholm", "mincemeat", "speakeasy"]
For length 6: 178 sets, example: ["alliance", "bonnet", "centipede", "isis", "lindholm", "vein"]
For length 7: 629 sets, example: ["balm", "brute", "cobol", "deploy", "filmy", "isis", "mycenae"]
For length 8: 1634 sets, example: ["alliance", "brute", "centipede", "departure", "mincemeat", "mycenae", "plugging", "smokescreen"]
For length 9: 4040 sets, example: ["alliance", "brute", "deploy", "efferent", "elysee", "fiat", "filmy", "flatworm", "mycenae"]
For length 10: 8673 sets, example: ["archbishop", "brute", "escritoire", "filmy", "gestapo", "isis", "lindholm", "mincemeat", "moresby", "speakeasy"]
For length 11: 15680 sets, example: ["cobol", "covariate", "deploy", "efferent", "elysee", "eradicate", "exorcism", "filmy", "flatworm", "lindholm", "speakeasy"]
For length 12: 25492 sets, example: ["alliance", "balm", "diophantine", "efferent", "eradicate", "fiat", "filmy", "flatworm", "infra", "isis", "lindholm", "mycenae"]
For length 13: 35940 sets, example: ["alliance", "archbishop", "bonnet", "departure", "deploy", "efferent", "fiat", "filmy", "gestapo", "infra", "moresby", "mycenae", "plugging"]
For length 14: 44920 sets, example: ["archbishop", "centipede", "cobol", "covariate", "deploy", "efferent", "eradicate", "escritoire", "fiat", "gestapo", "isis", "mincemeat", "speakeasy", "vein"]
For length 15: 49368 sets, example: ["alliance", "archbishop", "bonnet", "covariate", "departure", "diophantine", "efferent", "elysee", "eradicate", "escritoire", "isis", "mincemeat", "plugging", "speakeasy", "vein"]
For length 16: 47835 sets, example: ["alliance", "archbishop", "balm", "bonnet", "centipede", "cobol", "covariate", "departure", "elysee", "flatworm", "infra", "isis", "moresby", "mycenae", "plugging", "smokescreen"]
For length 17: 40960 sets, example: ["balm", "bonnet", "centipede", "cobol", "covariate", "departure", "deploy", "diophantine", "efferent", "elysee", "eradicate", "fiat", "filmy", "isis", "mincemeat", "smokescreen", "speakeasy"]
For length 18: 31139 sets, example: ["balm", "bonnet", "centipede", "covariate", "departure", "deploy", "diophantine", "efferent", "elysee", "eradicate", "exorcism", "gestapo", "infra", "isis", "mincemeat", "mycenae", "speakeasy", "vein"]
For length 19: 20530 sets, example: ["alliance", "archbishop", "balm", "bonnet", "departure", "deploy", "elysee", "exorcism", "fiat", "gestapo", "infra", "isis", "lindholm", "markham", "mincemeat", "mycenae", "plugging", "smokescreen", "vein"]
For length 20: 11926 sets, example: ["archbishop", "bonnet", "brute", "centipede", "cobol", "deploy", "diophantine", "elysee", "eradicate", "exorcism", "fiat", "isis", "lindholm", "markham", "mincemeat", "moresby", "mycenae", "plugging", "smokescreen", "speakeasy"]
For length 21: 6089 sets, example: ["alliance", "balm", "bonnet", "brute", "centipede", "cobol", "covariate", "departure", "deploy", "elysee", "escritoire", "exorcism", "filmy", "flatworm", "infra", "isis", "markham", "mincemeat", "moresby", "mycenae", "plugging"]
For length 22: 2688 sets, example: ["archbishop", "balm", "bonnet", "brute", "centipede", "covariate", "deploy", "diophantine", "elysee", "eradicate", "exorcism", "filmy", "flatworm", "gestapo", "isis", "markham", "mincemeat", "moresby", "mycenae", "plugging", "smokescreen", "speakeasy"]
For length 23: 956 sets, example: ["alliance", "archbishop", "balm", "brute", "centipede", "cobol", "departure", "deploy", "efferent", "elysee", "eradicate", "escritoire", "exorcism", "fiat", "gestapo", "infra", "isis", "lindholm", "markham", "mincemeat", "moresby", "plugging", "speakeasy"]
For length 24: 341 sets, example: ["alliance", "archbishop", "balm", "brute", "centipede", "cobol", "covariate", "departure", "deploy", "diophantine", "efferent", "elysee", "eradicate", "escritoire", "exorcism", "infra", "isis", "lindholm", "markham", "mincemeat", "mycenae", "plugging", "smokescreen", "speakeasy"]
For length 25: 73 sets, example: ["alliance", "archbishop", "balm", "bonnet", "brute", "centipede", "cobol", "departure", "deploy", "diophantine", "efferent", "elysee", "exorcism", "fiat", "filmy", "flatworm", "gestapo", "infra", "isis", "lindholm", "markham", "mincemeat", "mycenae", "speakeasy", "vein"]
For length 26: 14 sets, example: ["alliance", "archbishop", "balm", "bonnet", "centipede", "cobol", "departure", "diophantine", "efferent", "elysee", "eradicate", "escritoire", "exorcism", "fiat", "filmy", "flatworm", "gestapo", "infra", "isis", "lindholm", "mincemeat", "mycenae", "plugging", "smokescreen", "speakeasy", "vein"]
For length 27: 2 sets, example: ["alliance", "archbishop", "balm", "brute", "centipede", "cobol", "covariate", "deploy", "diophantine", "efferent", "elysee", "eradicate", "exorcism", "fiat", "filmy", "flatworm", "gestapo", "infra", "isis", "lindholm", "mincemeat", "moresby", "mycenae", "plugging", "smokescreen", "speakeasy", "vein"]
For length 28: None
For length 29: None
For length 30: None
For length 31: None
Grand total sets: 349167
</pre>
=={{header|Kotlin}}==
{{trans|C}}
<
class Item(val word: String, val weight: Int) {
Line 1,021 ⟶ 1,530:
println("The weights of the following $LIMIT subsets add up to zero:\n")
zeroSum(0, 0)
}</
{{out}}
Line 1,038 ⟶ 1,547:
</pre>
=={{header|Mathematica}}/{{header|Wolfram Language}}==
<
{"brute", 870}, {"centipede", -658}, {"cobol", 362}, {"covariate", 590},{"departure", 952},
{"deploy", 44}, {"diophantine", 645}, {"efferent", 54}, {"elysee", -326}, {"eradicate", 376},
Line 1,048 ⟶ 1,557:
result = Rest@Select[ Subsets[a, 7], (Total[#[[;; , 2]]] == 0) &];
Map[ (Print["A zero-sum subset of length ", Length[#], " : ", #[[;; , 1]]])& , result ]</
<pre>A zero-sum subset of length 2 : {archbishop,gestapo}
Line 1,061 ⟶ 1,570:
The above code uses a brute-force approach, but Mathematica includes several solution schemes that can be used to solve this problem. We can cast it as an integer linear programming problem, and thus find the largest or smallest subset sum, or even sums with specific constraints, such as a sum using three negative values and nine positive values.
<
{"brute", 870}, {"centipede", -658}, {"cobol", 362}, {"covariate", 590},{"departure", 952},
{"deploy", 44}, {"diophantine", 645}, {"efferent", 54}, {"elysee", -326}, {"eradicate", 376},
Line 1,095 ⟶ 1,604:
Print["3 -ves, 9 +ves: ", Select[Transpose[{threeNineSoln*aValues, aNames}], #[[1]] != 0 &]];
</syntaxhighlight>
<pre>Maximal solution: {{-624, alliance}, {-915, archbishop}, {397, balm},
Line 1,112 ⟶ 1,621:
{423, smokescreen}}.</pre>
=={{header|MiniZinc}}==
<syntaxhighlight lang="minizinc">
%Subset sum. Nigel Galloway: January 6th., 2021.
enum Items={alliance,archbishop,balm,bonnet,brute,centipede,cobol,covariate,departure,deploy,diophantine,efferent,elysee,eradicate,escritoire,exorcism,fiat,filmy,flatworm,gestapo,infra,isis,lindholm,markham,mincemeat,moresby,mycenae,plugging,smokescreen,speakeasy,vein};
array[Items] of int: weight=[-624,-915,397,452,870,-658,362,590,952,44,645,54,-326,376,856,-983,170,-874,503,915,-847,-982,999,475,-880,756,183,-266,423,-745,813];
var set of Items: selected;
var int: wSelected=sum(n in selected)(weight[n]);
constraint wSelected=0;
</syntaxhighlight>
{{out}}
<pre>
selected = {alliance, archbishop, balm, bonnet, brute, centipede, cobol, covariate, departure, deploy, diophantine, efferent, elysee, eradicate, escritoire, exorcism, fiat, filmy, flatworm, mincemeat, plugging, speakeasy};
----------
Finished in 185msec
</pre>
=={{header|Modula-2}}==
<
FROM FormatString IMPORT FormatString;
FROM Terminal IMPORT WriteString,WriteLn,ReadChar;
Line 1,214 ⟶ 1,738:
ReadChar;
END SubsetSum.</
=={{header|Nim}}==
{{libheader|itertools}}
We need the third party module "itertools" to compute the combinations.
<syntaxhighlight lang="nim">import sequtils, strformat, strutils
import itertools
const 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}
var words: seq[string]
var values: seq[int]
for (word, value) in Words:
words.add word
values.add value
for lg in 1..words.len:
block checkCombs:
for comb in combinations(words.len, lg):
var sum = 0
for idx in comb: sum += values[idx]
if sum == 0:
echo &"For length {lg}, found for example: ", comb.mapIt(words[it]).join(" ")
break checkCombs
echo &"For length {lg}, no set found."</syntaxhighlight>
{{out}}
<pre>For length 1, no set found.
For length 2, found for example: archbishop gestapo
For length 3, found for example: centipede markham mycenae
For length 4, found for example: alliance balm deploy mycenae
For length 5, found for example: alliance brute covariate deploy mincemeat
For length 6, found for example: alliance archbishop balm deploy gestapo mycenae
For length 7, found for example: alliance archbishop bonnet cobol departure exorcism moresby
For length 8, found for example: alliance archbishop balm bonnet fiat flatworm isis lindholm
For length 9, found for example: alliance archbishop balm bonnet brute covariate eradicate mincemeat plugging
For length 10, found for example: alliance archbishop balm bonnet brute centipede cobol departure deploy mincemeat
For length 11, found for example: alliance archbishop balm bonnet brute centipede cobol departure infra moresby speakeasy
For length 12, found for example: alliance archbishop balm bonnet brute centipede cobol covariate diophantine efferent elysee infra
For length 13, found for example: alliance archbishop balm bonnet brute centipede cobol covariate departure efferent eradicate filmy isis
For length 14, found for example: alliance archbishop balm bonnet brute centipede cobol covariate departure deploy elysee filmy markham speakeasy
For length 15, found for example: alliance archbishop balm bonnet brute centipede cobol covariate departure deploy elysee exorcism flatworm infra mycenae
For length 16, found for example: alliance archbishop balm bonnet brute centipede cobol covariate departure deploy diophantine elysee exorcism filmy gestapo infra
For length 17, found for example: alliance archbishop balm bonnet brute centipede cobol covariate departure deploy diophantine exorcism isis mincemeat mycenae plugging vein
For length 18, found for example: alliance archbishop balm bonnet brute centipede cobol covariate departure deploy diophantine efferent elysee exorcism filmy isis mycenae vein
For length 19, found for example: alliance archbishop balm bonnet brute centipede cobol covariate departure deploy diophantine efferent elysee eradicate exorcism fiat infra isis smokescreen
For length 20, found for example: alliance archbishop balm bonnet brute centipede cobol covariate departure deploy diophantine efferent elysee eradicate exorcism gestapo infra isis smokescreen speakeasy
For length 21, found for example: alliance archbishop balm bonnet brute centipede cobol covariate departure deploy diophantine efferent elysee eradicate exorcism flatworm infra lindholm mincemeat plugging speakeasy
For length 22, found for example: alliance archbishop balm bonnet brute centipede cobol covariate departure deploy diophantine efferent elysee eradicate escritoire exorcism fiat filmy flatworm mincemeat plugging speakeasy
For length 23, found for example: alliance archbishop balm bonnet brute centipede cobol covariate departure deploy diophantine efferent elysee eradicate escritoire exorcism infra isis mincemeat moresby mycenae smokescreen speakeasy
For length 24, found for example: alliance archbishop balm bonnet brute centipede cobol covariate departure deploy diophantine efferent elysee exorcism filmy gestapo infra markham mincemeat moresby mycenae plugging smokescreen speakeasy
For length 25, found for example: 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
For length 26, found for example: 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
For length 27, found for example: 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
For length 28, no set found.
For length 29, no set found.
For length 30, no set found.
For length 31, no set found.</pre>
=={{header|OCaml}}==
Line 1,220 ⟶ 1,831:
Just search randomly until a result is found:
<
[ "alliance", -624; "archbishop", -915; "balm", 397; "bonnet", 452;
"brute", 870; "centipede", -658; "cobol", 362; "covariate", 590;
Line 1,254 ⟶ 1,865:
in
let res = aux [] d in
List.iter (fun (n,w) -> Printf.printf " %4d\t%s\n" w n) res</
=={{header|Perl}}==
{{libheader|ntheory}}
<
my %pairs = (
Line 1,278 ⟶ 1,889:
lastfor, print "Length $n: @names[@_]\n" if vecsum(@weights[@_]) == 0;
} @names, $n;
}</
Printing just the first one found for each number of elements:
{{out}}
Line 1,294 ⟶ 1,905:
We can also use different modules for this brute force method. Assuming the same pairs/names/weights variables:
<
use Algorithm::Combinatorics qw/combinations/;
foreach my $n (1 .. @names) {
Line 1,303 ⟶ 1,914:
last;
}
}</
=={{header|Phix}}==
Simple Brute force
<!--<syntaxhighlight lang="phix">(phixonline)-->
<span style="color: #008080;">with</span> <span style="color: #008080;">javascript_semantics</span>
<span style="color: #008080;">constant</span> <span style="color: #0000FF;">{</span><span style="color: #000000;">words</span><span style="color: #0000FF;">,</span><span style="color: #000000;">weights</span><span style="color: #0000FF;">}</span> <span style="color: #0000FF;">=</span> <span style="color: #7060A8;">columnize</span><span style="color: #0000FF;">({{</span><span style="color: #008000;">"alliance"</span><span style="color: #0000FF;">,</span> <span style="color: #0000FF;">-</span><span style="color: #000000;">624</span><span style="color: #0000FF;">},</span> <span style="color: #0000FF;">{</span><span style="color: #008000;">"archbishop"</span><span style="color: #0000FF;">,</span> <span style="color: #0000FF;">-</span><span style="color: #000000;">915</span><span style="color: #0000FF;">},</span>
<span style="color: #0000FF;">{</span><span style="color: #008000;">"balm"</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">397</span><span style="color: #0000FF;">},</span> <span style="color: #0000FF;">{</span><span style="color: #008000;">"bonnet"</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">452</span><span style="color: #0000FF;">},</span> <span style="color: #0000FF;">{</span><span style="color: #008000;">"brute"</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">870</span><span style="color: #0000FF;">},</span>
<span style="color: #0000FF;">{</span><span style="color: #008000;">"centipede"</span><span style="color: #0000FF;">,</span> <span style="color: #0000FF;">-</span><span style="color: #000000;">658</span><span style="color: #0000FF;">},</span> <span style="color: #0000FF;">{</span><span style="color: #008000;">"cobol"</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">362</span><span style="color: #0000FF;">},</span> <span style="color: #0000FF;">{</span><span style="color: #008000;">"covariate"</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">590</span><span style="color: #0000FF;">},</span>
<span style="color: #0000FF;">{</span><span style="color: #008000;">"departure"</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">952</span><span style="color: #0000FF;">},</span> <span style="color: #0000FF;">{</span><span style="color: #008000;">"deploy"</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">44</span><span style="color: #0000FF;">},</span> <span style="color: #0000FF;">{</span><span style="color: #008000;">"diophantine"</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">645</span><span style="color: #0000FF;">},</span>
<span style="color: #0000FF;">{</span><span style="color: #008000;">"efferent"</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">54</span><span style="color: #0000FF;">},</span> <span style="color: #0000FF;">{</span><span style="color: #008000;">"elysee"</span><span style="color: #0000FF;">,</span> <span style="color: #0000FF;">-</span><span style="color: #000000;">326</span><span style="color: #0000FF;">},</span> <span style="color: #0000FF;">{</span><span style="color: #008000;">"eradicate"</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">376</span><span style="color: #0000FF;">},</span>
<span style="color: #0000FF;">{</span><span style="color: #008000;">"escritoire"</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">856</span><span style="color: #0000FF;">},</span> <span style="color: #0000FF;">{</span><span style="color: #008000;">"exorcism"</span><span style="color: #0000FF;">,</span> <span style="color: #0000FF;">-</span><span style="color: #000000;">983</span><span style="color: #0000FF;">},</span> <span style="color: #0000FF;">{</span><span style="color: #008000;">"fiat"</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">170</span><span style="color: #0000FF;">},</span>
<span style="color: #0000FF;">{</span><span style="color: #008000;">"filmy"</span><span style="color: #0000FF;">,</span> <span style="color: #0000FF;">-</span><span style="color: #000000;">874</span><span style="color: #0000FF;">},</span> <span style="color: #0000FF;">{</span><span style="color: #008000;">"flatworm"</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">503</span><span style="color: #0000FF;">},</span> <span style="color: #0000FF;">{</span><span style="color: #008000;">"gestapo"</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">915</span><span style="color: #0000FF;">},</span>
<span style="color: #0000FF;">{</span><span style="color: #008000;">"infra"</span><span style="color: #0000FF;">,</span> <span style="color: #0000FF;">-</span><span style="color: #000000;">847</span><span style="color: #0000FF;">},</span> <span style="color: #0000FF;">{</span><span style="color: #008000;">"isis"</span><span style="color: #0000FF;">,</span> <span style="color: #0000FF;">-</span><span style="color: #000000;">982</span><span style="color: #0000FF;">},</span> <span style="color: #0000FF;">{</span><span style="color: #008000;">"lindholm"</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">999</span><span style="color: #0000FF;">},</span>
<span style="color: #0000FF;">{</span><span style="color: #008000;">"markham"</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">475</span><span style="color: #0000FF;">},</span> <span style="color: #0000FF;">{</span><span style="color: #008000;">"mincemeat"</span><span style="color: #0000FF;">,</span> <span style="color: #0000FF;">-</span><span style="color: #000000;">880</span><span style="color: #0000FF;">},</span> <span style="color: #0000FF;">{</span><span style="color: #008000;">"moresby"</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">756</span><span style="color: #0000FF;">},</span>
<span style="color: #0000FF;">{</span><span style="color: #008000;">"mycenae"</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">183</span><span style="color: #0000FF;">},</span> <span style="color: #0000FF;">{</span><span style="color: #008000;">"plugging"</span><span style="color: #0000FF;">,</span> <span style="color: #0000FF;">-</span><span style="color: #000000;">266</span><span style="color: #0000FF;">},</span> <span style="color: #0000FF;">{</span><span style="color: #008000;">"smokescreen"</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">423</span><span style="color: #0000FF;">},</span>
<span style="color: #0000FF;">{</span><span style="color: #008000;">"speakeasy"</span><span style="color: #0000FF;">,</span> <span style="color: #0000FF;">-</span><span style="color: #000000;">745</span><span style="color: #0000FF;">},</span> <span style="color: #0000FF;">{</span><span style="color: #008000;">"vein"</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">813</span><span style="color: #0000FF;">}})</span>
<span style="color: #008080;">function</span> <span style="color: #000000;">comb</span><span style="color: #0000FF;">(</span><span style="color: #004080;">sequence</span> <span style="color: #000000;">pool</span><span style="color: #0000FF;">,</span> <span style="color: #004080;">integer</span> <span style="color: #000000;">needed</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">done</span><span style="color: #0000FF;">=</span><span style="color: #000000;">0</span><span style="color: #0000FF;">,</span> <span style="color: #004080;">sequence</span> <span style="color: #000000;">chosen</span><span style="color: #0000FF;">={})</span>
<span style="color: #008080;">if</span> <span style="color: #000000;">needed</span><span style="color: #0000FF;">=</span><span style="color: #000000;">0</span> <span style="color: #008080;">then</span> <span style="color: #000080;font-style:italic;">-- got a full set</span>
<span style="color: #008080;">if</span> <span style="color: #7060A8;">sum</span><span style="color: #0000FF;">(</span><span style="color: #7060A8;">extract</span><span style="color: #0000FF;">(</span><span style="color: #000000;">weights</span><span style="color: #0000FF;">,</span><span style="color: #000000;">chosen</span><span style="color: #0000FF;">))=</span><span style="color: #000000;">0</span> <span style="color: #008080;">then</span>
<span style="color: #004080;">sequence</span> <span style="color: #000000;">cw</span> <span style="color: #0000FF;">=</span> <span style="color: #7060A8;">extract</span><span style="color: #0000FF;">(</span><span style="color: #000000;">words</span><span style="color: #0000FF;">,</span><span style="color: #000000;">chosen</span><span style="color: #0000FF;">),</span>
<span style="color: #000000;">scw</span> <span style="color: #0000FF;">=</span> <span style="color: #7060A8;">shorten</span><span style="color: #0000FF;">(</span><span style="color: #000000;">cw</span><span style="color: #0000FF;">,</span><span style="color: #008000;">"items"</span><span style="color: #0000FF;">,</span><span style="color: #000000;">4</span><span style="color: #0000FF;">)</span>
<span style="color: #7060A8;">printf</span><span style="color: #0000FF;">(</span><span style="color: #000000;">1</span><span style="color: #0000FF;">,</span><span style="color: #008000;">"%d: %s\n"</span><span style="color: #0000FF;">,{</span><span style="color: #7060A8;">length</span><span style="color: #0000FF;">(</span><span style="color: #000000;">chosen</span><span style="color: #0000FF;">),</span><span style="color: #7060A8;">join</span><span style="color: #0000FF;">(</span><span style="color: #000000;">scw</span><span style="color: #0000FF;">,</span><span style="color: #008000;">","</span><span style="color: #0000FF;">)})</span>
<span style="color: #008080;">return</span> <span style="color: #004600;">true</span>
<span style="color: #008080;">end</span> <span style="color: #008080;">if</span>
<span style="color: #008080;">elsif</span> <span style="color: #000000;">done</span><span style="color: #0000FF;">+</span><span style="color: #000000;">needed</span><span style="color: #0000FF;"><=</span><span style="color: #7060A8;">length</span><span style="color: #0000FF;">(</span><span style="color: #000000;">pool</span><span style="color: #0000FF;">)</span> <span style="color: #008080;">then</span>
<span style="color: #000080;font-style:italic;">-- get all combinations with and without the next item:</span>
<span style="color: #000000;">done</span> <span style="color: #0000FF;">+=</span> <span style="color: #000000;">1</span>
<span style="color: #008080;">if</span> <span style="color: #000000;">comb</span><span style="color: #0000FF;">(</span><span style="color: #000000;">pool</span><span style="color: #0000FF;">,</span><span style="color: #000000;">needed</span><span style="color: #0000FF;">-</span><span style="color: #000000;">1</span><span style="color: #0000FF;">,</span><span style="color: #000000;">done</span><span style="color: #0000FF;">,</span><span style="color: #7060A8;">append</span><span style="color: #0000FF;">(</span><span style="color: #7060A8;">deep_copy</span><span style="color: #0000FF;">(</span><span style="color: #000000;">chosen</span><span style="color: #0000FF;">),</span><span style="color: #000000;">pool</span><span style="color: #0000FF;">[</span><span style="color: #000000;">done</span><span style="color: #0000FF;">]))</span>
<span style="color: #008080;">or</span> <span style="color: #000000;">comb</span><span style="color: #0000FF;">(</span><span style="color: #000000;">pool</span><span style="color: #0000FF;">,</span><span style="color: #000000;">needed</span> <span style="color: #0000FF;">,</span><span style="color: #000000;">done</span><span style="color: #0000FF;">,</span><span style="color: #000000;">chosen</span><span style="color: #0000FF;">)</span> <span style="color: #008080;">then</span>
<span style="color: #008080;">return</span> <span style="color: #004600;">true</span>
<span style="color: #008080;">end</span> <span style="color: #008080;">if</span>
<span style="color: #008080;">end</span> <span style="color: #008080;">if</span>
<span style="color: #008080;">return</span> <span style="color: #004600;">false</span>
<span style="color: #008080;">end</span> <span style="color: #008080;">function</span>
<span style="color: #004080;">integer</span> <span style="color: #000000;">n</span> <span style="color: #0000FF;">=</span> <span style="color: #7060A8;">length</span><span style="color: #0000FF;">(</span><span style="color: #000000;">weights</span><span style="color: #0000FF;">)</span>
<span style="color: #008080;">for</span> <span style="color: #000000;">i</span><span style="color: #0000FF;">=</span><span style="color: #000000;">1</span> <span style="color: #008080;">to</span> <span style="color: #000000;">n</span> <span style="color: #008080;">do</span>
<span style="color: #008080;">if</span> <span style="color: #008080;">not</span> <span style="color: #000000;">comb</span><span style="color: #0000FF;">(</span><span style="color: #7060A8;">tagset</span><span style="color: #0000FF;">(</span><span style="color: #000000;">n</span><span style="color: #0000FF;">),</span><span style="color: #000000;">i</span><span style="color: #0000FF;">)</span> <span style="color: #008080;">then</span>
<span style="color: #7060A8;">printf</span><span style="color: #0000FF;">(</span><span style="color: #000000;">1</span><span style="color: #0000FF;">,</span><span style="color: #008000;">"%d: No zero-sum subsets of that length\n"</span><span style="color: #0000FF;">,{</span><span style="color: #000000;">i</span><span style="color: #0000FF;">})</span>
<span style="color: #008080;">end</span> <span style="color: #008080;">if</span>
<span style="color: #008080;">end</span> <span style="color: #008080;">for</span>
<!--</syntaxhighlight>-->
{{out}}
<pre>
1: No zero-sum subsets of that length
2:
3:
4:
5:
6:
7:
8:
9:
10:
11:
12:
13:
14:
15:
16:
17:
18:
19:
20:
21:
22:
23:
24:
25:
26:
27:
28: No zero-sum subsets of that length
29: No zero-sum subsets of that length
30: No zero-sum subsets of that length
31: No zero-sum subsets of that length
</pre>
===Alternative===
Using the harder set of weights from Go, and the version 1 approach of Python,
using a dictionary so that fractional weights can be accomodated
Note that fractional weights may trigger all the usual IEEE-754 issues such as 0.3+0.6-0.9 != 0, so you may need to use sprintf()'d keys with matching to_number()'s.<br>
This is significantly faster (near instant, in fact) than an "all possible combinations" approach.
Shows the first zero-sum subset found, only.
<!--<syntaxhighlight lang="phix">(phixonline)-->
<span style="color: #008080;">with</span> <span style="color: #008080;">javascript_semantics</span>
<span style="color: #008080;">constant</span> <span style="color: #000000;">weights</span> <span style="color: #0000FF;">=</span> <span style="color: #0000FF;">{-</span><span style="color: #000000;">61</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">1</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">32</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">373</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">311</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">249</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">311</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">32</span><span style="color: #0000FF;">,</span> <span style="color: #0000FF;">-</span><span style="color: #000000;">92</span><span style="color: #0000FF;">,</span> <span style="color: #0000FF;">-</span><span style="color: #000000;">185</span><span style="color: #0000FF;">,</span> <span style="color: #0000FF;">-</span><span style="color: #000000;">433</span><span style="color: #0000FF;">,</span>
<span style="color: #0000FF;">-</span><span style="color: #000000;">402</span><span style="color: #0000FF;">,</span> <span style="color: #0000FF;">-</span><span style="color: #000000;">247</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">156</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">125</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">249</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">32</span><span style="color: #0000FF;">,</span> <span style="color: #0000FF;">-</span><span style="color: #000000;">464</span><span style="color: #0000FF;">,</span> <span style="color: #0000FF;">-</span><span style="color: #000000;">278</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">218</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">32</span><span style="color: #0000FF;">,</span>
<span style="color: #0000FF;">-</span><span style="color: #000000;">123</span><span style="color: #0000FF;">,</span> <span style="color: #0000FF;">-</span><span style="color: #000000;">216</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">373</span><span style="color: #0000FF;">,</span> <span style="color: #0000FF;">-</span><span style="color: #000000;">185</span><span style="color: #0000FF;">,</span> <span style="color: #0000FF;">-</span><span style="color: #000000;">402</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">156</span><span style="color: #0000FF;">,</span> <span style="color: #0000FF;">-</span><span style="color: #000000;">402</span><span style="color: #0000FF;">,</span> <span style="color: #0000FF;">-</span><span style="color: #000000;">61</span><span style="color: #0000FF;">,</span> <span style="color: #0000FF;">-</span><span style="color: #000000;">31</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">902</span> <span style="color: #0000FF;">}</span>
<span style="color: #004080;">integer</span> <span style="color: #000000;">sums</span> <span style="color: #0000FF;">=</span> <span style="color: #7060A8;">new_dict</span><span style="color: #0000FF;">()</span>
<span style="color: #008080;">for</span> <span style="color: #000000;">w</span><span style="color: #0000FF;">=</span><span style="color: #000000;">1</span> <span style="color: #008080;">to</span> <span style="color: #7060A8;">length</span><span style="color: #0000FF;">(</span><span style="color: #000000;">weights</span><span style="color: #0000FF;">)</span> <span style="color: #008080;">do</span>
<span style="color: #000080;font-style:italic;">-- make a separate modifiable copy of sums, otherwise
-- it c/would mark sums[weights[w]*{2,3,etc}] as valid,
-- ie there cannot be any w in the getd_by_index(node).</span>
<span style="color: #004080;">integer</span> <span style="color: #000000;">s</span> <span style="color: #0000FF;">=</span> <span style="color: #7060A8;">new_dict</span><span style="color: #0000FF;">(</span><span style="color: #000000;">sums</span><span style="color: #0000FF;">)</span>
<span style="color: #004080;">atom</span> <span style="color: #000000;">v</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">weights</span><span style="color: #0000FF;">[</span><span style="color: #000000;">w</span><span style="color: #0000FF;">]</span>
<span style="color: #008080;">if</span> <span style="color: #7060A8;">getd_index</span><span style="color: #0000FF;">(</span><span style="color: #000000;">v</span><span style="color: #0000FF;">,</span><span style="color: #000000;">s</span><span style="color: #0000FF;">)=</span><span style="color: #004600;">NULL</span> <span style="color: #008080;">then</span> <span style="color: #7060A8;">setd</span><span style="color: #0000FF;">(</span><span style="color: #000000;">v</span><span style="color: #0000FF;">,{</span><span style="color: #000000;">w</span><span style="color: #0000FF;">},</span><span style="color: #000000;">s</span><span style="color: #0000FF;">)</span> <span style="color: #008080;">end</span> <span style="color: #008080;">if</span>
<span style="color: #004080;">sequence</span> <span style="color: #000000;">sk</span> <span style="color: #0000FF;">=</span> <span style="color: #7060A8;">getd_all_keys</span><span style="color: #0000FF;">(</span><span style="color: #000000;">s</span><span style="color: #0000FF;">)</span>
<span style="color: #008080;">for</span> <span style="color: #000000;">i</span><span style="color: #0000FF;">=</span><span style="color: #000000;">1</span> <span style="color: #008080;">to</span> <span style="color: #7060A8;">length</span><span style="color: #0000FF;">(</span><span style="color: #000000;">sk</span><span style="color: #0000FF;">)</span> <span style="color: #008080;">do</span>
<span style="color: #004080;">integer</span> <span style="color: #000000;">node</span> <span style="color: #0000FF;">=</span> <span style="color: #7060A8;">getd_index</span><span style="color: #0000FF;">(</span><span style="color: #000000;">sk</span><span style="color: #0000FF;">[</span><span style="color: #000000;">i</span><span style="color: #0000FF;">],</span><span style="color: #000000;">sums</span><span style="color: #0000FF;">)</span>
<span style="color: #008080;">if</span> <span style="color: #000000;">node</span><span style="color: #0000FF;">!=</span><span style="color: #004600;">NULL</span> <span style="color: #008080;">and</span> <span style="color: #7060A8;">getd_index</span><span style="color: #0000FF;">(</span><span style="color: #000000;">sk</span><span style="color: #0000FF;">[</span><span style="color: #000000;">i</span><span style="color: #0000FF;">]+</span><span style="color: #000000;">v</span><span style="color: #0000FF;">,</span><span style="color: #000000;">s</span><span style="color: #0000FF;">)=</span><span style="color: #004600;">NULL</span> <span style="color: #008080;">then</span>
<span style="color: #7060A8;">setd</span><span style="color: #0000FF;">(</span><span style="color: #000000;">sk</span><span style="color: #0000FF;">[</span><span style="color: #000000;">i</span><span style="color: #0000FF;">]+</span><span style="color: #000000;">v</span><span style="color: #0000FF;">,</span><span style="color: #7060A8;">deep_copy</span><span style="color: #0000FF;">(</span><span style="color: #7060A8;">getd_by_index</span><span style="color: #0000FF;">(</span><span style="color: #000000;">node</span><span style="color: #0000FF;">,</span><span style="color: #000000;">sums</span><span style="color: #0000FF;">))&</span><span style="color: #000000;">w</span><span style="color: #0000FF;">,</span><span style="color: #000000;">s</span><span style="color: #0000FF;">)</span>
<span style="color: #008080;">end</span> <span style="color: #008080;">if</span>
<span style="color: #008080;">end</span> <span style="color: #008080;">for</span>
<span style="color: #7060A8;">destroy_dict</span><span style="color: #0000FF;">(</span><span style="color: #000000;">sums</span><span style="color: #0000FF;">)</span>
<span style="color: #000000;">sums</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">s</span>
<span style="color: #004080;">integer</span> <span style="color: #000000;">node</span> <span style="color: #0000FF;">=</span> <span style="color: #7060A8;">getd_index</span><span style="color: #0000FF;">(</span><span style="color: #000000;">0</span><span style="color: #0000FF;">,</span><span style="color: #000000;">sums</span><span style="color: #0000FF;">)</span>
<span style="color: #008080;">if</span> <span style="color: #000000;">node</span><span style="color: #0000FF;">!=</span><span style="color: #004600;">NULL</span> <span style="color: #008080;">then</span>
<span style="color: #004080;">sequence</span> <span style="color: #000000;">t</span> <span style="color: #0000FF;">=</span> <span style="color: #7060A8;">extract</span><span style="color: #0000FF;">(</span><span style="color: #000000;">weights</span><span style="color: #0000FF;">,</span><span style="color: #7060A8;">getd_by_index</span><span style="color: #0000FF;">(</span><span style="color: #000000;">node</span><span style="color: #0000FF;">,</span><span style="color: #000000;">sums</span><span style="color: #0000FF;">))</span>
<span style="color: #7060A8;">printf</span><span style="color: #0000FF;">(</span><span style="color: #000000;">1</span><span style="color: #0000FF;">,</span><span style="color: #008000;">"Total %d for %v\n"</span><span style="color: #0000FF;">,{</span><span style="color: #7060A8;">sum</span><span style="color: #0000FF;">(</span><span style="color: #000000;">t</span><span style="color: #0000FF;">),</span><span style="color: #000000;">t</span><span style="color: #0000FF;">})</span>
<span style="color: #008080;">exit</span>
<span style="color: #008080;">end</span> <span style="color: #008080;">if</span>
<span style="color: #008080;">end</span> <span style="color: #008080;">for</span>
<!--</syntaxhighlight>-->
{{out}}
<pre>
Total 0 for {-61,32,373,311,249,311,32,-92,-185,-433,-402,-247,156,125,249,32,-464,-278,218,32,-123,-216,373,-185,-402,156,-402,-61,902}
</pre>
=={{header|Picat}}==
Using constraint modelling.
<syntaxhighlight lang="picat">import cp.
%
% Get any solution.
%
go =>
things(Things),
subset_sum(Things, X, Z),
println(z=Z),
println(x=X),
println([Things[I] : I in 1..Things.length, X[I] == 1]),
nl.
%
% Solve subset problem for any length (wrapper).
%
subset_sum(Things, X, Z) =>
subset_sum(Things,_,X,Z).
%
% Solve for a specific length (if Len2 is nonvar).
%
subset_sum(Things, Len2, X, Z) =>
Weights = [ T[2] : T in Things],
Len = Things.length,
X = new_list(Len),
X :: 0..1,
Z #= sum(X),
if nonvar(Len2) then
Z #= Len2
end,
Z #> 0, % require at least one thing
sum([X[I] * Weights[I] : I in 1..Len]) #= 0,
solve($[ff], X).
things(Things) =>
Things = [
[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 ]
].</syntaxhighlight>
{{out}}
<pre>z = 8
x = [0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,1,0,1,0,1,0,1,0,0,1,1,1,1]
[[flatworm,503],[infra,-847],[lindholm,999],[mincemeat,-880],[plugging,-266],[smokescreen,423],[speakeasy,-745],[vein,813]]
</pre>
Some other experiments.
Get a solution - if possible - for a specific number of selected things.
<syntaxhighlight lang="picat">go2 =>
things(Things),
foreach(Len in 1..Things.length)
println(len=Len),
(subset_sum(Things, Len, X, _Z) ->
println([Things[I,1] : I in 1..Things.length, X[I] == 1])
;
true
),
nl
end,
nl.</syntaxhighlight>
{{out}}
<pre>len = 1
len = 2
[archbishop,gestapo]
len = 3
[exorcism,fiat,vein]
len = 4
[exorcism,gestapo,speakeasy,vein]
len = 5
[fiat,infra,lindholm,smokescreen,speakeasy]
len = 6
[exorcism,flatworm,gestapo,isis,plugging,vein]
len = 7
[fiat,flatworm,infra,isis,lindholm,plugging,smokescreen]
len = 8
[flatworm,infra,lindholm,mincemeat,plugging,smokescreen,speakeasy,vein]
len = 9
[exorcism,filmy,flatworm,infra,markham,moresby,plugging,smokescreen,vein]
len = 10
[fiat,filmy,flatworm,gestapo,isis,markham,mincemeat,moresby,mycenae,plugging]
len = 11
[exorcism,fiat,flatworm,gestapo,infra,isis,lindholm,plugging,smokescreen,speakeasy,vein]
len = 12
[eradicate,fiat,infra,isis,lindholm,mincemeat,moresby,mycenae,plugging,smokescreen,speakeasy,vein]
len = 13
[escritoire,fiat,filmy,gestapo,infra,isis,lindholm,markham,mincemeat,moresby,plugging,smokescreen,speakeasy]
len = 14
[escritoire,exorcism,fiat,flatworm,infra,isis,lindholm,mincemeat,moresby,mycenae,plugging,smokescreen,speakeasy,vein]
len = 15
[efferent,elysee,escritoire,exorcism,fiat,filmy,flatworm,infra,isis,lindholm,moresby,mycenae,smokescreen,speakeasy,vein]
len = 16
[diophantine,elysee,eradicate,fiat,filmy,flatworm,infra,isis,lindholm,markham,mincemeat,moresby,mycenae,plugging,speakeasy,vein]
len = 17
[deploy,diophantine,elysee,eradicate,escritoire,exorcism,fiat,filmy,flatworm,infra,isis,lindholm,markham,mincemeat,moresby,speakeasy,vein]
len = 18
[deploy,diophantine,efferent,escritoire,exorcism,fiat,filmy,gestapo,infra,isis,lindholm,markham,mincemeat,mycenae,plugging,smokescreen,speakeasy,vein]
len = 19
[departure,deploy,diophantine,efferent,elysee,eradicate,exorcism,fiat,filmy,flatworm,infra,isis,lindholm,markham,mincemeat,mycenae,smokescreen,speakeasy,vein]
len = 20
[covariate,diophantine,efferent,elysee,eradicate,exorcism,fiat,filmy,flatworm,gestapo,infra,isis,markham,mincemeat,moresby,mycenae,plugging,smokescreen,speakeasy,vein]
len = 21
[cobol,deploy,diophantine,efferent,elysee,eradicate,escritoire,exorcism,fiat,filmy,flatworm,infra,isis,lindholm,markham,mincemeat,mycenae,plugging,smokescreen,speakeasy,vein]
len = 22
[brute,centipede,cobol,covariate,deploy,diophantine,efferent,elysee,escritoire,exorcism,fiat,filmy,flatworm,infra,isis,markham,mincemeat,moresby,plugging,smokescreen,speakeasy,vein]
len = 23
[bonnet,centipede,cobol,departure,deploy,diophantine,efferent,elysee,eradicate,escritoire,exorcism,fiat,filmy,infra,isis,markham,mincemeat,moresby,mycenae,plugging,smokescreen,speakeasy,vein]
len = 24
[archbishop,brute,centipede,cobol,covariate,deploy,diophantine,efferent,elysee,escritoire,exorcism,fiat,filmy,flatworm,gestapo,infra,isis,markham,mincemeat,moresby,plugging,smokescreen,speakeasy,vein]
len = 25
[archbishop,bonnet,centipede,cobol,departure,deploy,diophantine,efferent,elysee,eradicate,escritoire,exorcism,fiat,filmy,gestapo,infra,isis,markham,mincemeat,moresby,mycenae,plugging,smokescreen,speakeasy,vein]
len = 26
[alliance,archbishop,bonnet,brute,centipede,covariate,departure,deploy,efferent,elysee,eradicate,exorcism,fiat,filmy,flatworm,gestapo,infra,isis,lindholm,mincemeat,moresby,mycenae,plugging,smokescreen,speakeasy,vein]
len = 27
[alliance,archbishop,balm,brute,centipede,cobol,covariate,deploy,diophantine,efferent,elysee,eradicate,exorcism,fiat,filmy,flatworm,gestapo,infra,isis,lindholm,mincemeat,moresby,mycenae,plugging,smokescreen,speakeasy,vein]
len = 28
len = 29
len = 30
len = 31</pre>
There are in total 349167 solutions of any number of items (the empty set is not a solution in our book).
<syntaxhighlight lang="picat">go3 =>
things(Things),
Count = count_all(subset_sum(Things, _X, _Z)),
println(count=Count),
nl.
</syntaxhighlight>
=={{header|PicoLisp}}==
<
(alliance . -624) (archbishop . -915) (balm . 397) (bonnet . 452)
(brute . 870) (centipede . -658) (cobol . 362) (covariate . 590)
Line 1,509 ⟶ 2,241:
(infra . -847) (isis . -982) (lindholm . 999) (markham . 475)
(mincemeat . -880) (moresby . 756) (mycenae . 183) (plugging . -266)
(smokescreen . 423) (speakeasy . -745) (vein . 813) )</
Minimal brute force solution:
<
(pick
Line 1,517 ⟶ 2,249:
(find '((L) (=0 (sum cdr L)))
(subsets N *Words) ) )
(range 1 (length *Words)) )</
{{Out}}
<pre>-> ((archbishop . -915) (gestapo . 915))</pre>
Line 1,523 ⟶ 2,255:
=={{header|Python}}==
===Version 1===
<
"alliance": -624, "archbishop": -925, "balm": 397,
"bonnet": 452, "brute": 870, "centipede": -658,
Line 1,557 ⟶ 2,289:
for x in s[-neg]:
print(x, words[x])
break</
{{out}}<pre>
('mycenae', 183)
Line 1,568 ⟶ 2,300:
</pre>
===Brute force===
<
>>>
>>> word2weight = {"alliance": -624, "archbishop": -915, "balm": 397, "bonnet": 452,
Line 1,588 ⟶ 2,320:
>>> answer
[('archbishop', -915), ('gestapo', 915)]</
=={{header|Racket}}==
<
#lang racket
Line 1,626 ⟶ 2,358:
(for ([i (sub1 len)]) (loop l len (add1 i) '() 0)))
(zero-subsets words)
</syntaxhighlight>
{{out}}
<pre>
Line 1,636 ⟶ 2,368:
(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)
</pre>
=={{header|Raku}}==
(formerly Perl 6)
<syntaxhighlight lang="raku" line>my @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;
my @weights = @pairs».value;
my %name = @pairs.hash.invert;
.say for (1..27).hyper(:3batch).map: -> $n {
given @weights.combinations($n).first({ 0 == [+] @^comb }) {
when .so { "Length $n: ({.map: {%name{$_}}})" }
default { "Length $n: (none)" }
}
}</syntaxhighlight>
{{out}}
<pre>Length 1: (none)
Length 2: (archbishop gestapo)
Length 3: (centipede markham mycenae)
Length 4: (alliance balm deploy mycenae)
Length 5: (alliance brute covariate deploy mincemeat)
Length 6: (alliance archbishop balm deploy gestapo mycenae)
Length 7: (alliance archbishop bonnet cobol departure exorcism moresby)
Length 8: (alliance archbishop balm bonnet fiat flatworm isis lindholm)
Length 9: (alliance archbishop balm bonnet brute covariate eradicate mincemeat plugging)
Length 10: (alliance archbishop balm bonnet brute centipede cobol departure deploy mincemeat)
Length 11: (alliance archbishop balm bonnet brute centipede cobol departure infra moresby speakeasy)
Length 12: (alliance archbishop balm bonnet brute centipede cobol covariate diophantine efferent elysee infra)
Length 13: (alliance archbishop balm bonnet brute centipede cobol covariate departure efferent eradicate filmy isis)
Length 14: (alliance archbishop balm bonnet brute centipede cobol covariate departure deploy elysee filmy markham speakeasy)
Length 15: (alliance archbishop balm bonnet brute centipede cobol covariate departure deploy elysee exorcism flatworm infra mycenae)
Length 16: (alliance archbishop balm bonnet brute centipede cobol covariate departure deploy diophantine elysee exorcism filmy gestapo infra)
Length 17: (alliance archbishop balm bonnet brute centipede cobol covariate departure deploy diophantine exorcism isis mincemeat mycenae plugging vein)
Length 18: (alliance archbishop balm bonnet brute centipede cobol covariate departure deploy diophantine efferent elysee exorcism filmy isis mycenae vein)
Length 19: (alliance archbishop balm bonnet brute centipede cobol covariate departure deploy diophantine efferent elysee eradicate exorcism fiat infra isis smokescreen)
Length 20: (alliance archbishop balm bonnet brute centipede cobol covariate departure deploy diophantine efferent elysee eradicate exorcism gestapo infra isis smokescreen speakeasy)
Length 21: (alliance archbishop balm bonnet brute centipede cobol covariate departure deploy diophantine efferent elysee eradicate exorcism flatworm infra lindholm mincemeat plugging speakeasy)
Length 22: (alliance archbishop balm bonnet brute centipede cobol covariate departure deploy diophantine efferent elysee eradicate escritoire exorcism fiat filmy flatworm mincemeat plugging speakeasy)
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)
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)
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)
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)
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)</pre>
=={{header|REXX}}==
Line 1,645 ⟶ 2,426:
<br>which "chunk" to search for solutions (that is, out of the 31 names, take a "chunk" at a time).
Added was "que pasa" informational messages. The sum (which is zero for this task) can be any number,
<br>
<
parse arg target stopAt chunkette . /*option optional arguments from the CL*/
if target=='' | target=="," then target= 0 /*Not specified? Then use the default.*/
if stopAt=='' | stopAt=="," then stopAt= 1 /* " " " " " " */
y= 0
@.= 0
end /*N*/
call eSort N /*sort the names with weights. */
Line 1,680 ⟶ 2,456:
call tello center(' doing chunk:' chunk" ", 79, '─')
call combN N, chunk /*N items, a CHUNK at a time. */
_= ??
if _==0 then _= 'No' /*Englishise _ for a zero count. */
call tello _ 'solution's(??) "found so far."
end /*chunk*/
Line 1,689 ⟶ 2,466:
/*──────────────────────────────────────────────────────────────────────────────────────*/
combN: procedure expose @. #. ?? stopAt target; parse arg x,y; !.= @.0
base= x + 1;
do n=1 for y; !.n=n /*construct the first combination. */
end /*n*/
ym= y - 1
do j=1; _= !.1;
if s>target then leave /*Is 1st dig>target? Then we're done.*/
do k=2 for ym; _= !.k; s= s + #._ /*Σ the weights; is sum > target ? */
Line 1,699 ⟶ 2,476:
end /*k*/
if s==target then call telly /*have we found a pot of gold? */
!.y= !.y + 1;
end /*j*/;
/*──────────────────────────────────────────────────────────────────────────────────────*/
.combUp: procedure expose !. y bbase;
p= !.d; do u=d to y; !.u= p + 1
if !.u >= bbase+u then return .combUp(u-1)
p= !.u /*P will be used for the next digt. */
end /*u*/; return 0 /*go back and sum this combination. */
/*──────────────────────────────────────────────────────────────────────────────────────*/
eSort: procedure expose #. @. $.; parse arg N,$; h= N
do while h>1; h= h % 2
do i=1 for N-h; j= i;
if $==. then do while $.k<$.j; parse value $.j $.k with $.k $.j
if h>=j then leave; j= j - h;
end /*while $.k<$.j*/
else do while #.k<#.j; parse value @.j @.k #.j #.k with @.k @.j #.k #.j
if h>=j then leave; j= j - h;
end /*while #.k<#.j*/
end /*i*/
end /*while h>1*/; return
/*──────────────────────────────────────────────────────────────────────────────────────*/
s: if arg(1)==1 then return arg(3); return word(arg(2) 's', 1)
tello: parse arg _,e; if e==. then say; say _; call lineout 'SUBSET.'y, _; return
/*──────────────────────────────────────────────────────────────────────────────────────*/
telly: ??= ?? + 1; nameL=
do gi=1 for y;
$.gi= @.ggg
end /*gi*/
call eSort y, . /*sort the names alphabetically. */
do gs=1 for y; nameL= nameL $.gs /*build a list of names whose sum = 0 */
Line 1,740 ⟶ 2,517:
call tello
call tello 'There are ' N " entries in the (above)" arg(1) 'table.'
call tello; return</
Output note: this program also writes the displayed output to file(s): SUBSET.nnn
<br> ──────── where nnn is the ''chunk'' number.
Line 1,747 ⟶ 2,524:
(The above arguments set the target sum to zero, and limits the finding of a dozen solutions.)
<pre>
[1] exorcism -983
[2] isis -982
Line 1,806 ⟶ 2,583:
=={{header|Ring}}==
<
# Project : Subset sum problem
Line 1,887 ⟶ 2,664:
next
return alist
</syntaxhighlight>
Output:
<pre>
Line 1,900 ⟶ 2,677:
=={{header|Ruby}}==
a brute force solution:
<
'alliance' =>-624, 'archbishop'=>-915, 'balm' => 397, 'bonnet' => 452,
'brute' => 870, 'centipede' =>-658, 'cobol' => 362, 'covariate'=> 590,
Line 1,922 ⟶ 2,699:
puts "no subsets of length #{n} sum to zero"
end
end</
{{out}}
Line 1,960 ⟶ 2,737:
=={{header|Scala}}==
{{Out}}Best seen running in your browser by [https://scastie.scala-lang.org/KnhJimmSTL6QXIGTAdZjBQ Scastie (remote JVM)].
<
private val LIMIT = 5
private val n = items.length
Line 2,022 ⟶ 2,799:
zeroSum(0, 0)
}</
=={{header|Sidef}}==
<
alliance => -624, archbishop => -915,
brute => 870, centipede => -658,
Line 2,056 ⟶ 2,834:
})
found || say "Length #{n}: (none)"
}</
{{out}}
<pre style="height: 40ex; overflow: scroll">
Line 2,092 ⟶ 2,870:
=={{header|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.
<
if {$size <= 0} {
return
Line 2,118 ⟶ 2,896:
# Nothing was found
return -code error "no subset sums to zero"
}</
Demonstrating:
<
alliance -624
archbishop -915
Line 2,154 ⟶ 2,932:
}
set zsss [searchForSubset $wordweights]
puts "Found zero-summing subset: [join [lsort $zsss] {, }]"</
{{Out}}
<pre>
Line 2,162 ⟶ 2,940:
=={{header|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.
<
#import int
Line 2,204 ⟶ 2,982:
#cast %zm
main = nullset weights</
The name of the function that takes the weighted set is <code>nullset</code>. 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:
* <code>=><></code> fold right combinator with the empty list as the vacuuous case
Line 2,225 ⟶ 3,003:
'smokescreen': 423,
'speakeasy': -745>
</pre>
=={{header|Wren}}==
{{trans|Kotlin}}
<syntaxhighlight lang="wren">import "./fmt" for Fmt
class Item {
construct new(word, weight) {
_word = word
_weight = weight
}
word { _word }
weight { _weight }
toString {Fmt.swrite("$-11s $4d", _word, _weight) }
}
var items = [
Item.new("alliance", -624),
Item.new("archbishop", -915),
Item.new("balm", 397),
Item.new("bonnet", 452),
Item.new("brute", 870),
Item.new("centipede", -658),
Item.new("cobol", 362),
Item.new("covariate", 590),
Item.new("departure", 952),
Item.new("deploy", 44),
Item.new("diophantine", 645),
Item.new("efferent", 54),
Item.new("elysee", -326),
Item.new("eradicate", 376),
Item.new("escritoire", 856),
Item.new("exorcism", -983),
Item.new("fiat", 170),
Item.new("filmy", -874),
Item.new("flatworm", 503),
Item.new("gestapo", 915),
Item.new("infra", -847),
Item.new("isis", -982),
Item.new("lindholm", 999),
Item.new("markham", 475),
Item.new("mincemeat", -880),
Item.new("moresby", 756),
Item.new("mycenae", 183),
Item.new("plugging", -266),
Item.new("smokescreen", 423),
Item.new("speakeasy", -745),
Item.new("vein", 813)
]
var n = items.count
var indices = List.filled(n, 0)
var count = 0
var LIMIT = 5
var zeroSum // recursive
zeroSum = Fn.new { |i, w|
if (i != 0 && w == 0) {
for (j in 0...i) System.print("%(items[indices[j]]) ")
System.print()
if (count < LIMIT) {
count = count + 1
} else {
return
}
}
var k = (i != 0) ? indices[i-1] + 1 : 0
var j = k
while (j < n) {
indices[i] = j
zeroSum.call(i + 1, w + items[j].weight)
if (count == LIMIT) return
j = j + 1
}
}
System.print("The weights of the following %(LIMIT) subsets add up to zero:\n")
zeroSum.call(0, 0)</syntaxhighlight>
{{out}}
<pre style="height: 90ex; overflow: scroll">
The weights of the following 5 subsets add up to zero:
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
mincemeat -880
plugging -266
speakeasy -745
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
infra -847
isis -982
mincemeat -880
moresby 756
mycenae 183
smokescreen 423
speakeasy -745
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
fiat 170
infra -847
isis -982
markham 475
mincemeat -880
plugging -266
speakeasy -745
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
exorcism -983
fiat 170
infra -847
isis -982
mincemeat -880
moresby 756
plugging -266
vein 813
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
exorcism -983
fiat 170
infra -847
isis -982
smokescreen 423
</pre>
=={{header|XPL0}}==
{{trans|C}}
<syntaxhighlight lang "XPL0">include xpllib; \for Print
def \Items\ Wd, Wt;
def N = 31;
int Set(N), Items;
proc SubSum(I, Weight);
int I, Weight, J;
[if I#0 & Weight=0 then
[for J:= 0 to I-1 do
Print("%s%s", if J then " " else "", Items(Set(J),Wd));
Print("\n");
exit;
];
for J:= if I#0 then Set(I-1)+1 else 0 to N-1 do
[Set(I):= J;
SubSum(I+1, Weight+Items(J,Wt));
];
];
[Items:= [
["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] ];
SubSum(0, 0);
]</syntaxhighlight>
{{out}}
<pre>
alliance archbishop balm bonnet brute centipede cobol covariate departure deploy diophantine efferent elysee eradicate escritoire exorcism fiat filmy flatworm mincemeat plugging speakeasy
</pre>
=={{header|zkl}}==
{{trans|C}}
<
T("alliance", -624), T("archbishop", -915), T("balm", 397),
T("bonnet", 452), T("brute", 870), T("centipede", -658),
Line 2,255 ⟶ 3,290:
set:=List.createLong(items.len(),0);
try{ subSum(set,0,0); }catch(TheEnd){}</
{{out}}
<pre>
|