[Jprogramming] Greatest Increasing Subsequence

Wed Sep 14 21:27:05 UTC 2016

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