Hey presto! You're right. Since you don't need to know the subsets,
you don't have to do the backtracking. For that matter, you can do it
with just one copy of the H vector: i{H tells how many ways you can add
up items to get i; so just find H for the whole input vector, and add
up the values corresponding to B. You them have to remove the
singletons that created one-element sets that added to equal themselves,
because you were supposed to be looking at only smaller numbers. You get:
findH=:4 :0
H=. (>:x){.1
for_e. y do.
H=.(+ (-e)&(|.!.0)) H
end.
H
)
(#B) -~ +/ B { ({:B) findH B
179
Probably not to hard to make tacit, too.
Henry Rich
On 3/12/2011 4:57 PM, Marshall Lochbaum wrote:
> 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
>
----------------------------------------------------------------------
For information about J forums see http://www.jsoftware.com/forums.htm
