+/ <: B ways"0 1 B 179 is slightly clearer.
"David Hotham" <[email protected]> wrote in message news:[email protected]... >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 > ---------------------------------------------------------------------- For information about J forums see http://www.jsoftware.com/forums.htm
