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
