Subset sum problem: Difference between revisions
Content added Content deleted
m (→{{header|REXX}}: added whitespace, order subroutines in alphabetic order, added comments, changed comments, deleted superfluous semicolons. -- ~~~~) |
(→{{header|Haskell}}: non-bruteforce) |
||
Line 499: | Line 499: | ||
{{out}} |
{{out}} |
||
<pre>["archbishop","gestapo"]</pre> |
<pre>["archbishop","gestapo"]</pre> |
||
None bruteforce: the list of numbers used here are different, and difficult for a bruteforce method. |
|||
<lang haskell>subsum ls = sub_ [(0,[])] ls where |
|||
sub_ a [] = a |
|||
sub_ a (x:xs) = sub_ (merge a $ map (f x) a) xs |
|||
f x (a,l) = (a+x, l++[x]) |
|||
-- keep list of sums sorted. Don't use standard sort! |
|||
merge [] a = a |
|||
merge a [] = a |
|||
merge a@((av,al):as) b@((bv,bl):bs) |
|||
| av < bv = (av,al):merge as b |
|||
| av == bv = (bv,bl):merge as bs |
|||
| otherwise = (bv,bl):merge a bs |
|||
items = [-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 ] |
|||
main = print $ snd.head.filter ((==0).fst) $ subsum items</lang> |
|||
{{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> |
|||
=={{header|Icon}} and {{header|Unicon}}== |
=={{header|Icon}} and {{header|Unicon}}== |