[Jprogramming] Greatest Increasing Subsequence

[Erling Hellenäs]

lisf =: 3 : 0

x =. y

if. 2>#x do. x return. end.

T =. {.x

for_xj. }.x do.

if. xj > {:T do.

T =. T, xj

else.

m =. T I. xj

NB. if. xj < m { T do. Slight impairment with this test

T =. xj m } T

NB. end.

end.

end.

T

)

lisf 6 1 3 4 2 8

1 2 4 8


As we can see the result is not correct. The length is correct and that 
is what the Fredman/Knuth algorithm calculates I think.

I also tried the algorithm. Many results are correct, I was lucky to 
have this test to show that it was wrong. Then I examined the Fredman 
paper a bit more.


/Erling


On 2016-09-15 11:52, Erling Hellenäs wrote:
> The Fredman paper is about calculation of the length L of the longest 
> increasing subsequence, not the calculation of the longest increasing 
> subsequence as such. The algorithm only computes "valueofminendvalue" 
> I think. /Erling
>
>
> On 2016-09-14 23:27, 'Mike Day' via Programming wrote:
>> I suspect it's pretty near optimal.  The wikipedia article points at 
>> Fredman's paper:
>> http://www.sciencedirect.com/science/article/pii/0012365X7590103X
>> analysing an algorithm of Knuth's.  He shows that it performs better 
>> than
>>    n log2(n) - n log2 log2 (n) + O(n)
>> rather than the O(n logn) cited for the function we've been looking at.
>>
>> I might have a play at tacit for the algorithm already discussed.
>>
>> Mike
>>
>> On 14/09/2016 14:57, Erling Hellenäs wrote:
>>> Any ideas about how you could make a substantially faster tacit 
>>> solution to this problem or how you could make this solution 
>>> substantially faster? /Erling
>>>
>>>
>>> On 2016-09-13 18:17, Erling Hellenäs wrote:
>>>> Hi all !
>>>>
>>>> My first idea only took me down to 1 second for 10 000 numbers, 25 
>>>> times longer than longscseq. I then made a tacit version of 
>>>> longascseq. It still takes about 4 times longer than longascseq.
>>>>
>>>> See these two versions below.
>>>>
>>>> I included the full project of the tacit version.
>>>>
>>>> Cheers,
>>>>
>>>> Erling
>>>>
>>>> NB. Find the longest stricty increasing subsequence
>>>>
>>>> NB. Values are the lowest last values yet found for each 
>>>> subsequence length.
>>>>
>>>> NB. Indices are the indices of these values in the original sequence.
>>>>
>>>> NB. Predecessors are indices to the end of the next lower subsequence
>>>>
>>>> NB. for each value in the original sequence.
>>>>
>>>> NB. The longest sequence is found by index lookup in predecessors 
>>>> from the index
>>>>
>>>> NB. of the highest found value.
>>>>
>>>>
>>>> Amend=:([:>[:{.[)`([:>[:{:[)`] }
>>>>
>>>> PickPower=: {~^:([`([:>[:{.])`([:>[:{:]))
>>>>
>>>> ValuesIndicesPredecessorsIndexInitialState=: [: < a:"_ , a:"_ , 
>>>> (([: # ]) $2:) ;0:
>>>>
>>>> PackValues=: <@+
>>>>
>>>> Values=: [: > 0 { ]
>>>>
>>>> Indices=: [: > 1 { ]
>>>>
>>>> Predecessors=: [: > 2 { ]
>>>>
>>>> Index=: [: > 3 { ]
>>>>
>>>> AdjustLength=: ((1 + [) >. [: # ]) {. ]
>>>>
>>>> AmendValues=: (([: {. [) ; [: {: [) Amend ([: {: [) AdjustLength 
>>>> Values
>>>>
>>>> AmendIndices=: (Index ; [: {: [) Amend ([: {: [) AdjustLength Indices
>>>>
>>>> AmendPredecessors=: ((([: <: [: {: [){Indices);Index ) Amend 
>>>> Predecessors
>>>>
>>>> DoBetweenElementsInFold=: ([,(Values I. [ )) ( [ 
>>>> (Values;Indices;AmendPredecessors;1+Index) 
>>>> AmendValues;AmendIndices;Predecessors;Index) ]
>>>>
>>>> Reconstruct=: [: (Predecessors PickPower ([: i. [: - [: # 
>>>> Indices);[: {: Indices) [: > ]
>>>>
>>>> LongestIncreasingSubsequenceIndices=: [: Reconstruct [: 
>>>> DoBetweenElementsInFold&.:>/ ([: |. PackValues) , 
>>>> ValuesIndicesPredecessorsIndexInitialState
>>>>
>>>> LongestIncreasingSubsequence=: ([: 
>>>> LongestIncreasingSubsequenceIndices ]){ ]
>>>>
>>>> LongestIncreasingSubsequence=: LongestIncreasingSubsequence f.
>>>>
>>>> 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. Removes groups which are both shorter than the new group or of 
>>>> equal length and which starts
>>>>
>>>> NB. with a number which is smaller or equal to the number which 
>>>> starts the new group.
>>>>
>>>> NB. Append the new group to the remaining groups.
>>>>
>>>> NB. When all numbers are drawn one of the longest remaining groups 
>>>> is selected.
>>>>
>>>>
>>>> GroupOfEmptyGroupInitialState=: [: < a:"_
>>>>
>>>> PackElements=: <@+
>>>>
>>>> StartsWithLonger=: ([: {.@> [) < [: {.@> ]
>>>>
>>>> Longer=:([: #@> [) < [: #@> ]
>>>>
>>>> SelectLongerOrStartsWithLonger=: (Longer +. StartsWithLonger ) # ]
>>>>
>>>> SelectGroupsWithLeftLessThanFirstElement=: ([ < [: {.@> ]) # ]
>>>>
>>>> SelectFirstGroupOfMaxLength=: ((1 <. [: # ]) {. [: I. [: (] = [: 
>>>> >./ ]) #@>) { ]
>>>>
>>>> PrependLeftInGroups=: ([: < [) ,&.> ]
>>>>
>>>> AddGroupWithLeftIfNoGroups=: ((0 = [: # ]) {. [: < [) , ]
>>>>
>>>> DoBetweenElementsInFold=: ([: {. [ AddGroupWithLeftIfNoGroups [ 
>>>> PrependLeftInGroups [: SelectFirstGroupOfMaxLength 
>>>> SelectGroupsWithLeftLessThanFirstElement ) ([ , 
>>>> SelectLongerOrStartsWithLonger) ]
>>>>
>>>> LongestIncreasingSubsequence=: [: ; [: SelectFirstGroupOfMaxLength 
>>>> [: > [: DoBetweenElementsInFold&.:>/ PackElements , 
>>>> GroupOfEmptyGroupInitialState
>>>>
>>>> LongestIncreasingSubsequence=: LongestIncreasingSubsequence f.
>>>>
>>>>
>>>> Full project of tacit version
>>>>
>>>> =======================
>>>>
>>>>
>>>> NB. Find the longest stricty increasing subsequence
>>>>
>>>> NB. Values are the lowest last values yet found for each 
>>>> subsequence length.
>>>>
>>>> NB. Indices are the indices of these values in the original sequence.
>>>>
>>>> NB. Predecessors are indices to the end of the next lower subsequence
>>>>
>>>> NB. for each value in the original sequence.
>>>>
>>>> NB. The longest sequence is found by index lookup in predecessors 
>>>> from the index
>>>>
>>>> NB. of the highest found value.
>>>>
>>>>
>>>> ts=: 6!:2 , 7!:2@] NB. Time and space
>>>>
>>>> Amend=:([:>[:{.[)`([:>[:{:[)`] }
>>>>
>>>> (1;0) Amend 3 4 5
>>>>
>>>> PickPower=: {~^:([`([:>[:{.])`([:>[:{:]))
>>>>
>>>> 2 3 4 PickPower 1;1
>>>>
>>>> ValuesIndicesPredecessorsIndexInitialState=: [: < a:"_ , a:"_ , 
>>>> (([: # ]) $2:) ;0:
>>>>
>>>> ValuesIndicesPredecessorsIndexInitialState 7 1 2 3
>>>>
>>>> PackValues=: <@+
>>>>
>>>> PackValues 7 1 2 3
>>>>
>>>> Values=: [: > 0 { ]
>>>>
>>>> Values 1 2 3;0 1 2;2 2 2;0
>>>>
>>>> Indices=: [: > 1 { ]
>>>>
>>>> Indices 1 2 3;0 1 2;2 2 2;0
>>>>
>>>> Predecessors=: [: > 2 { ]
>>>>
>>>> Predecessors 1 2 3;0 1 2;2 2 2;0
>>>>
>>>> Index=: [: > 3 { ]
>>>>
>>>> Index 1 2 3;0 1 2;2 2 2;0
>>>>
>>>> AdjustLength=: ((1 + [) >. [: # ]) {. ]
>>>>
>>>> 3 AdjustLength 1 2 3
>>>>
>>>> 2 AdjustLength 1 2 3
>>>>
>>>> AmendValues=: (([: {. [) ; [: {: [) Amend ([: {: [) AdjustLength 
>>>> Values
>>>>
>>>> (7,3) AmendValues 1 2 3;0 1 2;2 2 2;0
>>>>
>>>> AmendIndices=: (Index ; [: {: [) Amend ([: {: [) AdjustLength Indices
>>>>
>>>> (7,3) AmendIndices 1 2 3;0 1 2;2 2 2;0
>>>>
>>>> AmendPredecessors=: ((([: <: [: {: [){Indices);Index ) Amend 
>>>> Predecessors
>>>>
>>>> (7,3) AmendPredecessors 1 2 3;0 1 2;2 2 2;0
>>>>
>>>> DoBetweenElementsInFold=: ([,(Values I. [ )) ( [ 
>>>> (Values;Indices;AmendPredecessors;1+Index) 
>>>> AmendValues;AmendIndices;Predecessors;Index) ]
>>>>
>>>> 3 DoBetweenElementsInFold 1 2;1 2;0 1 1 2;3
>>>>
>>>> Reconstruct=: [: (Predecessors PickPower ([: i. [: - [: # 
>>>> Indices);[: {: Indices) [: > ]
>>>>
>>>> Reconstruct < 1 2 3;1 2 3;0 1 1 2;4
>>>>
>>>> LongestIncreasingSubsequenceIndices=: [: Reconstruct [: 
>>>> DoBetweenElementsInFold&.:>/ ([: |. PackValues) , 
>>>> ValuesIndicesPredecessorsIndexInitialState
>>>>
>>>> ( 7 DoBetweenElementsInFold [: > 
>>>> ValuesIndicesPredecessorsIndexInitialState)7 1 2 3
>>>>
>>>> ( 1 DoBetweenElementsInFold (7 DoBetweenElementsInFold [: > 
>>>> ValuesIndicesPredecessorsIndexInitialState))7 1 2 3
>>>>
>>>> ( 2 DoBetweenElementsInFold (1 DoBetweenElementsInFold (7 
>>>> DoBetweenElementsInFold [: > 
>>>> ValuesIndicesPredecessorsIndexInitialState)))7 1 2 3
>>>>
>>>> ( 3 DoBetweenElementsInFold (2 DoBetweenElementsInFold (1 
>>>> DoBetweenElementsInFold (7 DoBetweenElementsInFold [: > 
>>>> ValuesIndicesPredecessorsIndexInitialState))))7 1 2 3
>>>>
>>>> Reconstruct < (3 DoBetweenElementsInFold ( 2 
>>>> DoBetweenElementsInFold ( 1 DoBetweenElementsInFold ( 7 
>>>> DoBetweenElementsInFold [: > 
>>>> ValuesIndicesPredecessorsIndexInitialState))))7 1 2 3
>>>>
>>>> LongestIncreasingSubsequence=: ([: 
>>>> LongestIncreasingSubsequenceIndices ]){ ]
>>>>
>>>> LongestIncreasingSubsequence=: LongestIncreasingSubsequence f.
>>>>
>>>> LongestIncreasingSubsequence 7 1 2 3
>>>>
>>>> LongestIncreasingSubsequence i.0
>>>>
>>>> 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
>>>>
>>>> [a=:LongestIncreasingSubsequence 1000?1000
>>>>
>>>> #a
>>>>
>>>> 9!:1 [16807
>>>>
>>>> [a=:LongestIncreasingSubsequence ?1000$1000
>>>>
>>>> #a
>>>>
>>>> ts=: 6!:2 , 7!:2@] NB. Time and space
>>>>
>>>> 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
>
> ----------------------------------------------------------------------
> For information about J forums see http://www.jsoftware.com/forums.htm