[Jprogramming] Greatest Increasing Subsequence

['Mike Day' via Programming]

Thanks.
I'm sure you know the following,  but it might be worth pointing out:

    longascseq l
6 9 20 21 22 25 26 27

    l{~longascseq l
1 2 3 4 5 7 11 19

    lisM l
1 2 3 4 5 7 11 19

ie, longascseq returns the indices of the/a subsequence.

Very limited testing suggests that it's a little bit slower,
(on 10000 elements) but saves space compared to the function,
lisM, that I posted earlier.  I suppose that's because of the
if-then-else block,  though I haven't studied their differences
yet.

Cheers,
Mike

On 09/09/2016 20:09, Henry Rich wrote:
> 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
>
> ----------------------------------------------------------------------
> 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