Rosetta Code

Subset sum problem: Difference between revisions

Page Discussion

Subset sum problem (view source)

Revision as of 11:39, 11 April 2022

19,127 bytes added ,  2 years ago
m
→‎{{header|Phix}}: syntax coloured, made p2js compatible
(Added solution for Action!)
m (→‎{{header|Phix}}: syntax coloured, made p2js compatible)
Line 1,918:
=={{header|Phix}}==
Simple Brute force
<!--<lang Phix>(phixonline)-->
<lang Phix>sequence {words,weights} = columnize({{"alliance", -624},
<span style="color: #008080;">with</span> <span style="color: #008080;">javascript_semantics</span>
{"archbishop", -915},
<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>
{"balm", 397},
<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>
{"bonnet", 452},
<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>
{"brute", 870},
<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>
{"centipede", -658},
<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>
{"cobol", 362},
<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>
{"covariate", 590},
<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>
{"departure", 952},
<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>
{"deploy", 44},
<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>
{"diophantine", 645},
<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>
{"efferent", 54},
<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>
{"elysee", -326},
{"eradicate", 376},
<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>
{"escritoire", 856},
<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>
{"exorcism", -983},
<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>
{"fiat", 170},
<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>
{"filmy", -874},
<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>
{"flatworm", 503},
<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>
{"gestapo", 915},
<span style="color: #008080;">return</span> <span style="color: #004600;">true</span>
{"infra", -847},
<span style="color: #008080;">end</span> <span style="color: #008080;">if</span>
{"isis", -982},
<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>
{"lindholm", 999},
<span style="color: #000080;font-style:italic;">-- get all combinations with and without the next item:</span>
{"markham", 475},
<span style="color: #000000;">done</span> <span style="color: #0000FF;">+=</span> <span style="color: #000000;">1</span>
{"mincemeat", -880},
<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>
{"moresby", 756},
<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>
{"mycenae", 183},
<span style="color: #008080;">return</span> <span style="color: #004600;">true</span>
{"plugging", -266},
<span style="color: #008080;">end</span> <span style="color: #008080;">if</span>
{"smokescreen", 423},
<span style="color: #008080;">end</span> <span style="color: #008080;">if</span>
{"speakeasy", -745},
<span style="color: #008080;">return</span> <span style="color: #004600;">false</span>
{"vein", 813}})
<span style="color: #008080;">end</span> <span style="color: #008080;">function</span>
 
function comb(sequence pool, integer needed, done=0, sequence chosen={})
<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>
if needed=0 then -- got a full set
<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>
integer t = 0
<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>
for i=1 to length(chosen) do
<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>
t += weights[chosen[i]]
<span style="color: #008080;">end</span> <span style="color: #008080;">if</span>
end for
<span style="color: #008080;">end</span> <span style="color: #008080;">for</span>
if t=0 then
<!--</lang>-->
for i=1 to length(chosen) do
chosen[i] = words[chosen[i]]
end for
printf(1,"%d: %s\n",{length(chosen),sprint(chosen)})
return 1
end if
elsif done+needed<=length(pool) then
-- get all combinations with and without the next item:
done += 1
if comb(pool,needed-1,done,append(chosen,pool[done]))
or comb(pool,needed,done,chosen) then
return 1
end if
end if
return 0
end function
 
