# Re: [Jprogramming] Greatest Increasing Subsequence

Other things we can note about creating a tacit version of this algorithm:

-To use Insert to process the input array, the items of this array has to be boxed, since the initial state can not be an integer. This adds a lot of Box and Open operations.

-There is also only one Insert. There is no reverse Insert. This means either the algorithm has to be changed to work backwards, or the input array has to be reversed.

As we can see here, in F# there is a Fold and a FoldBack and there is a separate initial state.

https://msdn.microsoft.com/en-us/visualfsharpdocs/conceptual/array.fold%5B't,'state%5D-function-%5Bfsharp%5D

Cheers,

Erling

On 2016-09-15 14:12, Henry Rich wrote:
Tacitly appending to an array requires a copy; so does tacit amending. Thus, any tacit version is going to have quadratic performance.

But I am working on making (x , y) and (x m} y) operate in-place even in tacit forms. It will be a couple of months before that gets into a beta.

Henry Rich

On 9/15/2016 7:50 AM, 'Mike Day' via Programming wrote:
Interesting!  That wikipedia reference to Fredman is misleading,  to
say the least.  It misled me, anyway.   I'll have a look at whether it's
ok if one works with indices rather than values,  as in longascseq.

The tacit closure was nice, though...

Thanks,
Mike

On 15/09/2016 11:05, Erling Hellenäs wrote:
lisf =: 3 : 0

x =. y

if. 2>#x do. x return. end.

T =. {.x

for_xj. }.x do.

if. xj > {:T do.

T =. T, xj

else.

m =. T I. xj

NB. if. xj < m { T do. Slight impairment with this test

T =. xj m } T

NB. end.

end.

end.

T

)

lisf 6 1 3 4 2 8

1 2 4 8

As we can see the result is not correct. The length is correct and that is what the Fredman/Knuth algorithm calculates I think.

I also tried the algorithm. Many results are correct, I was lucky to have this test to show that it was wrong. Then I examined the Fredman paper a bit more.

/Erling

On 2016-09-15 11:52, Erling Hellenäs wrote:
The Fredman paper is about calculation of the length L of the longest increasing subsequence, not the calculation of the longest increasing subsequence as such. The algorithm only computes "valueofminendvalue" I think. /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 + [) >. [: # ]) {. ]

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

---------------------------------------------------------------------- For information about J forums see http://www.jsoftware.com/forums.htm

----------------------------------------------------------------------
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

----------------------------------------------------------------------
For information about J forums see http://www.jsoftware.com/forums.htm