Most efficient is the following solution
}.{. ({~@] ,:~ [ + {~)/ ^:_ B ,:&(0&,) }.(i: <:@{:)\ 0, >:A
14 30 22 28 33 36 34 50 50 69 35 34 37 38 46 49 66 49 43 48 65 72 52
R.E. Boss
> -----Oorspronkelijk bericht-----
> Van: [email protected] [mailto:programming-
> [email protected]] Namens R.E. Boss
> Verzonden: donderdag 4 augustus 2011 6:50
> Aan: Programming forum
> Onderwerp: Re: [Jprogramming] complicated sums of subarrays
>
> The following solution essentially uses the same idea
>
> }. +/ (0 , B) {~ ((~. <:/ ]) * [: (+/\ { 0 , I.)"1 =) 0 , >:A
> 14 30 22 28 33 36 34 50 50 69 35 34 37 38 46 49 66 49 43 48 65 72 52
>
>
> R.E. Boss
>
>
> > -----Oorspronkelijk bericht-----
> > Van: [email protected] [mailto:programming-
> > [email protected]] Namens Stefano Lanzavecchia
> > Verzonden: woensdag 3 augustus 2011 17:04
> > Aan: 'Programming forum'
> > Onderwerp: Re: [Jprogramming] complicated sums of subarrays
> >
> > Here's a quick and dirty translation from APL ([]IO 1 which accounts
> > for
> the
> > >:A) of an algorithm (I can't claim it's mine...):
> >
> > ] r=:(>./>:A),#>:A
> > 7 23
> >
> > ] m=:_1}."1 (1->:A)|."0 1 |:1,r$0
> > 1 0 0 0 0 0 0
> > 0 1 0 0 0 0 0
> > 0 1 0 0 0 0 0
> > 0 0 1 0 0 0 0
> > 0 0 0 1 0 0 0
> > 0 0 0 1 0 0 0
> > 0 0 0 1 0 0 0
> > 0 0 0 0 1 0 0
> > 0 0 0 0 1 0 0
> > 0 0 0 0 0 1 0
> > 0 0 1 0 0 0 0
> > 0 0 1 0 0 0 0
> > 0 0 0 1 0 0 0
> > 0 0 0 0 1 0 0
> > 0 0 0 0 1 0 0
> > 0 0 0 0 1 0 0
> > 0 0 0 0 0 1 0
> > 0 0 0 0 0 1 0
> > 0 0 0 1 0 0 0
> > 0 0 0 0 1 0 0
> > 0 0 0 0 0 1 0
> > 0 0 0 0 0 0 1
> > 0 0 0 0 1 0 0
> >
> > ] b=:,|:m +. *./\"1 -.m
> > 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 0 1 1 1 1 1 1 1 1 1 1 1
> > 1 1
> 1
> > 1 1 1 1 1 1 1 1 0 0 0 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 0 0 0 0
> > 1 1
> 1
> > 1 1 1 0 0 1 1 1 1 1 1 1 1 1 1 1 0 0 0 0 0 0 0 1 1 1 0 0 0 1 1 1 1 1 0
> > 1 1
> 1
> > 1 0 0 0 0 0 0 0 0 0 1 0 0 0 ...
> > ] w=:,(|.$m)$i.{.$m
> > 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 0 1 2 3 4 5
> > 6 7
> 8
> > 9 10 11 12 13 14 15 16 17 18 19 20 21 22 0 1 2 3 4 5 6 7 8 9 10 11 12
> > 13
> 14
> > 15 16 17 18 19 20 21 22 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18
> > 19
> 20
> > 21 22 0 1 2 3 4 5 6 7 8 9 ...
> >
> > a=:,|:m
> >
> > ] i=:(<:+/\a){a#w
> > 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 2 2 2 2 2 2 2 2 2 2
> > 2 2
> 2
> > 2 2 2 2 2 2 2 2 2 2 2 3 3 3 3 3 3 3 10 11 11 11 11 11 11 11 11 11 11
> > 11 11
> > 11 11 11 11 4 5 6 6 6 6 6 6 12 12 12 12 12 12 18 18 18 18 18 18 18 18
> > 18
> 18
> > 18 18 7 8 8 8 8 8 13 14 15 15...
> >
> > ] x=:($|:m)$(b*>:i){0,B
> > 14 14 14 14 14 14 14 14 14 14 14 14 14 14 14 14 14 14 14 14 14 14 14
> > 0 16 8 8 8 8 8 8 8 8 8 8 8 8 8 8 8 8 8 8 8 8 8
> > 0 0 0 6 6 6 6 6 6 6 13 12 12 12 12 12 12 12 12 12 12 12 12
> > 0 0 0 0 5 8 6 6 6 6 0 0 3 3 3 3 3 3 9 9 9 9 9
> > 0 0 0 0 0 0 0 16 16 16 0 0 0 1 9 12 12 12 0 5 5 5 9
> > 0 0 0 0 0 0 0 0 0 19 0 0 0 0 0 0 17 0 0 0 17 17 0
> > 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 7 0
> >
> > ] C=:+/x
> > 14 30 22 28 33 36 34 50 50 69 35 34 37 38 46 49 66 49 43 48 65 72 52
> >
> > I am sure it can be translated into proper J without too many
> > transpose, increment and so on. It might also need a bit of
> > improvement for the edge cases (empty arguments and the like) but I
> > hope it's a good starting
> point.
> >
> > The idea is that the problem seems to be a hierarchical sum where A is
> > the vector of depths in the tree.
> > Have fun!
> > --
> > Stefano
> >
> > > -----Original Message-----
> > > From: [email protected] [mailto:programming-
> > > [email protected]] On Behalf Of R.E. Boss
> > > Sent: Wednesday, August 03, 2011 3:37 PM
> > > To: Programming forum
> > > Subject: [Jprogramming] complicated sums of subarrays
> > >
> > > Let A be an 'almost' non-decreasing array of non-negative integers,
> > > which
> > is
> > > (by definition) a concatenation of non-decreasing sub arrays.
> > > E.g.
> > > A=. 0 1 1 2 3 3 3 4 4 5 , 2 2 3 4 4 4 5 5 , 3 4 5 6 , 4 The
> > > comma's
> > are
> > > superfluous but identify the non-decreasing sub arrays.
> > >
> > > Let B be an array of real numbers, with the same length as A.
> > > [B=. 20 ?.@#~ #A
> > > 14 16 8 6 5 8 6 16 16 19 13 12 3 1 9 12 17 0 9 5 17 7 9
> > >
> > > Required:
> > > array C, by taking array B and add each element of B, corresponding
> > > with element x in A, to all the next elements of B which correspond
> > > to elements
> > y
> > > in A with x<y and such that for all z in A placed between x and y,
> > > you
> > have x<z.
> > >
> > > I do have a solution, but it is essentially rank 0.
> > > Can anyone come up with an elegant solution of larger rank?
> > >
> > > The answer for the example above is
> > >
> > > A , B ,: C
> > > 0 1 1 2 3 3 3 4 4 5 2 2 3 4 4 4 5 5 3 4 5 6 4
> > > 14 16 8 6 5 8 6 16 16 19 13 12 3 1 9 12 17 0 9 5 17 7 9
> > > 14 30 22 28 33 36 34 50 50 69 35 34 37 38 46 49 66 49 43 48 65 72 52
> > >
> > >
> > > R.E. Boss
> > >
> > >
> > > Spoiler alert
> > >
> > >
> > >
> > >
> > >
> > >
> > >
> > >
> > >
> > >
> > >
> > >
> > >
> > >
> > >
> > >
> > >
> > >
> > >
> > >
> > >
> > >
> > >
> > >
> > >
> > >
> > >
> > >
> > >
> > >
> > >
> > >
> > >
> > >
> > >
> > >
> > >
> > >
> > >
> > >
> > >
> > >
> > >
> > >
> > >
> > > C=.([: +/ B {~ ] i: i.@>:@{:)\ A
> > >
> > > --------------------------------------------------------------------
> > > --
> > > 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
