A solution with this method:
B=: 3 4 9 14 15 19 28 37 47 50 54 56 59 61 70 73 78 81 92 95 97 99
sums=:4 :0
H=. (>:x){.1
for_e. y do.
H=.(+ (-e)&(|.!.0)) H
end.
{:H
)
+/ B sums&> (i.22) {.&.> (<B)
179
Note that by changing +. to +, HH is not needed.
Marshall
-----Original Message-----
From: [email protected]
[mailto:[email protected]] On Behalf Of Henry Rich
Sent: Saturday, March 12, 2011 9:49 AM
To: Programming forum
Subject: Re: [Jprogramming] greplin challenge
I think there is, but I don't have time to code the interesting part, which
resembles the integer knapsack problem. I will outline the solution.
Examining each value v in turn, the question is to count the subsets of
smaller values to find those that add up to v. So: count the subsets of a
set S that add up to a desired target v.
To do that, you create a Boolean vector H which is v+1 long and represents
which totals can be reached by combinations of elements of the set. The
idea is to consider the elements of S in turn, making a new copy of H after
considering each element. This will give an array HH which you then
backtrack through to find all the paths leading from the bottom-right to the
top-left.
Initialize HH =. ,: H =. (>:v) {. 1
for_e. S do.
NB. The values reachable possibly using e are all the values
NB. reachable not using e, and all those values plus e:
H =. H +. (-e) |.!.0 H
NB. Remember the new H after considering e
HH =. HH , H
end.
Now, if {: H is 1, there is a combination of elements that adds to v.
It remains to find all such subsets. You do this by going back through the
rows of HH.
The plan is, keep a list of reachable values, and for each one, the list of
sets that reach. Initially the list of reachable values is just v, and its
corresponding list of sets is empty.
Discard the last row of HH. Then, for each row starting with the last, see
which of the reachable values can be reached if you include, or exclude, the
Si that produced the row. You will have a new set of reachable values and
corresponding subsets.
When you get back to the first row of HH, you will have all the subsets.
The performance of this dynamic-programming solution is proportional to
(v*(number of items of S)); much faster than enumerating subsets.
Henry Rich
On 3/12/2011 5:37 AM, chris burke wrote:
> This challenge http://challenge.greplin.com seems to have missed the
> forum. Each is straightforward in J.
>
> The last is to count the subsets of an array where the largest number
> is the sum of the remaining numbers. The given array is
>
> B=: 3 4 9 14 15 19 28 37 47 50 54 56 59 61 70 73 78 81 92 95 97 99
>
> A brute force calculation is:
> <: +/ B ((+/=2*{:) @: #~)"1 #:i.2^#B
> 179
>
> This takes a few seconds. Is there a better way?
> ----------------------------------------------------------------------
> For information about J forums see http://www.jsoftware.com/forums.htm
>
----------------------------------------------------------------------
For information about J forums see http://www.jsoftware.com/forums.htm
----------------------------------------------------------------------
For information about J forums see http://www.jsoftware.com/forums.htm
