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