integer n = length(weights)
for i=1 to n do
if comb(tagset(n),i)=0 then
printf(1,"%d: No zero-sum subsets of that length\n",{i})
end if
end for</lang>
{{out}}
<pre>
1: No zero-sum subsets of that length
1: No zero-sum subsets of that length
2: {"archbishop" archbishop,"gestapo"}
3: {"centipede" centipede,"markham","mycenae"}
4: {"alliance" alliance,"balm","deploy","mycenae"}
5: {"alliance" alliance,"brute","covariate","deploy","mincemeat"}
6: {"alliance" alliance,"archbishop","balm","deploy","gestapo","mycenae"}
7: {"alliance" alliance,"archbishop","bonnet","cobol","departure","exorcism","moresby"}
8: {"alliance" alliance,"archbishop","balm","bonnet","fiat","flatworm","isis","lindholm"}
9: {"alliance" alliance,"archbishop","balm","bonnet","brute","covariate","eradicate","mincemeat","plugging"}
10: {"alliance" alliance,"archbishop","balm","bonnet","brute","centipede","cobol","departure","deploy","mincemeat"}
11: {"alliance" alliance,"archbishop","balm","bonnet","brute"...,"centipede","cobol","departure","infra","moresby","speakeasy"}, (11 items)
12: {"alliance" alliance,"archbishop","balm","bonnet","brute"...,"centipede","cobol","covariate","diophantine","efferent","elysee","infra"}, (12 items)
13: {"alliance" alliance,"archbishop","balm","bonnet","brute"...,"centipede","cobol","covariate","departure","efferent","eradicate","filmy","isis"}, (13 items)
14: {"alliance" alliance,"archbishop","balm","bonnet","brute"...,"centipede","cobol","covariate","departure","deploy","elysee","filmy","markham","speakeasy"}, (14 items)
15: {"alliance" alliance,"archbishop","balm","bonnet","brute"...,"centipede","cobol","covariate","departure","deploy","elysee","exorcism","flatworm","infra","mycenae"}, (15 items)
16: {"alliance" alliance,"archbishop","balm","bonnet","brute"...,"centipede","cobol","covariate","departure","deploy","diophantine","elysee","exorcism","filmy","gestapo","infra"}, (16 items)
17: {"alliance" alliance,"archbishop","balm","bonnet","brute"...,"centipede","cobol","covariate","departure","deploy","diophantine","exorcism","isis","mincemeat","mycenae","plugging","vein"}, (17 items)
18: {"alliance" alliance,"archbishop","balm","bonnet","brute"...,"centipede","cobol","covariate","departure","deploy","diophantine","efferent","elysee","exorcism","filmy","isis","mycenae","vein"}, (18 items)
19: {"alliance" alliance,"archbishop","balm","bonnet","brute"...,"centipede","cobol","covariate","departure","deploy","diophantine","efferent","elysee","eradicate","exorcism","fiat","infra","isis","smokescreen"}, (19 items)
20: {"alliance" alliance,"archbishop","balm","bonnet","brute"...,"centipede","cobol","covariate","departure","deploy","diophantine","efferent","elysee","eradicate","exorcism","gestapo","infra","isis","smokescreen","speakeasy"}, (20 items)
21: {"alliance" alliance,"archbishop","balm","bonnet","brute"...,"centipede","cobol","covariate","departure","deploy","diophantine","efferent","elysee","eradicate","exorcism","flatworm","infra","lindholm","mincemeat","plugging","speakeasy"}, (21 items)
22: {"alliance" alliance,"archbishop","balm","bonnet","brute"...,"centipede","cobol","covariate","departure","deploy","diophantine","efferent","elysee","eradicate","escritoire","exorcism","fiat","filmy","flatworm","mincemeat","plugging","speakeasy"}, (22 items)
23: {"alliance" alliance,"archbishop","balm","bonnet","brute"...,"centipede","cobol","covariate","departure","deploy","diophantine","efferent","elysee","eradicate","escritoire","exorcism","infra","isis","mincemeat","moresby","mycenae","smokescreen","speakeasy"}, (23 items)
24: {"alliance" alliance,"archbishop","balm","bonnet","brute"...,"centipede","cobol","covariate","departure","deploy","diophantine","efferent","elysee","exorcism","filmy","gestapo","infra","markham","mincemeat","moresby","mycenae","plugging","smokescreen","speakeasy"}, (24 items)
25: {"alliance" 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"}, (25 items)
26: {"alliance" 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"}, (26 items)
27: {"alliance" 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"}, (27 items)
28: No zero-sum subsets of that length
28: No zero-sum subsets of that length
29: No zero-sum subsets of that length
29: No zero-sum subsets of that length
30: No zero-sum subsets of that length
30: No zero-sum subsets of that length
31: 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, (modified to omit words and
using a dictionary so that fractional weights can be accomodated).<br>
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.<br>
This is significantly faster (near instant, in fact) than an "all possible combinations" approach.
Note that new_dict(tid) has been introduced for this task in 0.8.0, which has not yet been shipped.
 
Shows the first zero-sum subset found, only.
<!--<lang Phix>(phixonline)-->
<lang Phix>constant weights = {-61, 1, 32, 373, 311, 249, 311, 32, -92, -185, -433,
<span style="color: #008080;">with</span> <span style="color: #008080;">javascript_semantics</span>
-402, -247, 156, 125, 249, 32, -464, -278, 218, 32,
<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>
-123, -216, 373, -185, -402, 156, -402, -61, -31, 902 }
<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>
integer sums = new_dict()
 
for w=1 to length(weights) do
-- 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).
integer s = new_dict(sums)
atom v = weights[w]
if getd_index(v,s)=NULL then setd(v,{w},s) end if
<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>
sequence sk = getd_all_keys(s)
for i=1 to length(sk) do
<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>
integer node = getd_index(sk[i],sums)
<span style="color: #000080;font-style:italic;">-- make a separate modifiable copy of sums, otherwise
if node!=NULL and getd_index(sk[i]+v,s)=0 then
-- it c/would mark sums[weights[w]*{2,3,etc}] as valid,
setd(sk[i]+v,getd_by_index(node,sums)&w,s)
-- ie there cannot be any w in the getd_by_index(node).</span>
end if
<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>
end for
<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>
destroy_dict(sums)
<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>
sums = s
 
<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>
integer node = getd_index(0,sums)
<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>
if node!=0 then
<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>
sequence s0 = getd_by_index(node,sums)
<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>
atom t = 0 -- (sanity check)
<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>
for i=1 to length(s0) do
<span style="color: #008080;">end</span> <span style="color: #008080;">if</span>
integer si = s0[i]
<span style="color: #008080;">end</span> <span style="color: #008080;">for</span>
t += weights[si]
<span style="color: #7060A8;">destroy_dict</span><span style="color: #0000FF;">(</span><span style="color: #000000;">sums</span><span style="color: #0000FF;">)</span>
s0[i] = weights[si]
<span style="color: #000000;">sums</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">s</span>
end for
printf(1,"Total %d for %s\n",{t,sprint(s0)})
<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>
exit
<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>
end if
<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>
end for</lang>
<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>
<!--</lang>-->
{{out}}
<pre>
Petelomax
7,805

edits

Retrieved from "https://rosettacode.org/wiki/Special:MobileDiff/210681"