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
