I came up with this.
f =: (;@:{~ (i. >./)@:(#&>))@:(<@~.@:(>./\)\.)
NB. The main ingredient is ~.@:(>./\)
~.@:(>./\) l
7 8 13 15 19
~.@:(>./\) }.l
4 5 7 8 13 15 19
f l
4 5 7 8 13 15 19
NB. If there are more than one different subseqs
NB. of equal length, it returns the first.
NB. It fails on i.0
NB. I haven't checked it thoroughly.
NB. time and space on your l,
NB. 7 4 4 5 2 7 1 8 13 2 10 4 9 1 4 5 5 4 3 10 3 4 5 8 15 7 11 19
ts'l{~getmax ((3 : ''max =: __'')](g"0)&.>)"0(]@:<)\. l'
0.000665763 28416
ts'f l'
7.39736e_5 13696
NB. Timer does what it says on the box, showing the result, but
NB. not the space requirement.
NB. Boxes will probably line-wrap...
bigl =: ?10000#5000 NB. repeat rate approx 2
timer'bigl{~getmax ((3 : ''max =: __'')](g"0)&.>)"0(]@:<)\. bigl'
+------+---------------------------------------------------------------------------------------------+
|45.864|214 2236 2865 3360 3513 3821 3838 4080 4224 4587 4663 4755 4959
4965 4969 4970 4994 4997 4999|
+------+---------------------------------------------------------------------------------------------+
timer'f bigl'
+--------+---------------------------------------------------------------------------------------------+
|0.622002|214 2236 2865 3360 3513 3821 3838 4080 4224 4587 4663 4755
4959 4965 4969 4970 4994 4997 4999|
+--------+---------------------------------------------------------------------------------------------+
Quicker but is it quick enough? Is this what you were after?
Mike
On 02/09/2016 03:38, 'Jon Hough' via Programming wrote:
Given a list of numbers, find the greatest increasing subsequence of the list.
e.g if list is 6 1 3 4 2 8 then the greatest increasing subsequence is 1 3 4 8.
My solution:
NB. find greatest increasing subsequence of number list.
NB. example list
l =: 7 4 4 5 2 7 1 8 13 2 10 4 9 1 4 5 5 4 3 10 3 4 5 8 15 7 11 19
NB. running max
max =: __
NB. verb tests for new max, returns 1 if
NB. y is greater than current max, 0 otherwise.
g =: 3 : 0
gr =: 0
if. y > max do.
max =: y
gr=. 1
end.
gr
)
NB. find the indices in increasing subsequence
inc =: ((3 : 'max =: __')](g"0)&.>)"0(]@:<)\. l
NB. get the items with max index count. take the first item.
getmax =: I.@:(= >./)@:>@:(+/&.>) (I.@:>@:{.@:{ + {.@:[) ]
indices =: getmax inc
NB. return the items at given indices.
indices { l
This works fine, but seems overly complicated... and ugly. Any better solutions?
Also this algorithm is O(n^2) in time, but the most efficient algorithm can be
O(n log n).( https://en.wikipedia.org/wiki/Longest_increasing_subsequence )
----------------------------------------------------------------------
For information about J forums see http://www.jsoftware.com/forums.htm
---
This email has been checked for viruses by Avast antivirus software.
https://www.avast.com/antivirus
----------------------------------------------------------------------
For information about J forums see http://www.jsoftware.com/forums.htm
