[Jprogramming] Greatest Increasing Subsequence

Thu Sep 15 08:28:53 UTC 2016

The Knuth reference can be downloaded here:

http://www.mediafire.com/download/3btahsyzax4w7xp/Vol%2C3+SortingAndSearching-Donald+Knuth.pdf

Youngs tableau is on page 47.

/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