[Jprogramming] Greatest Increasing Subsequence

[Henry Rich]

I have created a Wiki page for this, where you can post solutions.

http://code.jsoftware.com/wiki/Essays/Longest_Increasing_Subsequence

I don't think a tacit solution can be efficient, considering how many 
in-place operations are needed.

Henry Rich

On 9/9/2016 1:46 PM, Erling Hellenäs wrote:
> 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'
>
>
> ----------------------------------------------------------------------
> For information about J forums see http://www.jsoftware.com/forums.htm