Subset sum problem: Difference between revisions
m
→{{header|Wren}}: Minor tidy
m (→{{header|Wren}}: Minor tidy) |
|||
(7 intermediate revisions by 7 users not shown) | |||
Line 95:
{{trans|Python}}
<
‘alliance’ = -624, ‘archbishop’ = -925, ‘balm’ = 397,
‘bonnet’ = 452, ‘brute’ = 870, ‘centipede’ = -658,
Line 133:
L(x) s[-neg]
print(x‘ ’words[x])
L.break</
{{out}}
Line 145:
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 203 ⟶ 333:
end loop;
end loop;
end SubsetSum;</
{{out}}
<pre>2: archbishop gestapo
Line 233 ⟶ 363:
=={{header|C}}==
<
#include <stdlib.h>
Line 297 ⟶ 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
Line 304 ⟶ 434:
=={{header|C sharp|C#}}==
{{trans|Java}}
<
using System.Collections.Generic;
Line 385 ⟶ 515:
}
}
}</
{{out}}
<pre>The weights of the following 5 subsets add up to zero:
Line 401 ⟶ 531:
=={{header|C++}}==
{{trans|C#}}
<
#include <vector>
Line 468 ⟶ 598:
subsum(0, 0);
return 0;
}</
{{out}}
<pre>alliance archbishop balm bonnet brute centipede cobol covariate departure deploy diophantine efferent elysee eradicate escritoire exorcism fiat filmy flatworm mincemeat plugging speakeasy
Line 479 ⟶ 609:
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 502 ⟶ 632:
comb.map!q{ a[0] });
"No solution found.".writeln;
}</
{{out}}
<pre>A subset of length 2: archbishop, gestapo</pre>
Line 509 ⟶ 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 605 ⟶ 735:
writeln("Zero sums: ", sols);
}</
{{out}}
<pre>Zero sums: 349167</pre>
Line 613 ⟶ 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 660 ⟶ 790:
(map (lambda(i) (first (list-ref input i))) (fillQ (map rest input))))
</syntaxhighlight>
{{out}}
<pre>
Line 715 ⟶ 845:
===Brute force===
We use the '''powerset''' procrastinator which gives in sequence all subsets of the input list.
<
(lib 'sequences) ;; for powerset
Line 742 ⟶ 872:
("deploy" . 44) ("diophantine" . 645) ("efferent" . 54)
("elysee" . -326) ("eradicate" . 376))
</syntaxhighlight>
=={{header|FunL}}==
<
def sumset( a ) = foldl1( (+), map(w, a) )
Line 789 ⟶ 919:
for i <- 0..5
println( i, subsetSum(s, snd, i).get() )</
{{out}}
Line 803 ⟶ 933:
=={{header|Go}}==
<
import "fmt"
Line 869 ⟶ 999:
}
fmt.Println("no subset sums to 0")
}</
{{out}}
<pre>
Line 885 ⟶ 1,015:
=={{header|Haskell}}==
<
combinations 0 _ = [[]]
combinations _ [] = []
Line 916 ⟶ 1,046:
W "vein" 813]
main = print $ map word $ head $ solver items</
{{out}}
<pre>["archbishop","gestapo"]</pre>
Non brute-force: the list of numbers used here are different, and difficult for a bruteforce method.
<
subsum w =
snd . head . filter ((== w) . fst) . (++ [(w, [])]) . foldl s [(0, [])]
Line 943 ⟶ 1,073:
main :: IO ()
main = print $ subsum 0 items</
{{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>
Line 949 ⟶ 1,079:
=={{header|Icon}} and {{header|Unicon}}==
{{trans|Ruby}}
<
procedure main()
Line 994 ⟶ 1,124:
return T
end</
{{libheader|Icon Programming Library}}
Line 1,036 ⟶ 1,166:
Task data:
<
alliance -624
archbishop -915
Line 1,071 ⟶ 1,201:
words=:{.@;:;._2 text
numbs=:+/|:0&".;._2 text</
Implementation:
<
p=:(#~ 0&<)y
n=:(#~ 0&>)y
Line 1,084 ⟶ 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 1,102 ⟶ 1,232:
=={{header|Java}}==
{{trans|Kotlin}}
<
private static class Item {
private String word;
Line 1,179 ⟶ 1,309:
zeroSum(0, 0);
}
}</
{{out}}
<pre>The weights of the following 5 subsets add up to zero:
Line 1,196 ⟶ 1,326:
{{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
# map( [null, .] ) | combinations | map(select(.));
if length == 0
then .
else .[0] as $x
| .[1:] | selections | ., ([$x] + .)
end ;
# input: a JSON object giving the weights
Line 1,218 ⟶ 1,343:
. as $dict
|
</syntaxhighlight>
'''An Example'''
<
{
"alliance": -624,
Line 1,256 ⟶ 1,381:
};
weights | first(zero_sums)</
{{out}}
<pre>
[
"
"
"
"
"
"
"
"
"elysee"
]
</pre>
=={{header|Julia}}==
<
const pairs = [
Line 1,304 ⟶ 1,428:
zerosums()
</
<pre>
For length 1: None
Line 1,343 ⟶ 1,467:
=={{header|Kotlin}}==
{{trans|C}}
<
class Item(val word: String, val weight: Int) {
Line 1,406 ⟶ 1,530:
println("The weights of the following $LIMIT subsets add up to zero:\n")
zeroSum(0, 0)
}</
{{out}}
Line 1,423 ⟶ 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,433 ⟶ 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,446 ⟶ 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,480 ⟶ 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,498 ⟶ 1,622:
=={{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};
Line 1,505 ⟶ 1,629:
var int: wSelected=sum(n in selected)(weight[n]);
constraint wSelected=0;
</syntaxhighlight>
{{out}}
<pre>
Line 1,513 ⟶ 1,637:
</pre>
=={{header|Modula-2}}==
<
FROM FormatString IMPORT FormatString;
FROM Terminal IMPORT WriteString,WriteLn,ReadChar;
Line 1,614 ⟶ 1,738:
ReadChar;
END SubsetSum.</
=={{header|Nim}}==
{{libheader|itertools}}
We need the third party module "itertools" to compute the combinations.
<
import itertools
Line 1,668 ⟶ 1,792:
echo &"For length {lg}, found for example: ", comb.mapIt(words[it]).join(" ")
break checkCombs
echo &"For length {lg}, no set found."</
{{out}}
Line 1,707 ⟶ 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,741 ⟶ 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,765 ⟶ 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,781 ⟶ 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,790 ⟶ 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,948 ⟶ 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,956 ⟶ 2,249:
(find '((L) (=0 (sum cdr L)))
(subsets N *Words) ) )
(range 1 (length *Words)) )</
{{Out}}
<pre>-> ((archbishop . -915) (gestapo . 915))</pre>
Line 1,962 ⟶ 2,255:
=={{header|Python}}==
===Version 1===
<
"alliance": -624, "archbishop": -925, "balm": 397,
"bonnet": 452, "brute": 870, "centipede": -658,
Line 1,996 ⟶ 2,289:
for x in s[-neg]:
print(x, words[x])
break</
{{out}}<pre>
('mycenae', 183)
Line 2,007 ⟶ 2,300:
</pre>
===Brute force===
<
>>>
>>> word2weight = {"alliance": -624, "archbishop": -915, "balm": 397, "bonnet": 452,
Line 2,027 ⟶ 2,320:
>>> answer
[('archbishop', -915), ('gestapo', 915)]</
=={{header|Racket}}==
<
#lang racket
Line 2,065 ⟶ 2,358:
(for ([i (sub1 len)]) (loop l len (add1 i) '() 0)))
(zero-subsets words)
</syntaxhighlight>
{{out}}
<pre>
Line 2,078 ⟶ 2,371:
=={{header|Raku}}==
(formerly Perl 6)
<syntaxhighlight lang="raku"
alliance => -624, archbishop => -915, balm => 397, bonnet => 452,
brute => 870, centipede => -658, cobol => 362, covariate => 590,
Line 2,095 ⟶ 2,388:
default { "Length $n: (none)" }
}
}</
{{out}}
<pre>Length 1: (none)
Line 2,135 ⟶ 2,428:
Added was "que pasa" informational messages. The sum (which is zero for this task) can be any number,
<br>and can be specifiable on the command line.
<
parse arg target stopAt chunkette . /*option optional arguments from the CL*/
if target=='' | target=="," then target= 0 /*Not specified? Then use the default.*/
Line 2,224 ⟶ 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 2,290 ⟶ 2,583:
=={{header|Ring}}==
<
# Project : Subset sum problem
Line 2,371 ⟶ 2,664:
next
return alist
</syntaxhighlight>
Output:
<pre>
Line 2,384 ⟶ 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 2,406 ⟶ 2,699:
puts "no subsets of length #{n} sum to zero"
end
end</
{{out}}
Line 2,444 ⟶ 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,506 ⟶ 2,799:
zeroSum(0, 0)
}</
=={{header|Sidef}}==
<
alliance => -624, archbishop => -915,
brute => 870, centipede => -658,
Line 2,541 ⟶ 2,834:
})
found || say "Length #{n}: (none)"
}</
{{out}}
<pre style="height: 40ex; overflow: scroll">
Line 2,577 ⟶ 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,603 ⟶ 2,896:
# Nothing was found
return -code error "no subset sums to zero"
}</
Demonstrating:
<
alliance -624
archbishop -915
Line 2,639 ⟶ 2,932:
}
set zsss [searchForSubset $wordweights]
puts "Found zero-summing subset: [join [lsort $zsss] {, }]"</
{{Out}}
<pre>
Line 2,647 ⟶ 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,689 ⟶ 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,714 ⟶ 3,007:
=={{header|Wren}}==
{{trans|Kotlin}}
<
class Item {
Line 2,789 ⟶ 3,082:
System.print("The weights of the following %(LIMIT) subsets add up to zero:\n")
zeroSum.call(0, 0)</
{{out}}
Line 2,907 ⟶ 3,200:
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,937 ⟶ 3,290:
set:=List.createLong(items.len(),0);
try{ subSum(set,0,0); }catch(TheEnd){}</
{{out}}
<pre>
|