[Jprogramming] Greatest Increasing Subsequence

[Henry Rich]

They're about the same speed on my machine.  I don't think the 
if-then-else is material.  They're essentially the same algorithm.

(I'm testing on J8.05 beta, where the long names don't affect performance)

Henry Rich

On 9/9/2016 7:26 PM, 'Mike Day' via Programming wrote:
> 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
>
> ----------------------------------------------------------------------
> For information about J forums see http://www.jsoftware.com/forums.htm