[Jprogramming] Greatest Increasing Subsequence

[Erling Hellenäs]

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'