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
