Subset sum problem: Difference between revisions
J
(Show a non-brute-force Mathematica solution.) |
(J) |
||
Line 757:
No zero-sum subsets of length 30
No zero-sum subsets of length 31</pre>
=={{header|J}}==
Task data:
<lang J>text=:0 :0
alliance -624
archbishop -915
balm 397
bonnet 452
brute 870
centipede -658
cobol 362
covariate 590
departure 952
deploy 44
diophantine 645
efferent 54
elysee -326
eradicate 376
escritoire 856
exorcism -983
fiat 170
filmy -874
flatworm 503
gestapo 915
infra -847
isis -982
lindholm 999
markham 475
mincemeat -880
moresby 756
mycenae 183
plugging -266
smokescreen 423
speakeasy -745
vein 813
)
words=:{.@;:;._2 text
numbs=:+/|:0&".;._2 text</lang>
Implementation:
<lang J>wsum0=:4 :0
p=:(#~ 0&<)y
n=:(#~ 0&>)y
poss=: +/@#~2#.inv 2 i.@^#
P=:poss p
N=:poss -n
choose=:(1{I.P e. N){P
keep=: [ #~ #&2@#@[ #: choose i.~ ]
;:inv words #~y e. (p keep P),n keep N
)</lang>
Task example:
<lang J> words wsum0 numbs
centipede markham mycenae</lang>
=={{header|Mathematica}}==
| |||