# Re: [Jprogramming] Greatest Increasing Subsequence

```The Knuth reference can be downloaded here:

```
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 + [) >. [: # ]) {. ]

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
```
```
----------------------------------------------------------------------
For information about J forums see http://www.jsoftware.com/forums.htm```