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
