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
