(# -~ (+/@:{ [: > [: (] + |.!.0)&.>/ <@- , <@({.&1)@>:@{:)) B
179
Henry Rich
On 3/12/2011 5:19 PM, Henry Rich wrote:
> 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
>
----------------------------------------------------------------------
For information about J forums see http://www.jsoftware.com/forums.htm
