[Jprogramming] Greatest Increasing Subsequence

[Erling Hellenäs]

Hi all !

This one is considerably faster, near lisJ.

ts'LongestIncreasingSubsequence 10000?10000'

2.40974 3.808e6

ts'LongestIncreasingSubsequence ?10000$10000'

2.46657 3.41504e6


It still uses a lot of memory. Handles 100 000 with quite some struggle.


ts'LongestIncreasingSubsequence ?100000$100000'

81.525 3.30742e7

Cheers,

Erling

NB. This is a solution to the problem of finding the longest strictly 
increasing subsequence.

NB. Draws numbers from the end of the sequence. Selects groups with its 
first element larger

NB. than the drawn element. Selects one of the longest of these groups 
if one exists and prepends

NB. the drawn number. If no such group exists create a new group 
containing the drawn number.

NB. Append the new group to the previous groups.

NB. Removes groups which are both shorter than the new group and which 
starts

NB. with a number which is smaller or equal to the number which starts 
the new group.

NB. When all numbers are drawn one of the longest remaining groups is 
selected.



GroupOfEmptyGroupInitialState=: [: < a:"_

GroupOfEmptyGroupInitialState ''

PackElements=: <@+

PackElements 6 1 3 4 2 8

SelectGroupsWithLeftLessThanFirstElement=: ([: , [ < [: (1 {. ])@> ]) # ]

PrependLeftInGroups=: ([: < [) ,&.> ]

2 PrependLeftInGroups <4 5

AddGroupWithLeftIfNoGroups=: ((0 = [: # ]) {. [: < [) , ]

2 AddGroupWithLeftIfNoGroups 0 {. <i.0

2 AddGroupWithLeftIfNoGroups , <1 2

SelectFirstGroupOfMaxLength=: ([: ((1 <. #) {. ]) [: I. ([: (] = '' $ [: 
 >./ ]) #@>)) { ]

SelectFirstGroupOfMaxLength (<2),(<2 4 5),<2 6 7

StartsWithSmallerOrEqual=: ([: {.@> ])<:[: {: [

Shorter=: ([: #@> ])<[: {. [

LengthAndFirstElement=: [: (# , {.) [: > ]

SelectNotShorterAndStartsWithSmallerOrEqual=: (([: LengthAndFirstElement 
[: {: ]) ( ([: -. Shorter *.StartsWithSmallerOrEqual) # ]) [: > [: {. ]) 
, [: {: ]

SelectNotShorterAndStartsWithSmallerOrEqual ((<1 2),(<3 4 5),(< 4 5),(< 
1 4 5));2 6 7

DoBetweenElementsInFold=: [: SelectNotShorterAndStartsWithSmallerOrEqual 
] ; [ AddGroupWithLeftIfNoGroups [ PrependLeftInGroups [: 
SelectFirstGroupOfMaxLength SelectGroupsWithLeftLessThanFirstElement

2 DoBetweenElementsInFold (<1 2 3),<4 5

LongestIncreasingSubsequence=: [: ; [: SelectFirstGroupOfMaxLength [: > 
[: DoBetweenElementsInFold&.:>/ PackElements , GroupOfEmptyGroupInitialState

LongestIncreasingSubsequence=: LongestIncreasingSubsequence f.

LongestIncreasingSubsequence 6 1 3 4 2 8

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

LongestIncreasingSubsequence l

9!:1 [16807

LongestIncreasingSubsequence 1000?1000

9!:1 [16807

LongestIncreasingSubsequence ?1000$1000

ts=: 6!:2 , 7!:2@] NB. Time and space

ts'LongestIncreasingSubsequence 1000?1000'

ts'LongestIncreasingSubsequence ?1000$1000'

ts'LongestIncreasingSubsequence 10000?10000'

ts'LongestIncreasingSubsequence ?10000$10000'