Doh! I should have studied your solution further before sending my msg. Sorry.
Note to self: think more; type less. ----- Original Message ----- From: Roger Hui <[email protected]> Date: Saturday, March 12, 2011 17:06 Subject: Re: [Jprogramming] greplin challenge To: Programming forum <[email protected]> > I have not studied this problem. However, when I saw > your solution > > findH=:4 :0 > H=. (>:x){.1 > for_e. y do. > H=.(+ (-e)&(|.!.0)) H > end. > H > ) > > I immediately thought "power operator", and I am surprised > that I don't find it in your latest > > (# -~ (+/@:{ [: > [: (] + |.!.0)&.>/ <@- , > <@({.&1)@>:@{:)) B > > > > ----- Original Message ----- > From: Henry Rich <[email protected]> > Date: Saturday, March 12, 2011 14:38 > Subject: Re: [Jprogramming] greplin challenge > To: Programming forum <[email protected]> > > > (# -~ (+/@:{ [: > [: (] + |.!.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
