[Jprogramming] Greatest Increasing Subsequence

Erling Hellenäs erling at erlinghellenas.se
Fri Sep 16 07:23:16 UTC 2016 

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

More information about the Programming mailing list