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

## Advertising

`-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 tacitamending. Thus, any tacit version is going to have quadraticperformance.But I am working on making (x , y) and (x m} y) operate in-place evenin tacit forms. It will be a couple of months before that gets into abeta.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 8As we can see the result is not correct. The length is correct andthat is what the Fredman/Knuth algorithm calculates I think.I also tried the algorithm. Many results are correct, I was lucky tohave this test to show that it was wrong. Then I examined theFredman 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 thelongest increasing subsequence, not the calculation of the longestincreasing subsequence as such. The algorithm only computes"valueofminendvalue" I think. /ErlingOn 2016-09-14 23:27, 'Mike Day' via Programming wrote:I suspect it's pretty near optimal. The wikipedia article pointsat Fredman's paper:http://www.sciencedirect.com/science/article/pii/0012365X7590103Xanalysing an algorithm of Knuth's. He shows that it performsbetter thann log2(n) - n log2 log2 (n) + O(n)rather than the O(n logn) cited for the function we've beenlooking 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 tacitsolution to this problem or how you could make this solutionsubstantially faster? /ErlingOn 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 oflongascseq. 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 subsequenceNB. Values are the lowest last values yet found for eachsubsequence length.NB. Indices are the indices of these values in the originalsequence.NB. Predecessors are indices to the end of the next lowersubsequenceNB. for each value in the original sequence.NB. The longest sequence is found by index lookup inpredecessors from the indexNB. 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 ([: {: [) AdjustLengthValuesAmendIndices=: (Index ; [: {: [) Amend ([: {: [) AdjustLengthIndicesAmendPredecessors=: ((([: <: [: {: [){Indices);Index ) AmendPredecessorsDoBetweenElementsInFold=: ([,(Values I. [ )) ( [(Values;Indices;AmendPredecessors;1+Index)AmendValues;AmendIndices;Predecessors;Index) ]Reconstruct=: [: (Predecessors PickPower ([: i. [: - [: #Indices);[: {: Indices) [: > ]LongestIncreasingSubsequenceIndices=: [: Reconstruct [:DoBetweenElementsInFold&.:>/ ([: |. PackValues) ,ValuesIndicesPredecessorsIndexInitialStateLongestIncreasingSubsequence=: ([:LongestIncreasingSubsequenceIndices ]){ ]LongestIncreasingSubsequence=: LongestIncreasingSubsequence f.NB. This is a solution to the problem of finding the longeststrictly increasing subsequence.NB. Draws numbers from the end of the sequence. Selects groupswith its first element largerNB. than the drawn element. Selects one of the longest of thesegroups if one exists and prependsNB. the drawn number. If no such group exists create a new groupcontaining the drawn number.NB. Removes groups which are both shorter than the new group orof equal length and which startsNB. with a number which is smaller or equal to the number whichstarts the new group.NB. Append the new group to the remaining groups.NB. When all numbers are drawn one of the longest remaininggroups is selected.GroupOfEmptyGroupInitialState=: [: < a:"_ PackElements=: <@+ StartsWithLonger=: ([: {.@> [) < [: {.@> ] Longer=:([: #@> [) < [: #@> ] SelectLongerOrStartsWithLonger=: (Longer +. StartsWithLonger ) # ] SelectGroupsWithLeftLessThanFirstElement=: ([ < [: {.@> ]) # ]SelectFirstGroupOfMaxLength=: ((1 <. [: # ]) {. [: I. [: (] = [:>./ ]) #@>) { ]PrependLeftInGroups=: ([: < [) ,&.> ] AddGroupWithLeftIfNoGroups=: ((0 = [: # ]) {. [: < [) , ]DoBetweenElementsInFold=: ([: {. [ AddGroupWithLeftIfNoGroups [PrependLeftInGroups [: SelectFirstGroupOfMaxLengthSelectGroupsWithLeftLessThanFirstElement ) ([ ,SelectLongerOrStartsWithLonger) ]LongestIncreasingSubsequence=: [: ; [:SelectFirstGroupOfMaxLength [: > [: DoBetweenElementsInFold&.:>/PackElements , GroupOfEmptyGroupInitialStateLongestIncreasingSubsequence=: LongestIncreasingSubsequence f. Full project of tacit version ======================= NB. Find the longest stricty increasing subsequenceNB. Values are the lowest last values yet found for eachsubsequence length.NB. Indices are the indices of these values in the originalsequence.NB. Predecessors are indices to the end of the next lowersubsequenceNB. for each value in the original sequence.NB. The longest sequence is found by index lookup inpredecessors from the indexNB. 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;1ValuesIndicesPredecessorsIndexInitialState=: [: < 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 3AmendValues=: (([: {. [) ; [: {: [) Amend ([: {: [) AdjustLengthValues(7,3) AmendValues 1 2 3;0 1 2;2 2 2;0AmendIndices=: (Index ; [: {: [) Amend ([: {: [) AdjustLengthIndices(7,3) AmendIndices 1 2 3;0 1 2;2 2 2;0AmendPredecessors=: ((([: <: [: {: [){Indices);Index ) AmendPredecessors(7,3) AmendPredecessors 1 2 3;0 1 2;2 2 2;0DoBetweenElementsInFold=: ([,(Values I. [ )) ( [(Values;Indices;AmendPredecessors;1+Index)AmendValues;AmendIndices;Predecessors;Index) ]3 DoBetweenElementsInFold 1 2;1 2;0 1 1 2;3Reconstruct=: [: (Predecessors PickPower ([: i. [: - [: #Indices);[: {: Indices) [: > ]Reconstruct < 1 2 3;1 2 3;0 1 1 2;4LongestIncreasingSubsequenceIndices=: [: Reconstruct [:DoBetweenElementsInFold&.:>/ ([: |. PackValues) ,ValuesIndicesPredecessorsIndexInitialState( 7 DoBetweenElementsInFold [: >ValuesIndicesPredecessorsIndexInitialState)7 1 2 3( 1 DoBetweenElementsInFold (7 DoBetweenElementsInFold [: >ValuesIndicesPredecessorsIndexInitialState))7 1 2 3( 2 DoBetweenElementsInFold (1 DoBetweenElementsInFold (7DoBetweenElementsInFold [: >ValuesIndicesPredecessorsIndexInitialState)))7 1 2 3( 3 DoBetweenElementsInFold (2 DoBetweenElementsInFold (1DoBetweenElementsInFold (7 DoBetweenElementsInFold [: >ValuesIndicesPredecessorsIndexInitialState))))7 1 2 3Reconstruct < (3 DoBetweenElementsInFold ( 2DoBetweenElementsInFold ( 1 DoBetweenElementsInFold ( 7DoBetweenElementsInFold [: >ValuesIndicesPredecessorsIndexInitialState))))7 1 2 3LongestIncreasingSubsequence=: ([: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 seehttp://www.jsoftware.com/forums.htm----------------------------------------------------------------------For information about J forums seehttp://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 seehttp://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