A recursion along these lines but without the dynamic programming element is
still quite a lot more efficient than the brute force approach.
(I expect it's possible to make this solution tacit, but I fear I'm not up
to the job).
NB. How many ways of reaching target x using values in y?
ways=: 4 : 0
if. 0 = x do. 1 return. end.
if. 0 = # y do. 0 return. end.
head=. {. y
rest=. }. y
withoutH=. x ways rest
if. head > x do. withH=. 0 else. withH=. (x - head) ways rest end.
withH + withoutH
)
($ B) -~ +/ B ways"0 1 B
179
Ts '($ B) -~ +/ B ways"0 1 B'
0.547134 64000
Ts '<: +/ B ((+/=2*{:) @: #~)"1 #:i.2^#B'
3.47389 2.09722e8
David
"Henry Rich" <[email protected]> wrote in message
news:[email protected]...
>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
