Subset sum problem: Difference between revisions
Content added Content deleted
(Show a non-brute-force Mathematica solution.) |
(J) |
||
Line 757: | Line 757: | ||
No zero-sum subsets of length 30 |
No zero-sum subsets of length 30 |
||
No zero-sum subsets of length 31</pre> |
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}}== |
=={{header|Mathematica}}== |