Subset sum problem: Difference between revisions

=={{header|Phix}}==

Simple Brute force

<lang Phix>sequence {words,weights} = columnize({{"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}})

function comb(sequence pool, integer needed, done=0, sequence chosen={})

if needed=0 then -- got a full set

integer t = 0

for i=1 to length(chosen) do

t += weights[chosen[i]]

end for

if t=0 then

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

2: {"archbishop","gestapo"}

3: {"centipede","markham","mycenae"}

4: {"alliance","balm","deploy","mycenae"}

5: {"alliance","brute","covariate","deploy","mincemeat"}

6: {"alliance","archbishop","balm","deploy","gestapo","mycenae"}

7: {"alliance","archbishop","bonnet","cobol","departure","exorcism","moresby"}

8: {"alliance","archbishop","balm","bonnet","fiat","flatworm","isis","lindholm"}

9: {"alliance","archbishop","balm","bonnet","brute","covariate","eradicate","mincemeat","plugging"}

10: {"alliance","archbishop","balm","bonnet","brute","centipede","cobol","departure","deploy","mincemeat"}

11: {"alliance","archbishop","balm","bonnet","brute","centipede","cobol","departure","infra","moresby","speakeasy"}

12: {"alliance","archbishop","balm","bonnet","brute","centipede","cobol","covariate","diophantine","efferent","elysee","infra"}

13: {"alliance","archbishop","balm","bonnet","brute","centipede","cobol","covariate","departure","efferent","eradicate","filmy","isis"}

14: {"alliance","archbishop","balm","bonnet","brute","centipede","cobol","covariate","departure","deploy","elysee","filmy","markham","speakeasy"}

15: {"alliance","archbishop","balm","bonnet","brute","centipede","cobol","covariate","departure","deploy","elysee","exorcism","flatworm","infra","mycenae"}

16: {"alliance","archbishop","balm","bonnet","brute","centipede","cobol","covariate","departure","deploy","diophantine","elysee","exorcism","filmy","gestapo","infra"}

17: {"alliance","archbishop","balm","bonnet","brute","centipede","cobol","covariate","departure","deploy","diophantine","exorcism","isis","mincemeat","mycenae","plugging","vein"}

18: {"alliance","archbishop","balm","bonnet","brute","centipede","cobol","covariate","departure","deploy","diophantine","efferent","elysee","exorcism","filmy","isis","mycenae","vein"}

19: {"alliance","archbishop","balm","bonnet","brute","centipede","cobol","covariate","departure","deploy","diophantine","efferent","elysee","eradicate","exorcism","fiat","infra","isis","smokescreen"}

20: {"alliance","archbishop","balm","bonnet","brute","centipede","cobol","covariate","departure","deploy","diophantine","efferent","elysee","eradicate","exorcism","gestapo","infra","isis","smokescreen","speakeasy"}

21: {"alliance","archbishop","balm","bonnet","brute","centipede","cobol","covariate","departure","deploy","diophantine","efferent","elysee","eradicate","exorcism","flatworm","infra","lindholm","mincemeat","plugging","speakeasy"}

22: {"alliance","archbishop","balm","bonnet","brute","centipede","cobol","covariate","departure","deploy","diophantine","efferent","elysee","eradicate","escritoire","exorcism","fiat","filmy","flatworm","mincemeat","plugging","speakeasy"}

23: {"alliance","archbishop","balm","bonnet","brute","centipede","cobol","covariate","departure","deploy","diophantine","efferent","elysee","eradicate","escritoire","exorcism","infra","isis","mincemeat","moresby","mycenae","smokescreen","speakeasy"}

24: {"alliance","archbishop","balm","bonnet","brute","centipede","cobol","covariate","departure","deploy","diophantine","efferent","elysee","exorcism","filmy","gestapo","infra","markham","mincemeat","moresby","mycenae","plugging","smokescreen","speakeasy"}

25: {"alliance","archbishop","balm","bonnet","brute","centipede","cobol","covariate","departure","deploy","diophantine","eradicate","exorcism","fiat","filmy","flatworm","infra","isis","lindholm","markham","mincemeat","moresby","mycenae","plugging","speakeasy"}

26: {"alliance","archbishop","balm","bonnet","brute","centipede","cobol","covariate","departure","deploy","diophantine","elysee","eradicate","escritoire","exorcism","fiat","filmy","gestapo","infra","isis","markham","mincemeat","mycenae","plugging","speakeasy","vein"}

27: {"alliance","archbishop","balm","bonnet","brute","centipede","covariate","departure","deploy","efferent","elysee","eradicate","escritoire","exorcism","fiat","filmy","flatworm","infra","isis","lindholm","markham","mincemeat","moresby","mycenae","plugging","smokescreen","speakeasy"}

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 (modified to omit words and

using dictionary so that fractional weights can be accomodated).<br>

This is significantly faster (near instant, in fact) than an "all possible combinations" approach.<br>

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>constant weights = {-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 }

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

sequence sk = getd_all_keys(s)

for i=1 to length(sk) do

integer node = getd_index(sk[i],sums)

if node!=NULL and getd_index(sk[i]+v,s)=0 then

setd(sk[i]+v,getd_by_index(node,sums)&w,s)

end if

end for

destroy_dict(sums)

sums = s

integer node = getd_index(0,sums)

if node!=0 then

sequence s0 = getd_by_index(node,sums)

atom t = 0 -- (sanity check)

for i=1 to length(s0) do

integer si = s0[i]

t += weights[si]

s0[i] = weights[si]

end for

printf(1,"Total %d for %s\n",{t,sprint(s0)})

exit

end if

end for</lang>

{{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>