What is the "j" expression for the "maximum consecutive ones" problem?
Asked Answered
D

2

6

In the paper "Combinatory Logic and Combinators in Array Languages" they give a solution in APL:

      vec ← 1 1 0 1 1 1 0 0 0 1
      ⍝ split (partition) on zeroes
      ⊆⍨vec
┌───┬─────┬─┐
│1 1│1 1 1│1│
└───┴─────┴─┘
      ⍝ size of each sublist
      ≢ ̈⊆⍨vec
2 3 1
      ⍝ max reduction
      ⌈/≢¨⊆⍨vec
3

For clarity, they also note:

The final maximum consecutive ones APL solution can be translated for those who don’t read APL: reduce(max, map(length, W(partition, vec)))

So, how would one express the following in J?

 ⌈/≢¨⊆⍨vec

The symbol seems to be a "partition" operator. It's not clear this exists in J but I may have just missed it. Curious what the above expression would be in "J".

Dentiform answered 13/9, 2022 at 0:0 Comment(2)
Short answer is the “cut” conjunction ;.; for example, >./ #;._1 ]0, 1 1 0 1 1 1 0 0 0 1 NB. Returns 3. I’ll try to find the time for a formal answer later. If I can’t or don’t, anyone at all is free to use this comment as a basis of their answer. No need for attribution.Isotron
Btw, (⌈/¯1-2-/∘⍸1,1,⍨~) is a much more efficient function for computing this.Evenings
R
4

Dan Bron's answer in the comments is the way to go for sure. I did a video on this problem and if you are interested you can watch me walk through the different options. https://www.youtube.com/watch?v=lbi_PMVbeaQ The version I ended preferring was

t=:[: >./ [: #;. _2 ,&0

but I also look at

t=:[: {: [: $ [: ];. _2 ,&0

as an alternative.

Regimentals answered 13/9, 2022 at 18:49 Comment(2)
Abusing ];. for its result shape is delicious. Love it.Isotron
thanks for the link to the video. more than i could have hoped forDentiform
C
3

To provide a different point of view, the maximum number of 1s in a row is also the maximum of the difference between consecutive indices of 0s in the array (minus one), for which J (almost) has a primitive: I. (up to a -.). So the following works too:

t=: [: -&1 [: >./ [: 2&(-~/;._3) [: I. -.
Chatham answered 19/9, 2022 at 19:48 Comment(0)

© 2022 - 2024 — McMap. All rights reserved.