Re: [Jprogramming] Greatest Increasing Subsequence

[Erling Hellenäs]

Yes, and it's about the ease with which you find a solution.

It seems Insert should normally be more concise than writing the loop, 
and tacit code more concise than explicit, but in this case, with these 
complications and others, the looping explicit code is clearly to prefer.


/Erling

On 2016-09-16 15:31, Raul Miller wrote:

The boxing is a measurable performance issue, since you wind up doing a lot
of boxed operations.

The reversing is not a measurable performance issue, since it only happens
twice and because the overall algorithm is does so much more work.

Both of these are "conciseness" issues, however. But if conciseness were
the overriding goal then at some point you would be considering explicit
code.



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

Re: [Jprogramming] Greatest Increasing Subsequence

[Raul Miller]

The boxing is a measurable performance issue, since you wind up doing a lot
of boxed operations.

The reversing is not a measurable performance issue, since it only happens
twice and because the overall algorithm is does so much more work.

Both of these are "conciseness" issues, however. But if conciseness were
the overriding goal then at some point you would be considering explicit
code.

-- 
Raul


On Fri, Sep 16, 2016 at 3:23 AM, Erling Hellenäs 
wrote:

> 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=:([:>[:{.[)`([:>[:{:[)`] }

Re: [Jprogramming] Greatest Increasing Subsequence

[Erling Hellenäs]

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 

Re: [Jprogramming] Greatest Increasing Subsequence

[Erling Hellenäs]

The best tacit solution I found so far. Minor adjustments, slightly faster.

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.


Values=: [: > 0 { ]

Indices=: [: > 1 { ]

Predecessors=: [: > 2 { ]

Index=: [: > 3 { ]

NewValue=: 0 { [

NewValueIndex=: 1 { [

AmendItem=:(0 { [)`(1 { [)`] }

ValuesIndicesPredecessorsIndexInitialState=: [: < a:"_ , a:"_ , (# $ 2:) 
; 0:


PackValues=: <@+

AppendValuesAndIndices=: (Values,NewValue);Indices,Index

AmendValuesAndIndices=: ([ AmendItem Values);(Index , NewValueIndex) 
AmendItem Indices


AmendOrAppend=: 
AppendValuesAndIndices`AmendValuesAndIndices@.(NewValueIndex < [: # Values)


AmendPredecessors=: ((([: <: NewValueIndex){Indices),Index ) AmendItem 
Predecessors


DoBetweenElementsInFold=: ([,(Values I. [ )) ( [ 
(Values;Indices;AmendPredecessors;1+Index) 
AmendOrAppend,Predecessors;Index) ]


PickPower=: {~^:([`([: > 0 { ])`([: > 1 { ]))

Reconstruct=: [: (Predecessors PickPower ([: i. [: - [: # Indices);[: {: 
Indices) [: > ]


LongestIncreasingSubsequenceIndices=: [: Reconstruct [: 
DoBetweenElementsInFold&.:>/ ([: |. PackValues) , 
ValuesIndicesPredecessorsIndexInitialState


LongestIncreasingSubsequence=: ([: LongestIncreasingSubsequenceIndices 
]) { ]


LongestIncreasingSubsequence=: LongestIncreasingSubsequence f.


On 2016-09-15 14:53, 'Mike Day' via Programming wrote:

Something to look forward to! (Henry's work on tacit amend/append, below)

Meanwhile,  here's a version of Fredman/Knuth that re-introduces 
indexing to
allow capture of the required subsequence as well as its length. It's 
marginally

slower than longascseq1 for ?.~100,  although it's now virtually the
same algorithm.

Not so easy to tacitise...

NB. version of Fredman/Knuth with indexing
lisfi =: 3 : 0
p  =. <. x   =. y  NB. predecessors/values
if. 2>#x do. x return. end.
T  =. {.x
i  =. 0NB. index array
for_xj. }.x do.
   xji   =. >:xj_index
   if. xj > {:T do.
 T =. T,  xj
 i =. i,  xji
 m =. <:#i
   else.
 m =. T I. xj
 T =. xj  m } T
 i =. xji m } i
   end.
   p  =. (i{~<:m) xji } p
end.
x{~p{~^:(i.-#i){:i
)

Mike

On 15/09/2016 13: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 

Re: [Jprogramming] Greatest Increasing Subsequence

[Henry Rich]

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 ) # ]

Re: [Jprogramming] Greatest Increasing Subsequence

['Mike Day' via Programming]

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 

Re: [Jprogramming] Greatest Increasing Subsequence

[Erling Hellenäs]

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

Re: [Jprogramming] Greatest Increasing Subsequence

[Erling Hellenäs]

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

Re: [Jprogramming] Greatest Increasing Subsequence

['Mike Day' via Programming]

I should probably have gone straight to Knuth,  but here's what I 
managed with
Fredman's account of the algorithm.  The tacit version is surprisingly 
easy!!!


Note that this algorithm does not in general produce the same 
subsequence as
the Wikipedia alternative,  but it is of equal length,  and is a bit 
quicker.
Also, the subsquence's indices are not available,  so it is deficient 
compared
to longascseq etc; the latter are  /: -like while lisf and taclisf 
(below) are

not.

NB. Fredman/Knuth algorithm as in
NB. https://dx.doi.org/10.1016%2F0012-365X%2875%2990103-X

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
)

NB. see how to do tacit amend/append xi in T
NB.10 ([ I.~ } ]`(,~)@.(>{:) ) 7 9 11  NB. 10 <: 11, so insert
NB. 7 9 10
NB.20 ([ I.~ } ]`(,~)@.(>{:) ) 7 9 11  NB. 20 > 11, so append
NB. 7 9 11 20
   doxj =: ([ I.~ } ]`(,~)@.(>{:) )  NB. amend T (rha) with xj (lha)

   taclisf =: doxj / @ |.NB. closed form on array

   q =: ?.~ 100

   timer'(#; 10&{.) longascseq1 q'
+-+++
|8|1971|647 1210 1309 1399 1450 1688 1993 2006 2349 2729|
+-+++

   timer'(#; 10&{.) lisf q'
+-+++
|4.238|1971|0 2 4 7 9 12 13 20 28 37|
+-+++

   timer'(#; 10&{.) taclisf q'
+-+++
|4.742|1971|0 2 4 7 9 12 13 20 28 37|
+-+++

Space requirements are similar for all 3, at ~ 8.4 Mb,
with lisf <~ taclisf <~ longascseq1 , in this case.

Mike

Please note that I've snipped earlier history (below)
from this correspondence.

On 15/09/2016 09:28, Erling Hellenäs wrote:

The Knuth reference can be downloaded here:

http://www.mediafire.com/download/3btahsyzax4w7xp/Vol%2C3+SortingAndSearching-Donald+Knuth.pdf 



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




[ sorry, but I've snipped the rest - Mike]

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

Re: [Jprogramming] Greatest Increasing Subsequence

[Erling Hellenäs]

The Knuth reference can be downloaded here:

http://www.mediafire.com/download/3btahsyzax4w7xp/Vol%2C3+SortingAndSearching-Donald+Knuth.pdf

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=: [: < 

Re: [Jprogramming] Greatest Increasing Subsequence

['Mike Day' via Programming]

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

Re: [Jprogramming] Greatest Increasing Subsequence

[Erling Hellenäs]

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 ) 

Re: [Jprogramming] Greatest Increasing Subsequence

['Mike Day' via Programming]

It depends on both m and n in ?m#n

Also, note that it's better to move definition of the input outside the 
time

(and space) test.

Using ?. to fix the samples,  and 1 ts to save waiting on longer arguments:

   ts each '#longascseq1 q';'#longascseq2 q'[q =: ?.~10NB. set outside
+--+--+
|0.475994 1.18106e6|0.675194 1.17299e6|
+--+--+
   ts each '#longascseq1 ?.~10';'#longascseq2 ?.~10' NB. set inside
+--+--+
|0.493492 6.42419e6|0.629799 6.41613e6|
+--+--+
   1 ts each '#longascseq1 q';'#longascseq2 q'[q =: ?.~100
+-+-+
|3.38978 8.74317e6|7.69395 8.72691e6|
+-+-+
   1 ts each '#longascseq1 ?.~100';'#longascseq2 ?.~100'
+-++
|3.71289 5.06865e7|8.4527 5.06702e7|
+-++
It appears that the estimate of space used is more strongly influenced
than time,  here.

I'm wondering why you tested equality in this way:
   (([: longascseq1 ]) *./ . = [: longascseq2 ])a

Isn't it sufficient to test
(longascseq1 -: longascseq2 )l

1   ?

Thanks,
Mike



On 14/09/2016 09:30, Erling Hellenäs wrote:
I can't verify that. For some values it is faster, yes, but it seems 
measurements with 1 000 000 items shows your original assumption was 
correct. See below. /Erling


NB. Find the longest ascending subsequence in y

NB. y is a list of numbers

NB. Result is indexes of the values that form the largest ascending 
sequence in y


longascseq1 =: 3 : 0"1

NB. Initialize the arrays

valueofminendvalue =. indexofminendvalue =. 0$0

predecessor =. (#y)$2

NB. process the input

for_v. y do.

NB. j{indexofminendvalue is the index in the original input of the 
smallest


NB. input value that ends a sequence of length j+1. valueofminendvalue is

NB. the corresponding value.

NB. When a new value v comes in, we see how many previous values are 
smaller;


NB. calling that value j, we see that the new value becomes the 
smallest value


NB. that ends a subsequence of length j+1

if. (#valueofminendvalue) = j =. valueofminendvalue I. v do.

NB. New highest value (and therefore new greatest length): extend the 
arrays


valueofminendvalue =. valueofminendvalue , v

indexofminendvalue =. indexofminendvalue , v_index

else.

NB. New low value for an existing length: update for that length

valueofminendvalue =. v j} valueofminendvalue

indexofminendvalue =. v_index j} indexofminendvalue

end.

NB. Get a snapshot of the predecessor to the added point at the time 
it was


NB. added. This predecessor is given by the end of the next-shorter 
subsequence.


predecessor =. (indexofminendvalue {~ <: j) v_index} predecessor NB. 
wraps if j=0, but who cares?


end.

NB. Reconstruct the chain of predecessors from the end

predecessor {~^:(i.-#indexofminendvalue) {: indexofminendvalue

)

NB. Find the longest ascending subsequence in y

NB. y is a list of numbers

NB. Result is indexes of the values that form the largest ascending 
sequence in y


longascseq2 =: 3 : 0"1

NB. Initialize the arrays

valueofminendvalue =. indexofminendvalue =. 0$0

predecessor =. (#y)$2

NB. process the input

for_v. y do.

NB. j{indexofminendvalue is the index in the original input of the 
smallest


NB. input value that ends a sequence of length j+1. valueofminendvalue is

NB. the corresponding value.

NB. When a new value v comes in, we see how many previous values are 
smaller;


NB. calling that value j, we see that the new value becomes the 
smallest value


NB. that ends a subsequence of length j+1

NB. if. (#valueofminendvalue) = j =. valueofminendvalue I. v do.

if. (#indexofminendvalue) = j =. v I.~ indexofminendvalue{y do.

NB. valueofminendvalue =. valueofminendvalue , v

indexofminendvalue =. indexofminendvalue , v_index

else.

NB. valueofminendvalue =. v j} valueofminendvalue

indexofminendvalue =. v_index j} indexofminendvalue

end.

NB. Get a snapshot of the predecessor to the added point at the time 
it was


NB. added. This predecessor is given by the end of the next-shorter 
subsequence.


predecessor =. (indexofminendvalue {~ <: j) v_index} predecessor NB. 
wraps if j=0, but who cares?


end.

NB. Reconstruct the chain of predecessors from the end

predecessor {~^:(i.-#indexofminendvalue) {: indexofminendvalue

)

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

(longascseq1 { ])l

1 2 3 4 5 7 11 19

(longascseq2 { ])l

1 2 3 4 5 7 11 19

a=:1?1

(([: longascseq1 ]) *./ . = [: longascseq2 ])a

1

ts'(longascseq1 { ]) 1?1'

0.0439489 830592

ts'(longascseq2 { ]) 1?1'

0.0415926 830720

ts'(longascseq1 { ]) ?1$1'

0.044282 439424

ts'(longascseq2 { ]) ?1$1'

0.0410495 435840

ts'(longascseq1 { ]) 10?10'

0.446059 6.42803e6

ts'(longascseq2 { ]) 10?10'

0.468622 6.41946e6

ts'(longascseq1 { ]) 

Re: [Jprogramming] Greatest Increasing Subsequence

[Erling Hellenäs]

I can't verify that. For some values it is faster, yes, but it seems 
measurements with 1 000 000 items shows your original assumption was 
correct. See below. /Erling


NB. Find the longest ascending subsequence in y

NB. y is a list of numbers

NB. Result is indexes of the values that form the largest ascending 
sequence in y


longascseq1 =: 3 : 0"1

NB. Initialize the arrays

valueofminendvalue =. indexofminendvalue =. 0$0

predecessor =. (#y)$2

NB. process the input

for_v. y do.

NB. j{indexofminendvalue is the index in the original input of the smallest

NB. input value that ends a sequence of length j+1. valueofminendvalue is

NB. the corresponding value.

NB. When a new value v comes in, we see how many previous values are 
smaller;


NB. calling that value j, we see that the new value becomes the smallest 
value


NB. that ends a subsequence of length j+1

if. (#valueofminendvalue) = j =. valueofminendvalue I. v do.

NB. New highest value (and therefore new greatest length): extend the arrays

valueofminendvalue =. valueofminendvalue , v

indexofminendvalue =. indexofminendvalue , v_index

else.

NB. New low value for an existing length: update for that length

valueofminendvalue =. v j} valueofminendvalue

indexofminendvalue =. v_index j} indexofminendvalue

end.

NB. Get a snapshot of the predecessor to the added point at the time it was

NB. added. This predecessor is given by the end of the next-shorter 
subsequence.


predecessor =. (indexofminendvalue {~ <: j) v_index} predecessor NB. 
wraps if j=0, but who cares?


end.

NB. Reconstruct the chain of predecessors from the end

predecessor {~^:(i.-#indexofminendvalue) {: indexofminendvalue

)

NB. Find the longest ascending subsequence in y

NB. y is a list of numbers

NB. Result is indexes of the values that form the largest ascending 
sequence in y


longascseq2 =: 3 : 0"1

NB. Initialize the arrays

valueofminendvalue =. indexofminendvalue =. 0$0

predecessor =. (#y)$2

NB. process the input

for_v. y do.

NB. j{indexofminendvalue is the index in the original input of the smallest

NB. input value that ends a sequence of length j+1. valueofminendvalue is

NB. the corresponding value.

NB. When a new value v comes in, we see how many previous values are 
smaller;


NB. calling that value j, we see that the new value becomes the smallest 
value


NB. that ends a subsequence of length j+1

NB. if. (#valueofminendvalue) = j =. valueofminendvalue I. v do.

if. (#indexofminendvalue) = j =. v I.~ indexofminendvalue{y do.

NB. valueofminendvalue =. valueofminendvalue , v

indexofminendvalue =. indexofminendvalue , v_index

else.

NB. valueofminendvalue =. v j} valueofminendvalue

indexofminendvalue =. v_index j} indexofminendvalue

end.

NB. Get a snapshot of the predecessor to the added point at the time it was

NB. added. This predecessor is given by the end of the next-shorter 
subsequence.


predecessor =. (indexofminendvalue {~ <: j) v_index} predecessor NB. 
wraps if j=0, but who cares?


end.

NB. Reconstruct the chain of predecessors from the end

predecessor {~^:(i.-#indexofminendvalue) {: indexofminendvalue

)

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

(longascseq1 { ])l

1 2 3 4 5 7 11 19

(longascseq2 { ])l

1 2 3 4 5 7 11 19

a=:1?1

(([: longascseq1 ]) *./ . = [: longascseq2 ])a

1

ts'(longascseq1 { ]) 1?1'

0.0439489 830592

ts'(longascseq2 { ]) 1?1'

0.0415926 830720

ts'(longascseq1 { ]) ?1$1'

0.044282 439424

ts'(longascseq2 { ]) ?1$1'

0.0410495 435840

ts'(longascseq1 { ]) 10?10'

0.446059 6.42803e6

ts'(longascseq2 { ]) 10?10'

0.468622 6.41946e6

ts'(longascseq1 { ]) ?10$10'

0.447244 3.28205e6

ts'(longascseq2 { ]) ?10$10'

0.458428 3.27373e6

ts'(longascseq1 { ]) 100?100'

4.55264 5.07078e7

ts'(longascseq2 { ]) 100?100'

5.98209 5.06932e7

ts'(longascseq1 { ]) ?100$100'

4.42172 2.55429e7

ts'(longascseq2 { ]) ?100$100'

5.83236 2.55252e7


On 2016-09-13 20:38, 'Mike Day' via Programming wrote:

Actually,  the hit on run time gets more significant as the length of the
sequence and/or the optimal subsequence increase, so it's not negligible
for, say, ?100#50,  but fine for ?1#5000, and not too bad
for ?10#5

Mike

On 13/09/2016 19:22, 'Mike Day' via Programming wrote:

Thanks.

It might help to point out that the main loop in Henry Rich's version,
as shown in the wiki page, can be simplified slightly with negligible
effect on run time,  some savings in space,  and doing without the
"sorted value" array.

I'm rather surprised - I'd introduced the array which I'd called mx,
more helpfully called valeofminendvalue by Henry,  to avoid repeated
indirect look-up into the raw input.

Here's a copy of the relevant part of the loop with the removed or
former code commented out:

NB.   if. (#valueofminendvalue) = j =. valueofminendvalue I. v do.
  if. (#indexofminendvalue) = j =. v 

Re: [Jprogramming] Greatest Increasing Subsequence

['Mike Day' via Programming]

Actually,  the hit on run time gets more significant as the length of the
sequence and/or the optimal subsequence increase, so it's not negligible
for, say, ?100#50,  but fine for ?1#5000, and not too bad
for ?10#5

Mike

On 13/09/2016 19:22, 'Mike Day' via Programming wrote:

Thanks.

It might help to point out that the main loop in Henry Rich's version,
as shown in the wiki page, can be simplified slightly with negligible
effect on run time,  some savings in space,  and doing without the
"sorted value" array.

I'm rather surprised - I'd introduced the array which I'd called mx,
more helpfully called valeofminendvalue by Henry,  to avoid repeated
indirect look-up into the raw input.

Here's a copy of the relevant part of the loop with the removed or
former code commented out:

NB.   if. (#valueofminendvalue) = j =. valueofminendvalue I. v do.
  if. (#indexofminendvalue) = j =. v I.~ indexofminendvalue{y do.
NB. valueofminendvalue =. valueofminendvalue , v
indexofminendvalue =. indexofminendvalue , v_index
  else.
NB. valueofminendvalue =. v j} valueofminendvalue
indexofminendvalue =. v_index j} indexofminendvalue
  end.

I won't venture to suggest changes in your code, below!

Mike

On 13/09/2016 17: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 

Re: [Jprogramming] Greatest Increasing Subsequence

['Mike Day' via Programming]

Thanks.

It might help to point out that the main loop in Henry Rich's version,
as shown in the wiki page, can be simplified slightly with negligible
effect on run time,  some savings in space,  and doing without the
"sorted value" array.

I'm rather surprised - I'd introduced the array which I'd called mx,
more helpfully called valeofminendvalue by Henry,  to avoid repeated
indirect look-up into the raw input.

Here's a copy of the relevant part of the loop with the removed or
former code commented out:

NB.   if. (#valueofminendvalue) = j =. valueofminendvalue I. v do.
  if. (#indexofminendvalue) = j =. v I.~ indexofminendvalue{y do.
NB. valueofminendvalue =. valueofminendvalue , v
indexofminendvalue =. indexofminendvalue , v_index
  else.
NB. valueofminendvalue =. v j} valueofminendvalue
indexofminendvalue =. v_index j} indexofminendvalue
  end.

I won't venture to suggest changes in your code, below!

Mike

On 13/09/2016 17: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=: 

Re: [Jprogramming] Greatest Increasing Subsequence

[Erling Hellenäs]

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 

Re: [Jprogramming] Greatest Increasing Subsequence

[Henry Rich]

(x I. y) does use binary search, and requires that y be either 
nonincreasing or nondecreasing.


Length of names has a tiny effect on performance, as the interpreter has 
to compare the name against a stored name.  It is barely noticeable; 
slightly more noticeable when J8.05 added a fast path for singleton 
operations; disappears for local names now that J8.05 prehashes names 
assigned by local assignment.  Not worth mentioning, except that the 
difference between the two programs was so small.


Henry Rich

On 9/10/2016 3:58 AM, 'Mike Day' via Programming wrote:
Yes.  It clearly saves space to have "valueofminendvalue",  my "mx",  
grow
as it needs, rather than to start with maximal length.  I hadn't 
spotted how

to avoid indexed assignment when your "j", my "lo",  increases. No need
for those clunky _1s in the index array!

So then I'm surprised that my space-hungry version doesn't suffer a hit
on the performance of dyadic I. on the maximal length mx .  Does it 
use binary

search?

Also, has length of variable names affected performance in early J 
versions?

I'm just lazy and all thumbs, so have avoided long names!

Thanks,

Mike

On 10/09/2016 00:39, Henry Rich wrote:
They're about the same speed on my machine.  I don't think the 
if-then-else is material.  They're essentially the same algorithm.


(I'm testing on J8.05 beta, where the long names don't affect 
performance)


Henry Rich

On 9/9/2016 7:26 PM, 'Mike Day' via Programming wrote:

Thanks.
I'm sure you know the following,  but it might be worth pointing out:

   longascseq l
6 9 20 21 22 25 26 27

   l{~longascseq l
1 2 3 4 5 7 11 19

   lisM l
1 2 3 4 5 7 11 19

ie, longascseq returns the indices of the/a subsequence.

Very limited testing suggests that it's a little bit slower,
(on 1 elements) but saves space compared to the function,
lisM, that I posted earlier.  I suppose that's because of the
if-then-else block,  though I haven't studied their differences
yet.

Cheers,
Mike

On 09/09/2016 20:09, Henry Rich wrote:

I have created a Wiki page for this, where you can post solutions.

http://code.jsoftware.com/wiki/Essays/Longest_Increasing_Subsequence

I don't think a tacit solution can be efficient, considering how 
many in-place operations are needed.


Henry Rich

On 9/9/2016 1:46 PM, Erling Hellenäs wrote:

Hi all !

This one is considerably faster, near lisJ.

ts'LongestIncreasingSubsequence 1?1'

2.40974 3.808e6

ts'LongestIncreasingSubsequence ?1$1'

2.46657 3.41504e6


It still uses a lot of memory. Handles 100 000 with quite some 
struggle.



ts'LongestIncreasingSubsequence ?10$10'

81.525 3.30742e7

Cheers,

Erling

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. Append the new group to the previous groups.

NB. Removes groups which are both shorter than the new group and 
which starts


NB. with a number which is smaller or equal to the number which 
starts the new group.


NB. When all numbers are drawn one of the longest remaining groups 
is selected.




GroupOfEmptyGroupInitialState=: [: < a:"_

GroupOfEmptyGroupInitialState ''

PackElements=: <@+

PackElements 6 1 3 4 2 8

SelectGroupsWithLeftLessThanFirstElement=: ([: , [ < [: (1 {. ])@> 
]) # ]


PrependLeftInGroups=: ([: < [) ,&.> ]

2 PrependLeftInGroups <4 5

AddGroupWithLeftIfNoGroups=: ((0 = [: # ]) {. [: < [) , ]

2 AddGroupWithLeftIfNoGroups 0 {. SelectFirstGroupOfMaxLength=: ([: ((1 <. #) {. ]) [: I. ([: (] = 
'' $ [: >./ ]) #@>)) { ]


SelectFirstGroupOfMaxLength (<2),(<2 4 5),<2 6 7

StartsWithSmallerOrEqual=: ([: {.@> ])<:[: {: [

Shorter=: ([: #@> ])<[: {. [

LengthAndFirstElement=: [: (# , {.) [: > ]

SelectNotShorterAndStartsWithSmallerOrEqual=: (([: 
LengthAndFirstElement [: {: ]) ( ([: -. Shorter 
*.StartsWithSmallerOrEqual) # ]) [: > [: {. ]) , [: {: ]


SelectNotShorterAndStartsWithSmallerOrEqual ((<1 2),(<3 4 5),(< 4 
5),(< 1 4 5));2 6 7


DoBetweenElementsInFold=: [: 
SelectNotShorterAndStartsWithSmallerOrEqual ] ; [ 
AddGroupWithLeftIfNoGroups [ PrependLeftInGroups [: 
SelectFirstGroupOfMaxLength SelectGroupsWithLeftLessThanFirstElement


2 DoBetweenElementsInFold (<1 2 3),<4 5

LongestIncreasingSubsequence=: [: ; [: SelectFirstGroupOfMaxLength 
[: > [: DoBetweenElementsInFold&.:>/ PackElements , 
GroupOfEmptyGroupInitialState


LongestIncreasingSubsequence=: LongestIncreasingSubsequence f.

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

LongestIncreasingSubsequence 1000?1000

9!:1 [16807

LongestIncreasingSubsequence ?1000$1000

ts=: 6!:2 , 7!:2@] NB. Time and space

Re: [Jprogramming] Greatest Increasing Subsequence

['Mike Day' via Programming]

Thanks.
I'm sure you know the following,  but it might be worth pointing out:

   longascseq l
6 9 20 21 22 25 26 27

   l{~longascseq l
1 2 3 4 5 7 11 19

   lisM l
1 2 3 4 5 7 11 19

ie, longascseq returns the indices of the/a subsequence.

Very limited testing suggests that it's a little bit slower,
(on 1 elements) but saves space compared to the function,
lisM, that I posted earlier.  I suppose that's because of the
if-then-else block,  though I haven't studied their differences
yet.

Cheers,
Mike

On 09/09/2016 20:09, Henry Rich wrote:

I have created a Wiki page for this, where you can post solutions.

http://code.jsoftware.com/wiki/Essays/Longest_Increasing_Subsequence

I don't think a tacit solution can be efficient, considering how many 
in-place operations are needed.


Henry Rich

On 9/9/2016 1:46 PM, Erling Hellenäs wrote:

Hi all !

This one is considerably faster, near lisJ.

ts'LongestIncreasingSubsequence 1?1'

2.40974 3.808e6

ts'LongestIncreasingSubsequence ?1$1'

2.46657 3.41504e6


It still uses a lot of memory. Handles 100 000 with quite some struggle.


ts'LongestIncreasingSubsequence ?10$10'

81.525 3.30742e7

Cheers,

Erling

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. Append the new group to the previous groups.

NB. Removes groups which are both shorter than the new group and 
which starts


NB. with a number which is smaller or equal to the number which 
starts the new group.


NB. When all numbers are drawn one of the longest remaining groups is 
selected.




GroupOfEmptyGroupInitialState=: [: < a:"_

GroupOfEmptyGroupInitialState ''

PackElements=: <@+

PackElements 6 1 3 4 2 8

SelectGroupsWithLeftLessThanFirstElement=: ([: , [ < [: (1 {. ])@> ]) 
# ]


PrependLeftInGroups=: ([: < [) ,&.> ]

2 PrependLeftInGroups <4 5

AddGroupWithLeftIfNoGroups=: ((0 = [: # ]) {. [: < [) , ]

2 AddGroupWithLeftIfNoGroups 0 {. SelectFirstGroupOfMaxLength=: ([: ((1 <. #) {. ]) [: I. ([: (] = '' $ 
[: >./ ]) #@>)) { ]


SelectFirstGroupOfMaxLength (<2),(<2 4 5),<2 6 7

StartsWithSmallerOrEqual=: ([: {.@> ])<:[: {: [

Shorter=: ([: #@> ])<[: {. [

LengthAndFirstElement=: [: (# , {.) [: > ]

SelectNotShorterAndStartsWithSmallerOrEqual=: (([: 
LengthAndFirstElement [: {: ]) ( ([: -. Shorter 
*.StartsWithSmallerOrEqual) # ]) [: > [: {. ]) , [: {: ]


SelectNotShorterAndStartsWithSmallerOrEqual ((<1 2),(<3 4 5),(< 4 
5),(< 1 4 5));2 6 7


DoBetweenElementsInFold=: [: 
SelectNotShorterAndStartsWithSmallerOrEqual ] ; [ 
AddGroupWithLeftIfNoGroups [ PrependLeftInGroups [: 
SelectFirstGroupOfMaxLength SelectGroupsWithLeftLessThanFirstElement


2 DoBetweenElementsInFold (<1 2 3),<4 5

LongestIncreasingSubsequence=: [: ; [: SelectFirstGroupOfMaxLength [: 
> [: DoBetweenElementsInFold&.:>/ PackElements , 
GroupOfEmptyGroupInitialState


LongestIncreasingSubsequence=: LongestIncreasingSubsequence f.

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

LongestIncreasingSubsequence 1000?1000

9!:1 [16807

LongestIncreasingSubsequence ?1000$1000

ts=: 6!:2 , 7!:2@] NB. Time and space

ts'LongestIncreasingSubsequence 1000?1000'

ts'LongestIncreasingSubsequence ?1000$1000'

ts'LongestIncreasingSubsequence 1?1'

ts'LongestIncreasingSubsequence ?1$1'


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

Re: [Jprogramming] Greatest Increasing Subsequence

[Henry Rich]

I have created a Wiki page for this, where you can post solutions.

http://code.jsoftware.com/wiki/Essays/Longest_Increasing_Subsequence

I don't think a tacit solution can be efficient, considering how many 
in-place operations are needed.


Henry Rich

On 9/9/2016 1:46 PM, Erling Hellenäs wrote:

Hi all !

This one is considerably faster, near lisJ.

ts'LongestIncreasingSubsequence 1?1'

2.40974 3.808e6

ts'LongestIncreasingSubsequence ?1$1'

2.46657 3.41504e6


It still uses a lot of memory. Handles 100 000 with quite some struggle.


ts'LongestIncreasingSubsequence ?10$10'

81.525 3.30742e7

Cheers,

Erling

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. Append the new group to the previous groups.

NB. Removes groups which are both shorter than the new group and which 
starts


NB. with a number which is smaller or equal to the number which starts 
the new group.


NB. When all numbers are drawn one of the longest remaining groups is 
selected.




GroupOfEmptyGroupInitialState=: [: < a:"_

GroupOfEmptyGroupInitialState ''

PackElements=: <@+

PackElements 6 1 3 4 2 8

SelectGroupsWithLeftLessThanFirstElement=: ([: , [ < [: (1 {. ])@> ]) # ]

PrependLeftInGroups=: ([: < [) ,&.> ]

2 PrependLeftInGroups <4 5

AddGroupWithLeftIfNoGroups=: ((0 = [: # ]) {. [: < [) , ]

2 AddGroupWithLeftIfNoGroups 0 {. SelectFirstGroupOfMaxLength=: ([: ((1 <. #) {. ]) [: I. ([: (] = '' $ 
[: >./ ]) #@>)) { ]


SelectFirstGroupOfMaxLength (<2),(<2 4 5),<2 6 7

StartsWithSmallerOrEqual=: ([: {.@> ])<:[: {: [

Shorter=: ([: #@> ])<[: {. [

LengthAndFirstElement=: [: (# , {.) [: > ]

SelectNotShorterAndStartsWithSmallerOrEqual=: (([: 
LengthAndFirstElement [: {: ]) ( ([: -. Shorter 
*.StartsWithSmallerOrEqual) # ]) [: > [: {. ]) , [: {: ]


SelectNotShorterAndStartsWithSmallerOrEqual ((<1 2),(<3 4 5),(< 4 
5),(< 1 4 5));2 6 7


DoBetweenElementsInFold=: [: 
SelectNotShorterAndStartsWithSmallerOrEqual ] ; [ 
AddGroupWithLeftIfNoGroups [ PrependLeftInGroups [: 
SelectFirstGroupOfMaxLength SelectGroupsWithLeftLessThanFirstElement


2 DoBetweenElementsInFold (<1 2 3),<4 5

LongestIncreasingSubsequence=: [: ; [: SelectFirstGroupOfMaxLength [: 
> [: DoBetweenElementsInFold&.:>/ PackElements , 
GroupOfEmptyGroupInitialState


LongestIncreasingSubsequence=: LongestIncreasingSubsequence f.

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

LongestIncreasingSubsequence 1000?1000

9!:1 [16807

LongestIncreasingSubsequence ?1000$1000

ts=: 6!:2 , 7!:2@] NB. Time and space

ts'LongestIncreasingSubsequence 1000?1000'

ts'LongestIncreasingSubsequence ?1000$1000'

ts'LongestIncreasingSubsequence 1?1'

ts'LongestIncreasingSubsequence ?1$1'


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


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

Re: [Jprogramming] Greatest Increasing Subsequence

[Erling Hellenäs]

Hi all !

This one is considerably faster, near lisJ.

ts'LongestIncreasingSubsequence 1?1'

2.40974 3.808e6

ts'LongestIncreasingSubsequence ?1$1'

2.46657 3.41504e6


It still uses a lot of memory. Handles 100 000 with quite some struggle.


ts'LongestIncreasingSubsequence ?10$10'

81.525 3.30742e7

Cheers,

Erling

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. Append the new group to the previous groups.

NB. Removes groups which are both shorter than the new group and which 
starts


NB. with a number which is smaller or equal to the number which starts 
the new group.


NB. When all numbers are drawn one of the longest remaining groups is 
selected.




GroupOfEmptyGroupInitialState=: [: < a:"_

GroupOfEmptyGroupInitialState ''

PackElements=: <@+

PackElements 6 1 3 4 2 8

SelectGroupsWithLeftLessThanFirstElement=: ([: , [ < [: (1 {. ])@> ]) # ]

PrependLeftInGroups=: ([: < [) ,&.> ]

2 PrependLeftInGroups <4 5

AddGroupWithLeftIfNoGroups=: ((0 = [: # ]) {. [: < [) , ]

2 AddGroupWithLeftIfNoGroups 0 {. SelectFirstGroupOfMaxLength=: ([: ((1 <. #) {. ]) [: I. ([: (] = '' $ [: 
>./ ]) #@>)) { ]


SelectFirstGroupOfMaxLength (<2),(<2 4 5),<2 6 7

StartsWithSmallerOrEqual=: ([: {.@> ])<:[: {: [

Shorter=: ([: #@> ])<[: {. [

LengthAndFirstElement=: [: (# , {.) [: > ]

SelectNotShorterAndStartsWithSmallerOrEqual=: (([: LengthAndFirstElement 
[: {: ]) ( ([: -. Shorter *.StartsWithSmallerOrEqual) # ]) [: > [: {. ]) 
, [: {: ]


SelectNotShorterAndStartsWithSmallerOrEqual ((<1 2),(<3 4 5),(< 4 5),(< 
1 4 5));2 6 7


DoBetweenElementsInFold=: [: SelectNotShorterAndStartsWithSmallerOrEqual 
] ; [ AddGroupWithLeftIfNoGroups [ PrependLeftInGroups [: 
SelectFirstGroupOfMaxLength SelectGroupsWithLeftLessThanFirstElement


2 DoBetweenElementsInFold (<1 2 3),<4 5

LongestIncreasingSubsequence=: [: ; [: SelectFirstGroupOfMaxLength [: > 
[: DoBetweenElementsInFold&.:>/ PackElements , GroupOfEmptyGroupInitialState


LongestIncreasingSubsequence=: LongestIncreasingSubsequence f.

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

LongestIncreasingSubsequence 1000?1000

9!:1 [16807

LongestIncreasingSubsequence ?1000$1000

ts=: 6!:2 , 7!:2@] NB. Time and space

ts'LongestIncreasingSubsequence 1000?1000'

ts'LongestIncreasingSubsequence ?1000$1000'

ts'LongestIncreasingSubsequence 1?1'

ts'LongestIncreasingSubsequence ?1$1'


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

Re: [Jprogramming] Greatest Increasing Subsequence

[Louis de Forcrand]

Indeed lisL does return several results. I believe one verb I wrote returned 
all subsequences of maximal length, but the (much faster) version which is 
referred to by lisL only returns some longest subsequences. They should all be 
correct.

Louis

> On 09 Sep 2016, at 17:04, Raul Miller  wrote:
> 
> Hmm... thinking that through,
> 
> NB. longest sequence lengths should all match
> assert 1=#~.{:@$@>(lisI; lisJ; lisM; lisL; lisEH) a
> 
> (And also could use a verification that each longest sequence is a valid 
> one...)
> 
> Thanks,
> 
> -- 
> Raul
> 
> 
> On Fri, Sep 9, 2016 at 10:30 AM, Erling Hellenäs
>  wrote:
>> Hi all !
>> 
>> Good point. It seems lisI gives strange results. lisL sometimes gives
>> several results, which are probably all correct. There can be many different
>> longest strictly increasing subsequences.
>> 
>> a
>> 
>> 4 12 10 23 18 19 8 7 5 2 0 16 15 11 1 9 22 3 13 14 21 17 24 20 6
>> 
>> lisI a
>> 
>> 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 2
>> 2 2 2 2 2 2 2 2 2 2 2 2 2 3 3 3 3 3 3 3 3 3 3 3 3 3 4 4 4 5
>> 
>> lisJ a
>> 
>> 0 1 3 13 14 17 20
>> 
>> lisM a
>> 
>> 0 1 3 13 14 17 20
>> 
>> lisL a
>> 
>> 0 1 3 13 14 17 20
>> 
>> 4 5 9 13 14 17 20
>> 
>> lisXR a
>> 
>> 0 1 3 13 14 17 20
>> 
>> lisEH a
>> 
>> 0 1 3 13 14 17 20
>> 
>> 
>> Cheers,
>> Erling
>> 
>> 
>> 
>>> On 2016-09-09 16:02, Raul Miller wrote:
>>> 
>>> 1=#~.(lisI; lisJ; lisM; lisL; lisEH) a
>> 
>> 
>> --
>> 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

Re: [Jprogramming] Greatest Increasing Subsequence

[Raul Miller]

Hmm... thinking that through,

NB. longest sequence lengths should all match
assert 1=#~.{:@$@>(lisI; lisJ; lisM; lisL; lisEH) a

(And also could use a verification that each longest sequence is a valid one...)

Thanks,

-- 
Raul


On Fri, Sep 9, 2016 at 10:30 AM, Erling Hellenäs
 wrote:
> Hi all !
>
> Good point. It seems lisI gives strange results. lisL sometimes gives
> several results, which are probably all correct. There can be many different
> longest strictly increasing subsequences.
>
> a
>
> 4 12 10 23 18 19 8 7 5 2 0 16 15 11 1 9 22 3 13 14 21 17 24 20 6
>
> lisI a
>
> 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 2
> 2 2 2 2 2 2 2 2 2 2 2 2 2 3 3 3 3 3 3 3 3 3 3 3 3 3 4 4 4 5
>
> lisJ a
>
> 0 1 3 13 14 17 20
>
> lisM a
>
> 0 1 3 13 14 17 20
>
> lisL a
>
> 0 1 3 13 14 17 20
>
> 4 5 9 13 14 17 20
>
> lisXR a
>
> 0 1 3 13 14 17 20
>
> lisEH a
>
> 0 1 3 13 14 17 20
>
>
> Cheers,
> Erling
>
>
>
> On 2016-09-09 16:02, Raul Miller wrote:
>>
>> 1=#~.(lisI; lisJ; lisM; lisL; lisEH) a
>
>
> --
> For information about J forums see http://www.jsoftware.com/forums.htm
--
For information about J forums see http://www.jsoftware.com/forums.htm

Re: [Jprogramming] Greatest Increasing Subsequence

[Erling Hellenäs]

Hi all !

Good point. It seems lisI gives strange results. lisL sometimes gives 
several results, which are probably all correct. There can be many 
different longest strictly increasing subsequences.


a

4 12 10 23 18 19 8 7 5 2 0 16 15 11 1 9 22 3 13 14 21 17 24 20 6

lisI a

0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 
1 2 2 2 2 2 2 2 2 2 2 2 2 2 2 3 3 3 3 3 3 3 3 3 3 3 3 3 4 4 4 5


lisJ a

0 1 3 13 14 17 20

lisM a

0 1 3 13 14 17 20

lisL a

0 1 3 13 14 17 20

4 5 9 13 14 17 20

lisXR a

0 1 3 13 14 17 20

lisEH a

0 1 3 13 14 17 20


Cheers,
Erling



On 2016-09-09 16:02, Raul Miller wrote:

1=#~.(lisI; lisJ; lisM; lisL; lisEH) a


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

Re: [Jprogramming] Greatest Increasing Subsequence

[Raul Miller]

One thing I keep meaning to do, when i see stuff like this, is verify
that the various versions are giving the same results for the same
test arguments. (In the past, I have seen timing examples where we
were comparing timings on code that gave different results.)

I haven't done that here, yet, but I can recommend an approach. Something like:

   assert 1=#~.(lisI; lisJ; lisM; lisL; lisEH) a

Thanks,

-- 
Raul


On Fri, Sep 9, 2016 at 9:39 AM, Erling Hellenäs
 wrote:
> Hi all !
>
> I made a new version. The code is below. This is the present scoreboard:
>
> a=: 25 ? 25
>
> timespacex 'lisI a'
>
> 0.000296778 3584
>
> timespacex 'lisJ a'
>
> 0.000545234 3712
>
> timespacex 'lisM a'
>
> 0.000131711 10752
>
> timespacex 'lisL a'
>
> 0.000174047 11776
>
> timespacex 'lisXR a' NB. comment out for larger arrays,a.
>
> 0.0101456 247424
>
> timespacex 'lisEH a'
>
> 0.000304476 14208
>
>
> a=: 1000 ? 1000
>
> timespacex 'lisI a'
>
> 0.0226869 538880
>
> timespacex 'lisJ a'
>
> 0.0577798 1.13357e6
>
> timespacex 'lisM a'
>
> 0.0046749 45952
>
> timespacex 'lisL a'
>
> 0.161294 594176
>
> NB.timespacex 'lisXR a' NB. comment out for larger arrays,a.
>
> timespacex 'lisEH a'
>
> 0.236193 718720
>
>
> a=: 1 ? 1
>
> timespacex 'lisI a'
>
> 0.311934 1.69006e7
>
> timespacex 'lisJ a'
>
> 1.45356 2.31916e7
>
> timespacex 'lisM a'
>
> 0.04604 548736
>
> timespacex 'lisL a'
>
> 17.0889 1.31657e7
>
> NB.timespacex 'lisXR a' NB. comment out for larger arrays,a.
>
> timespacex 'lisEH a'
>
> 26.5314 1.44383e7
>
>
> It is hard to create a good tacit solution?
>
>
> Cheers,
>
> Erling
>
>
>
> NB.===
>
>
> NB. Jon - bizarre version. Uses anonymous verbs for most of the logic.
>
> NB. Slow and, uses huge amounts of memory.
>
> appendOrInsert=:(3 : 'insert max' [ 3 :
> '(max=:<:#lst)[(min=:0)[val=:i{r[i=:y')`(3 : '(lst=:lst,y)[prev=:(_1{lst) y}
> prev')@.(3 : '(val>({:lst){r)[val=:y{r')
>
> insert=:(3 : '(prev=: ((y-1){lst)i}prev)[(lst=: i y }lst)' ] ])@:(3 :
> 'mid'`(3 : 'min=: mid+1')@.(3 :
> '(val>(mid{lst){r)[(mid=:<.(min+y)%2)')^:(0&<)^:_)
>
>
> lisJ =: 3 : 0
>
> r=:y NB. array
>
> [val=:0[max=:0[mid=:0[min=:0 NB. useful numbers
>
> lst=:0 NB. list of indices
>
> prev=: (#y)#0 NB. previous indices
>
> i=:0 NB. current index
>
>
> appendOrInsert"0 >: i.<: # y NB. append the items, or insert them, into lst
> (and update prev)
>
> res=:''
>
> ptr=: _1{lst
>
> (ptr)^:(#lst) res
>
> |. res
>
> )
>
>
> buildEx =: 4 : 0
>
> res=:y,ptr{r
>
> ptr=: ptr{prev
>
> res
>
> )
>
>
>
> NB.===
>
>
>
> NB. Imperative version. just for benchmarking
>
> lisI =: 3 : 0
>
> lst =: 0
>
> r=: y
>
> parent=: (#y)#0
>
> for_i.>:i.<:# r do.
>
> if.((i{r) > ({: lst){r ) do.
>
> parent=:(_1{lst) i}parent
>
> lst =: lst, i
>
> else.
>
> min=: 0
>
> max =: <:#lst
>
> while. min < max do.
>
> mid =: <. (min + max) % 2
>
> if. (i{r) > ((mid { lst{r)) do. min =: mid + 1
>
> else. max =: mid end.
>
> end.
>
> lst=: (i) max} lst
>
> parent=: ((max-1){lst)(i}) parent
>
> end.
>
> end.
>
> res=: ''
>
> ptr=: _1{lst
>
> while. (# res) < # lst do.
>
> res=:res,ptr{r
>
> ptr=:ptr{parent
>
> end.
>
> I. res
>
> )
>
>
>
>
> NB.===
>
>
>
> NB. Mike's version.
>
>
> lisM =: 3 : 0
>
> n =. #x =. y
>
> if. 2>#x do. x return. end. NB. special case empty or singleton array
>
> if. (-:/:~)x do. ~.x return. end. NB. special case sorted arrays
>
> if. (-:\:~)x do. {.x return. end.
>
> p =. n#0
>
> NB. seed m with trailing _1 so that final L (as in wiki algorithm) can be
> found
>
> m =. n 0 } _1#~>:n
>
> NB. set up sorted mx, with just the first element of x, so that I. works
>
> mx =. ({.x) 1 } (<:<./x), n#>:>./x
>
> for_i. i.n do.
>
> xi =. i{x
>
> lo =. mx I. xi
>
> p =. (m{~<:lo) i } p NB. better than appending to short p for larger x
>
> m =. i lo } m
>
> mx =. xi lo } mx
>
> end.
>
> |. x{~(p{~])^:(i.L) m{~ L =. <: m i. _1
>
> )
>
>
> NB.===
>
>
> NB. Louis' version.
>
> p=: ] , [ ,&.> ] #~ (< {.&>) (= >./)@:* #&>@]
>
> e=: }:@>@(#~ (= >./)@:(#&>))@>
>
>
> s=: [: e (<<_) p&.>/@,~ <"0
>
> pi=: ] , [ ,&.> ] {~ (< {.&>) (i. >./)@:* #&>@]
>
> lisL =: [: e (<<_) pi&.>/@,~ <"0 NB. <- this one.
>
>
> f=: ((] >: (-~ >./)) #&>) # ]
>
>
> P=: ] , [ ,&.> ] #~ (< {.&>) (,@[ #^:_1 (= >./)@#) #&>@]
>
> sp=: [: e (<<_) ({:@[ f {.@[ P ])&.>/@,~ (,&.> i.@#)
>
>
>
>
> NB.===
>
>
>
> NB. Xiao's version with Raul's modifications. Renamed verbs to avoid
> clashing.
>
>
> NB. dyads
>
> exr=: (1 + {:@[ < ]) {. [ ; ,
>
> hxr=: [: ; exr&.>
>
>
> NB. monads
>
> gxr=: (}.@] ;~ {.@] ; (hxr {.))&>/
>
> cxr=: ({::~ [: (i. >./) #@>)@>@{.
>
> dxr=: (<_) ; ]
>
> lisXR=: ([: cxr gxr^:(#@(>@{:)))@dxr
>
>
> 

Re: [Jprogramming] Greatest Increasing Subsequence

[Erling Hellenäs]

Hi all !

I made a new version. The code is below. This is the present scoreboard:

a=: 25 ? 25

timespacex 'lisI a'

0.000296778 3584

timespacex 'lisJ a'

0.000545234 3712

timespacex 'lisM a'

0.000131711 10752

timespacex 'lisL a'

0.000174047 11776

timespacex 'lisXR a' NB. comment out for larger arrays,a.

0.0101456 247424

timespacex 'lisEH a'

0.000304476 14208


a=: 1000 ? 1000

timespacex 'lisI a'

0.0226869 538880

timespacex 'lisJ a'

0.0577798 1.13357e6

timespacex 'lisM a'

0.0046749 45952

timespacex 'lisL a'

0.161294 594176

NB.timespacex 'lisXR a' NB. comment out for larger arrays,a.

timespacex 'lisEH a'

0.236193 718720


a=: 1 ? 1

timespacex 'lisI a'

0.311934 1.69006e7

timespacex 'lisJ a'

1.45356 2.31916e7

timespacex 'lisM a'

0.04604 548736

timespacex 'lisL a'

17.0889 1.31657e7

NB.timespacex 'lisXR a' NB. comment out for larger arrays,a.

timespacex 'lisEH a'

26.5314 1.44383e7


It is hard to create a good tacit solution?


Cheers,

Erling


NB.=== 




NB. Jon - bizarre version. Uses anonymous verbs for most of the logic.

NB. Slow and, uses huge amounts of memory.

appendOrInsert=:(3 : 'insert max' [ 3 : 
'(max=:<:#lst)[(min=:0)[val=:i{r[i=:y')`(3 : 
'(lst=:lst,y)[prev=:(_1{lst) y} prev')@.(3 : '(val>({:lst){r)[val=:y{r')


insert=:(3 : '(prev=: ((y-1){lst)i}prev)[(lst=: i y }lst)' ] ])@:(3 : 
'mid'`(3 : 'min=: mid+1')@.(3 : 
'(val>(mid{lst){r)[(mid=:<.(min+y)%2)')^:(0&<)^:_)



lisJ =: 3 : 0

r=:y NB. array

[val=:0[max=:0[mid=:0[min=:0 NB. useful numbers

lst=:0 NB. list of indices

prev=: (#y)#0 NB. previous indices

i=:0 NB. current index


appendOrInsert"0 >: i.<: # y NB. append the items, or insert them, into 
lst (and update prev)


res=:''

ptr=: _1{lst

(ptr)^:(#lst) res

|. res

)


buildEx =: 4 : 0

res=:y,ptr{r

ptr=: ptr{prev

res

)



NB.===



NB. Imperative version. just for benchmarking

lisI =: 3 : 0

lst =: 0

r=: y

parent=: (#y)#0

for_i.>:i.<:# r do.

if.((i{r) > ({: lst){r ) do.

parent=:(_1{lst) i}parent

lst =: lst, i

else.

min=: 0

max =: <:#lst

while. min < max do.

mid =: <. (min + max) % 2

if. (i{r) > ((mid { lst{r)) do. min =: mid + 1

else. max =: mid end.

end.

lst=: (i) max} lst

parent=: ((max-1){lst)(i}) parent

end.

end.

res=: ''

ptr=: _1{lst

while. (# res) < # lst do.

res=:res,ptr{r

ptr=:ptr{parent

end.

I. res

)




NB.===



NB. Mike's version.


lisM =: 3 : 0

n =. #x =. y

if. 2>#x do. x return. end. NB. special case empty or singleton array

if. (-:/:~)x do. ~.x return. end. NB. special case sorted arrays

if. (-:\:~)x do. {.x return. end.

p =. n#0

NB. seed m with trailing _1 so that final L (as in wiki algorithm) can 
be found


m =. n 0 } _1#~>:n

NB. set up sorted mx, with just the first element of x, so that I. works

mx =. ({.x) 1 } (<:<./x), n#>:>./x

for_i. i.n do.

xi =. i{x

lo =. mx I. xi

p =. (m{~<:lo) i } p NB. better than appending to short p for larger x

m =. i lo } m

mx =. xi lo } mx

end.

|. x{~(p{~])^:(i.L) m{~ L =. <: m i. _1

)


NB.===


NB. Louis' version.

p=: ] , [ ,&.> ] #~ (< {.&>) (= >./)@:* #&>@]

e=: }:@>@(#~ (= >./)@:(#&>))@>


s=: [: e (<<_) p&.>/@,~ <"0

pi=: ] , [ ,&.> ] {~ (< {.&>) (i. >./)@:* #&>@]

lisL =: [: e (<<_) pi&.>/@,~ <"0 NB. <- this one.


f=: ((] >: (-~ >./)) #&>) # ]


P=: ] , [ ,&.> ] #~ (< {.&>) (,@[ #^:_1 (= >./)@#) #&>@]

sp=: [: e (<<_) ({:@[ f {.@[ P ])&.>/@,~ (,&.> i.@#)




NB.===



NB. Xiao's version with Raul's modifications. Renamed verbs to avoid 
clashing.



NB. dyads

exr=: (1 + {:@[ < ]) {. [ ; ,

hxr=: [: ; exr&.>


NB. monads

gxr=: (}.@] ;~ {.@] ; (hxr {.))&>/

cxr=: ({::~ [: (i. >./) #@>)@>@{.

dxr=: (<_) ; ]

lisXR=: ([: cxr gxr^:(#@(>@{:)))@dxr


NB.===


NB. Erling's version


GroupOfEmptyGroupInitialState=: [: < a:"_

PackElements=: <@+

SelectGroupsWithLeftLessThanFirstElement=: ([: , [ < [: (1 {. ])@> ]) # ]

PrependLeftInGroups=: ([: < [) ,&.> ]

AddGroupWithLeftIfNoGroups=: ((0 = [: # ]) {. [: < [) , ]

SelectFirstGroupOfMaxLength=: ([: ((1 <. #) {. ]) [: I. ([: (] = '' $ [: 
>./ ]) #@>)) { ]


DoBetweenElementsInFold=: ] , [ AddGroupWithLeftIfNoGroups [ 
PrependLeftInGroups [: SelectFirstGroupOfMaxLength 
SelectGroupsWithLeftLessThanFirstElement


LongestIncreasingSubsequence=: [: ; [: SelectFirstGroupOfMaxLength [: > 
[: DoBetweenElementsInFold&.:>/ PackElements , GroupOfEmptyGroupInitialState


lisEH=: LongestIncreasingSubsequence f.


NB.===


a=: 25 ? 25

timespacex 'lisI a'

timespacex 'lisJ a'

timespacex 'lisM a'

Re: [Jprogramming] Greatest Increasing Subsequence

[Erling Hellenäs]

OK, here is my solution to the problem of finding the longest strictly 
increasing subsequence. /Erling


NB. This is a solution to the problem of finding the longest strictly 
increasing subsequence.


NB. Draws numbers from the end of the sequence. Each number is placed in 
one or more groups.


NB. If the number is less than the first number in a group this group is 
duplicated and


NB. the new number placed first in one of the two groups.

NB. If the number is not less than the first number in any group a new 
group is


NB. created with only this number.

NB. Of the resulting groups which now starts with the new number only 
one of the


NB. groups is selected, one of the longest groups.

NB. All groups which do not start with the new number are kept.

NB. When all numbers are drawn the longest remaining group is selected.



LongestIncreasingSubsequence=: [: SelectFirstGroupOfMaxLength [: > [: 
([: DoBetweenElementsInFold&.> / PackElements , 
GroupOfEmptyGroupInitialState) ]


PackElements=: <@+

GroupOfEmptyGroupInitialState=: [: < a:"_

DoBetweenElementsInFold=: [ (( LeftIsNotFirstInGroup +. 
FirstGroupOfMaxLenghtInGroupsWithLeftFirstInGroup) # ] 
)AppendGroupsWithEmptyLeftOrGroupsWithLeftAppendedFirst


AppendGroupsWithEmptyLeftOrGroupsWithLeftAppendedFirst=: ] , [ 
AddGroupWIthLeftIfNoGroups [ PrependLeftInGroups 
SelectGroupsWithLeftLessThanFirstElement


SelectGroupsWithLeftLessThanFirstElement=:([: , [ < [: (1 {. ])@> ]) # ]

PrependLeftInGroups=: ( [: < [) ,&.> ]

AddGroupWIthLeftIfNoGroups=:(((0 = [: # ]) {. [: < [),])

FirstGroupOfMaxLenghtInGroupsWithLeftFirstInGroup=:[: 
FirstGroupOfMaxLength LengthOfGroups * LeftIsFirstInGroup


LeftIsFirstInGroup=: [: , [ = [: (1 {. ])@> ]

LengthOfGroups=:([: #@> ])

FirstGroupOfMaxLength=: [: ./ ]

LeftIsNotFirstInGroup=: [: , [ ~: [: ( 1 {. ])@> ]

SelectFirstGroupOfMaxLength=:([: FirstGroupOfMaxLength ([: #@> ]))#]


PackElements 6 1 3 4 2 8

GroupOfEmptyGroupInitialState ''

2 DoBetweenElementsInFold (<1 2 3),<4 5

2 AppendGroupsWithEmptyLeftOrGroupsWithLeftAppendedFirst (<1 2 3),<4 5

1 AppendGroupsWithEmptyLeftOrGroupsWithLeftAppendedFirst (<1 2 3),<4 5

8 AppendGroupsWithEmptyLeftOrGroupsWithLeftAppendedFirst (<1 2 3),<4 5

2 SelectGroupsWithLeftLessThanFirstElement (<1 2 3),<4 5

2 PrependLeftInGroups <4 5

2 AddGroupWIthLeftIfNoGroups 0 {. 
You've got a point there.  I think - may be wrong - that others have

looked for strict increasing sequences.

Mike


On 08/09/2016 12:54, Erling Hellenäs wrote:
Well, it found a longer subsequence. Guess I didn't understand the 
problem definition. I was not able to Google "greatest increasing 
subsequence". It is the "longest increasing subsquence" problem we 
are solving? /Erling



On 2016-09-08 13:41, 'Mike Day' via Programming wrote:

Thanks.  No problems with line-wrapping in youe mail here!

Naming your function lisEH,  and mine lis,  I find:

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

;lisEH l

1 2 4 4 4 4 5 7 11 19

lis l

1 2 3 4 5 7 11 19


So lisEH appears to miss the 3

Mike


On 08/09/2016 11:53, Erling Hellenäs wrote:

Hi all !

The problem seemed like too much fun so I made my own version. See 
below. You will have to fix rows cut by the mail system to run it.


It handles 1 numbers in some minutes on my computer.

All comments are welcome.

Cheers,

Erling

NB. Draws numbers from the end of the sequence. Each number is 
placed in one or more groups.


NB. If the number is less than or equal to the first number in a 
group this group is duplicated and


NB. the new number placed first in one of the two groups.

NB. If the number is not less than or equal to the first number in 
any group a new group is


NB. created with only this number.

NB. Of the resulting groups which now starts with the new number 
the longest group is selected.


NB. All groups which do not start with the new number are kept.

NB. When all numbers are drawn the longest remaining group is 
selected.




LargestIncreasingSubsequence=: [: SelectFirstGroupOfMaxLength [: > 
[: ([: DoBetweenElementsInFold&.> / PackElements , 
GroupOfEmptyGroupInitialState) ]


PackElements=: <@+

GroupOfEmptyGroupInitialState=: [: < a:"_

DoBetweenElementsInFold=: [ (( LeftIsNotFirstInGroup +. 
FirstGroupOfMaxLenghtInGroupsWithLeftFirstInGroup) # ] 
)AppendGroupsWithEmptyLeftOrGroupsWithLeftAppendedFirst


AppendGroupsWithEmptyLeftOrGroupsWithLeftAppendedFirst=: ] , [ 
AddGroupWIthLeftIfNoGroups [ PrependLeftInGroups 
SelectGroupsWithLeftLessOrEqualToFirstElement


SelectGroupsWithLeftLessOrEqualToFirstElement=:([: , [ <: [: (1 {. 
])@> ]) # ]


PrependLeftInGroups=: ( [: < [) ,&.> ]

AddGroupWIthLeftIfNoGroups=:(((0 = [: # ]) {. [: < [),])

FirstGroupOfMaxLenghtInGroupsWithLeftFirstInGroup=:[: 
FirstGroupOfMaxLength LengthOfGroups * LeftIsFirstInGroup


LeftIsFirstInGroup=: [: , [ = [: (1 {. ])@> ]

LengthOfGroups=:([: #@> ])

FirstGroupOfMaxLength=: [: ./ ]

LeftIsNotFirstInGroup=: [: , [ ~: [: ( 1 {. 

Re: [Jprogramming] Greatest Increasing Subsequence

['Mike Day' via Programming]

You've got a point there.  I think - may be wrong - that others have

looked for strict increasing sequences.

Mike


On 08/09/2016 12:54, Erling Hellenäs wrote:
Well, it found a longer subsequence. Guess I didn't understand the 
problem definition. I was not able to Google "greatest increasing 
subsequence". It is the "longest increasing subsquence" problem we are 
solving? /Erling



On 2016-09-08 13:41, 'Mike Day' via Programming wrote:

Thanks.  No problems with line-wrapping in youe mail here!

Naming your function lisEH,  and mine lis,  I find:

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

;lisEH l

1 2 4 4 4 4 5 7 11 19

lis l

1 2 3 4 5 7 11 19


So lisEH appears to miss the 3

Mike


On 08/09/2016 11:53, Erling Hellenäs wrote:

Hi all !

The problem seemed like too much fun so I made my own version. See 
below. You will have to fix rows cut by the mail system to run it.


It handles 1 numbers in some minutes on my computer.

All comments are welcome.

Cheers,

Erling

NB. Draws numbers from the end of the sequence. Each number is 
placed in one or more groups.


NB. If the number is less than or equal to the first number in a 
group this group is duplicated and


NB. the new number placed first in one of the two groups.

NB. If the number is not less than or equal to the first number in 
any group a new group is


NB. created with only this number.

NB. Of the resulting groups which now starts with the new number the 
longest group is selected.


NB. All groups which do not start with the new number are kept.

NB. When all numbers are drawn the longest remaining group is selected.



LargestIncreasingSubsequence=: [: SelectFirstGroupOfMaxLength [: > 
[: ([: DoBetweenElementsInFold&.> / PackElements , 
GroupOfEmptyGroupInitialState) ]


PackElements=: <@+

GroupOfEmptyGroupInitialState=: [: < a:"_

DoBetweenElementsInFold=: [ (( LeftIsNotFirstInGroup +. 
FirstGroupOfMaxLenghtInGroupsWithLeftFirstInGroup) # ] 
)AppendGroupsWithEmptyLeftOrGroupsWithLeftAppendedFirst


AppendGroupsWithEmptyLeftOrGroupsWithLeftAppendedFirst=: ] , [ 
AddGroupWIthLeftIfNoGroups [ PrependLeftInGroups 
SelectGroupsWithLeftLessOrEqualToFirstElement


SelectGroupsWithLeftLessOrEqualToFirstElement=:([: , [ <: [: (1 {. 
])@> ]) # ]


PrependLeftInGroups=: ( [: < [) ,&.> ]

AddGroupWIthLeftIfNoGroups=:(((0 = [: # ]) {. [: < [),])

FirstGroupOfMaxLenghtInGroupsWithLeftFirstInGroup=:[: 
FirstGroupOfMaxLength LengthOfGroups * LeftIsFirstInGroup


LeftIsFirstInGroup=: [: , [ = [: (1 {. ])@> ]

LengthOfGroups=:([: #@> ])

FirstGroupOfMaxLength=: [: ./ ]

LeftIsNotFirstInGroup=: [: , [ ~: [: ( 1 {. ])@> ]

SelectFirstGroupOfMaxLength=:([: FirstGroupOfMaxLength ([: #@> ]))#]


PackElements 6 1 3 4 2 8

GroupOfEmptyGroupInitialState ''

2 DoBetweenElementsInFold (<1 2 3),<4 5

2 AppendGroupsWithEmptyLeftOrGroupsWithLeftAppendedFirst (<1 2 3),<4 5

1 AppendGroupsWithEmptyLeftOrGroupsWithLeftAppendedFirst (<1 2 3),<4 5

8 AppendGroupsWithEmptyLeftOrGroupsWithLeftAppendedFirst (<1 2 3),<4 5

2 SelectGroupsWithLeftLessOrEqualToFirstElement (<1 2 3),<4 5

2 PrependLeftInGroups <4 5

2 AddGroupWIthLeftIfNoGroups 0 {. 2 FirstGroupOfMaxLenghtInGroupsWithLeftFirstInGroup (<2),(<2 4 5),<2 
6 7


2 LeftIsFirstInGroup (<1 2 3),<2 4 5

2 LengthOfGroups (<1 2 3),<2 4 5

FirstGroupOfMaxLength 3 3

2 LeftIsNotFirstInGroup (<1 2 3),<2 4 5

2 LeftIsNotFirstInGroup (<1 2 3),<2 4 5

SelectFirstGroupOfMaxLength (<2),(<2 4 5),<2 6 7

LargestIncreasingSubsequence=: LargestIncreasingSubsequence f.

LargestIncreasingSubsequence 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

LargestIncreasingSubsequence l

LargestIncreasingSubsequence 1000?1000





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



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

Re: [Jprogramming] Greatest Increasing Subsequence

[Erling Hellenäs]

Well, it found a longer subsequence. Guess I didn't understand the 
problem definition. I was not able to Google "greatest increasing 
subsequence". It is the "longest increasing subsquence" problem we are 
solving? /Erling



On 2016-09-08 13:41, 'Mike Day' via Programming wrote:

Thanks.  No problems with line-wrapping in youe mail here!

Naming your function lisEH,  and mine lis,  I find:

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

;lisEH l

1 2 4 4 4 4 5 7 11 19

lis l

1 2 3 4 5 7 11 19


So lisEH appears to miss the 3

Mike


On 08/09/2016 11:53, Erling Hellenäs wrote:

Hi all !

The problem seemed like too much fun so I made my own version. See 
below. You will have to fix rows cut by the mail system to run it.


It handles 1 numbers in some minutes on my computer.

All comments are welcome.

Cheers,

Erling

NB. Draws numbers from the end of the sequence. Each number is placed 
in one or more groups.


NB. If the number is less than or equal to the first number in a 
group this group is duplicated and


NB. the new number placed first in one of the two groups.

NB. If the number is not less than or equal to the first number in 
any group a new group is


NB. created with only this number.

NB. Of the resulting groups which now starts with the new number the 
longest group is selected.


NB. All groups which do not start with the new number are kept.

NB. When all numbers are drawn the longest remaining group is selected.



LargestIncreasingSubsequence=: [: SelectFirstGroupOfMaxLength [: > [: 
([: DoBetweenElementsInFold&.> / PackElements , 
GroupOfEmptyGroupInitialState) ]


PackElements=: <@+

GroupOfEmptyGroupInitialState=: [: < a:"_

DoBetweenElementsInFold=: [ (( LeftIsNotFirstInGroup +. 
FirstGroupOfMaxLenghtInGroupsWithLeftFirstInGroup) # ] 
)AppendGroupsWithEmptyLeftOrGroupsWithLeftAppendedFirst


AppendGroupsWithEmptyLeftOrGroupsWithLeftAppendedFirst=: ] , [ 
AddGroupWIthLeftIfNoGroups [ PrependLeftInGroups 
SelectGroupsWithLeftLessOrEqualToFirstElement


SelectGroupsWithLeftLessOrEqualToFirstElement=:([: , [ <: [: (1 {. 
])@> ]) # ]


PrependLeftInGroups=: ( [: < [) ,&.> ]

AddGroupWIthLeftIfNoGroups=:(((0 = [: # ]) {. [: < [),])

FirstGroupOfMaxLenghtInGroupsWithLeftFirstInGroup=:[: 
FirstGroupOfMaxLength LengthOfGroups * LeftIsFirstInGroup


LeftIsFirstInGroup=: [: , [ = [: (1 {. ])@> ]

LengthOfGroups=:([: #@> ])

FirstGroupOfMaxLength=: [: ./ ]

LeftIsNotFirstInGroup=: [: , [ ~: [: ( 1 {. ])@> ]

SelectFirstGroupOfMaxLength=:([: FirstGroupOfMaxLength ([: #@> ]))#]


PackElements 6 1 3 4 2 8

GroupOfEmptyGroupInitialState ''

2 DoBetweenElementsInFold (<1 2 3),<4 5

2 AppendGroupsWithEmptyLeftOrGroupsWithLeftAppendedFirst (<1 2 3),<4 5

1 AppendGroupsWithEmptyLeftOrGroupsWithLeftAppendedFirst (<1 2 3),<4 5

8 AppendGroupsWithEmptyLeftOrGroupsWithLeftAppendedFirst (<1 2 3),<4 5

2 SelectGroupsWithLeftLessOrEqualToFirstElement (<1 2 3),<4 5

2 PrependLeftInGroups <4 5

2 AddGroupWIthLeftIfNoGroups 0 {. 



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

Re: [Jprogramming] Greatest Increasing Subsequence

['Mike Day' via Programming]

Thanks.  No problems with line-wrapping in youe mail here!

Naming your function lisEH,  and mine lis,  I find:

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

;lisEH l

1 2 4 4 4 4 5 7 11 19

lis l

1 2 3 4 5 7 11 19


So lisEH appears to miss the 3

Mike


On 08/09/2016 11:53, Erling Hellenäs wrote:

Hi all !

The problem seemed like too much fun so I made my own version. See 
below. You will have to fix rows cut by the mail system to run it.


It handles 1 numbers in some minutes on my computer.

All comments are welcome.

Cheers,

Erling

NB. Draws numbers from the end of the sequence. Each number is placed 
in one or more groups.


NB. If the number is less than or equal to the first number in a group 
this group is duplicated and


NB. the new number placed first in one of the two groups.

NB. If the number is not less than or equal to the first number in any 
group a new group is


NB. created with only this number.

NB. Of the resulting groups which now starts with the new number the 
longest group is selected.


NB. All groups which do not start with the new number are kept.

NB. When all numbers are drawn the longest remaining group is selected.



LargestIncreasingSubsequence=: [: SelectFirstGroupOfMaxLength [: > [: 
([: DoBetweenElementsInFold&.> / PackElements , 
GroupOfEmptyGroupInitialState) ]


PackElements=: <@+

GroupOfEmptyGroupInitialState=: [: < a:"_

DoBetweenElementsInFold=: [ (( LeftIsNotFirstInGroup +. 
FirstGroupOfMaxLenghtInGroupsWithLeftFirstInGroup) # ] 
)AppendGroupsWithEmptyLeftOrGroupsWithLeftAppendedFirst


AppendGroupsWithEmptyLeftOrGroupsWithLeftAppendedFirst=: ] , [ 
AddGroupWIthLeftIfNoGroups [ PrependLeftInGroups 
SelectGroupsWithLeftLessOrEqualToFirstElement


SelectGroupsWithLeftLessOrEqualToFirstElement=:([: , [ <: [: (1 {. 
])@> ]) # ]


PrependLeftInGroups=: ( [: < [) ,&.> ]

AddGroupWIthLeftIfNoGroups=:(((0 = [: # ]) {. [: < [),])

FirstGroupOfMaxLenghtInGroupsWithLeftFirstInGroup=:[: 
FirstGroupOfMaxLength LengthOfGroups * LeftIsFirstInGroup


LeftIsFirstInGroup=: [: , [ = [: (1 {. ])@> ]

LengthOfGroups=:([: #@> ])

FirstGroupOfMaxLength=: [: ./ ]

LeftIsNotFirstInGroup=: [: , [ ~: [: ( 1 {. ])@> ]

SelectFirstGroupOfMaxLength=:([: FirstGroupOfMaxLength ([: #@> ]))#]


PackElements 6 1 3 4 2 8

GroupOfEmptyGroupInitialState ''

2 DoBetweenElementsInFold (<1 2 3),<4 5

2 AppendGroupsWithEmptyLeftOrGroupsWithLeftAppendedFirst (<1 2 3),<4 5

1 AppendGroupsWithEmptyLeftOrGroupsWithLeftAppendedFirst (<1 2 3),<4 5

8 AppendGroupsWithEmptyLeftOrGroupsWithLeftAppendedFirst (<1 2 3),<4 5

2 SelectGroupsWithLeftLessOrEqualToFirstElement (<1 2 3),<4 5

2 PrependLeftInGroups <4 5

2 AddGroupWIthLeftIfNoGroups 0 {. 



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

Re: [Jprogramming] Greatest Increasing Subsequence

[Henry Rich]

> i.@#)



NB.=== 




NB. Xiao's version with Raul's modifications. Renamed verbs to 
avoid clashing.


NB. dyads
  exr=:  (1 + {:@[ < ]) {. [ ; ,
  hxr=:  [: ; exr&.>

NB. monads
  gxr=: (}.@] ;~ {.@] ; (hxr {.))&>/
  cxr=: ({::~ [: (i. >./) #@>)@>@{.
  dxr=: (<_) ; ]
  lisXR=: ([: cxr gxr^:(#@(>@{:)))@dxr

NB.=== 



a=: 25 ? 25
timespacex 'lisI a'
timespacex 'lisJ a'
timespacex 'lisM a'
timespacex 'lisL a'
timespacex 'lisXR a' NB. comment out for larger arrays,a.

Playing around with various arrays, it seems lisM is the most 
efficient in time and space (more than the imperative version).
lisM and lisI can handle array larger than 1. The others 
struggle or give up with them.




On Sun, 9/4/16, 'Mike Day' via Programming 
<programm...@jsoftware.com> wrote:


Subject: Re: [Jprogramming] Greatest Increasing Subsequence
To: programm...@jsoftware.com
Date: Sunday, September 4, 2016, 4:30 AM

This version of
"lis" is a bit more J-like,  especially in using
dyadic I.
instead of the diy binary search,
at the expense of a slightly more
complicated set-up for the m and mx arrays.

lis =: 3 : 0
n   =. #x   =. y
if. 2>#x do. x return. end.
   NB. special case empty or singleton array
if. (-:/:~)x do. ~.x return. end. NB. special
case sorted arrays
if. (-:\:~)x do. {.x
return. end.
p   =. n#0
NB. seed m with trailing _1 so that final L (as
in wiki algorithm) can
be found
m   =. n 0 } _1#~>:n
NB. set up sorted mx, with just the first
element of x, so that I. works
mx  =.
({.x) 1 } (<:<./x), n#>:>./x
for_i. i.n do.
xi=.
i{x
lo=. mx I. xi
p =. (m{~<:lo) i } p
NB. better than appending to short p for
larger x
m
   =. i  lo } m
mx=.
xi lo } mx
end.
|.
x{~(p{~])^:(i.L) m{~ L =. <: m i. _1
)

Mike


On 02/09/2016 20:45, 'Mike
Day' via Programming wrote:

Well,

assuming for now that it does work,  here's an attempt
at a J

version of

the pseudo-code listed at
https://en.wikipedia.org/wiki/Longest_increasing_subsequence#Efficient_algorithms 



lis =: 3 : 0   NB. longest

increasing subsequence

m

   =. 0#~>:n   =.
#x   =. y

L

   =. #p   =. ''

mx  =. m{x NB. added this vector

for better look-up of x{~mid{m

for_i.

i.n do.

   'lo hi' =.

1, L

xi =. i{x
while. lo <: hi do.
   mid=. >.@-: lo + hi

NB.   if. xi > x{~ mid{m do. NB. next
line a bit better
   if. xi > mid{mx do.
lo =. >: mid
   else.

  hi =.

<: mid

   end.
end.
p

   =. p, m{~<:lo

m

   =. i  lo } m

mx

  =. xi lo } mxNB. update my additional array

L =. L >. lo
NB. smoutput i; (x{.~ >:i);

L{.m   NB. diagnostic
end.

|. x{~(p{~])^:(i.L) L{m
)

It's reasonably fast on ?1#5000 -

but possibly wrong!It does

fail on an

empty array.
Mike



On 02/09/2016 17:30, Raul Miller wrote:
It seems to me that the

"efficient algorithm" documented on the

wikipedia page would have an analogous

flaw. It is performing binary
searches on unsorted lists. That said, it does perform
correctly for

this example.

Thanks,


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


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

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

Re: [Jprogramming] Greatest Increasing Subsequence

[bill lam]

It depends on whether the sequence will converge.
try
  (1 2 3 4 5 6){~^:(5&>)^:(0) 1
  (1 2 3 4 5 6){~^:(5&>)^:(1) 1
  (1 2 3 4 5 6){~^:(5&>)^:(2) 1
  (1 2 3 4 5 6){~^:(5&>)^:(3) 1
etc.

Ср, 07 сен 2016, jprogramming написал(а):
> This also runs out of memory:
> 
>(1 2 3 4 5 6){~^:(5&>)^:(_) 1
> |out of memory
> |   (1 2 3 4 5 6){~^:(5&>)^:(_)1
> 
> whereas this doesn't
> {&(1 2 3 4 5 6)^:(5&>)^:(_)1
> 
> 
> Wouldn't this imply the bug (if there is a bug) is not in the boxed integer?
> 
> System details:
> 
> Engine: j804/j64/windows
> Release: commercial/2015-12-21 16:18:48
> Library: 8.04.15
> Qt IDE: 1.4.10/5.4.2
> Platform: Win 64
> Installer: J804 install
> 
> 
> ------------
> On Wed, 9/7/16, 'Jon Hough' via Programming <programm...@jsoftware.com> wrote:
> 
>  Subject: Re: [Jprogramming] Greatest Increasing Subsequence
>  To: programm...@jsoftware.com
>  Date: Wednesday, September 7, 2016, 6:30 PM
>  
>  " It appears that   interpreted 
>   as <_ regardless of n."
>  
>  I'm not sure this is the case, for any left hand verb.
>  ]^:(<4) 4
>  works fine.
>  
>  
>  
>  On Wed, 9/7/16, Henry Rich <henryhr...@gmail.com>
>  wrote:
>  
>   Subject: Re: [Jprogramming] Greatest Increasing
>  Subsequence
>   To: programm...@jsoftware.com
>   Date: Wednesday, September 7, 2016, 6:05 PM
>   
>   I noticed this the other
>   day.  It appears thatas <_ regardless of n.  I'll look into
>   it.
>   
>   Henry Rich
>   
>   On 9/6/2016 11:53 PM,
>   Xiao-Yong Jin wrote:
>   > I’m trying to
>   rewrite lisM in a readable tacit form but hit something I
>   didn’t understand.
>   > Supplying i.n to
>   ^: works fine, butsays.  Namely
>   >
>   > 
>     (_1+i.5){~^:(i.4)4
>   >
>   > produces 4 3 2 1, but
>   >
>   >   
>   (_1+i.5){~^:(<4)4
>   >
>   > exhausts all the memory with J804 and
>   J805beta.
>   >
>   > The
>   dictionary says
>   >
>   > 
>     If n is boxed it must be an atom, and u^:(<m)
>   >     ↔ u^:(i.m) y     
>       if m is a non-negative integer
>   >
>   > so the above two
>   should be the same.  What’s going on here?
>   >
>   >> On Sep 5, 2016,
>   at 3:17 AM, 'Mike Day' via Programming <programm...@jsoftware.com>
>   wrote:
>   >>
>   >>
>   Thanks Jon
>   >>
>   >>
>   lisM isn't really "my" version - I was just
>   translating the pseudo-code...
>   >> I
>   expect -without checking! - that its advantage over lisl
>   resides in avoiding the do-it-yourself binary search by
>   using J's built-in dyadic I. , albeit at the expense of
>   an explicit sorted array, which I called mx .   I
>   tried limiting the I. search to only the first L items of
>   mx,  but with no benefit,  at least for the sizes I
>   tried.
>   >> The time taken to recover
>   the result is fairly trivial,  so I don't suppose my
>   use of
>   >> |. x{~(p{~])^:(i.L) L{m
>   >> is particularly interesting,  but it
>   avoided that explicit while loop.
>   >>
>   >> Mike
>   >>
>   >> Please reply
>   to mike_liz@tiscali.co.uk.
>   >> Sent from my iPad
>   >>
>   >>> On 5 Sep
>   2016, at 08:07, 'Jon Hough' via Programming <programm...@jsoftware.com>
>   wrote:
>   >>>
>   >>> Just out of interest, I compared
>   the various results.
>   >>> I wrote a
>   fully imperative version, which uses in-place modification
>   of the results array.
>   >>>
>   >>> I also wrote a version that avoids
>   any while / for loops (because I wanted to avoid using
>   them), and ended up putting
>   >>>
>   most of the logic in anonymous verbs. Which is probably a
>   big mistake because that gets very slow. Also barely
>   readable.
>   >>>
>   >>>
>   
> NB.===
>   >>>
>   >>> NB.
>   Jon - bizarre version. Uses anonymous verbs for most of
>  the
>   logic.
>   >>> NB. Slow and, uses huge
>   amounts of memory.
>   >>>
>   appendOrInsert=:(3 : 'insert max' [ 3 :
>   '(max=:<:#lst)[(min=:0)[val=:i{r[i=:y')`(3 :
>   '(lst=:lst,y)[prev=:(_1{lst) y} prev')@.(3 :
>   '(val>({:lst){

Re: [Jprogramming] Greatest Increasing Subsequence

['Jon Hough' via Programming]

This also runs out of memory:

   (1 2 3 4 5 6){~^:(5&>)^:(_) 1
|out of memory
|   (1 2 3 4 5 6){~^:(5&>)^:(_)1

whereas this doesn't
{&(1 2 3 4 5 6)^:(5&>)^:(_)1


Wouldn't this imply the bug (if there is a bug) is not in the boxed integer?

System details:

Engine: j804/j64/windows
Release: commercial/2015-12-21 16:18:48
Library: 8.04.15
Qt IDE: 1.4.10/5.4.2
Platform: Win 64
Installer: J804 install



On Wed, 9/7/16, 'Jon Hough' via Programming <programm...@jsoftware.com> wrote:

 Subject: Re: [Jprogramming] Greatest Increasing Subsequence
 To: programm...@jsoftware.com
 Date: Wednesday, September 7, 2016, 6:30 PM
 
 " It appears that 
 wrote:
 
  Subject: Re: [Jprogramming] Greatest Increasing
 Subsequence
  To: programm...@jsoftware.com
  Date: Wednesday, September 7, 2016, 6:05 PM
  
  I noticed this the other
  day.  It appears that  I’m trying to
  rewrite lisM in a readable tacit form but hit something I
  didn’t understand.
  > Supplying i.n to
  ^: works fine, but 
  > 
    (_1+i.5){~^:(i.4)4
  >
  > produces 4 3 2 1, but
  >
  >   
  (_1+i.5){~^:(<4)4
  >
  > exhausts all the memory with J804 and
  J805beta.
  >
  > The
  dictionary says
  >
  > 
    If n is boxed it must be an atom, and u^:(<m)
  >     ↔ u^:(i.m) y     
      if m is a non-negative integer
  >
  > so the above two
  should be the same.  What’s going on here?
  >
  >> On Sep 5, 2016,
  at 3:17 AM, 'Mike Day' via Programming <programm...@jsoftware.com>
  wrote:
  >>
  >>
  Thanks Jon
  >>
  >>
  lisM isn't really "my" version - I was just
  translating the pseudo-code...
  >> I
  expect -without checking! - that its advantage over lisl
  resides in avoiding the do-it-yourself binary search by
  using J's built-in dyadic I. , albeit at the expense of
  an explicit sorted array, which I called mx .   I
  tried limiting the I. search to only the first L items of
  mx,  but with no benefit,  at least for the sizes I
  tried.
  >> The time taken to recover
  the result is fairly trivial,  so I don't suppose my
  use of
  >> |. x{~(p{~])^:(i.L) L{m
  >> is particularly interesting,  but it
  avoided that explicit while loop.
  >>
  >> Mike
  >>
  >> Please reply
  to mike_liz@tiscali.co.uk.
  >> Sent from my iPad
  >>
  >>> On 5 Sep
  2016, at 08:07, 'Jon Hough' via Programming <programm...@jsoftware.com>
  wrote:
  >>>
  >>> Just out of interest, I compared
  the various results.
  >>> I wrote a
  fully imperative version, which uses in-place modification
  of the results array.
  >>>
  >>> I also wrote a version that avoids
  any while / for loops (because I wanted to avoid using
  them), and ended up putting
  >>>
  most of the logic in anonymous verbs. Which is probably a
  big mistake because that gets very slow. Also barely
  readable.
  >>>
  >>>
  NB.===
  >>>
  >>> NB.
  Jon - bizarre version. Uses anonymous verbs for most of
 the
  logic.
  >>> NB. Slow and, uses huge
  amounts of memory.
  >>>
  appendOrInsert=:(3 : 'insert max' [ 3 :
  '(max=:<:#lst)[(min=:0)[val=:i{r[i=:y')`(3 :
  '(lst=:lst,y)[prev=:(_1{lst) y} prev')@.(3 :
  '(val>({:lst){r)[val=:y{r')
  >>> insert=:(3 : '(prev=:
  ((y-1){lst)i}prev)[(lst=: i y }lst)' ] ])@:(3 :
  'mid'`(3 : 'min=: mid+1')@.(3 :
  '(val>(mid{lst){r)[(mid=:<.(min+y)%2)')^:(0&<)^:_)
  >>>
  >>> lisJ
  =: 3 : 0
  >>> r=:y           
    NB. array
  >>>
  [val=:0[max=:0[mid=:0[min=:0  NB. useful numbers
  >>> lst=:0            NB. list
  of indices
  >>> prev=: (#y)#0   
      NB. previous indices
  >>>
  i=:0            NB. current index
  >>>
  >>>
  appendOrInsert"0 >: i.<: # y    NB. append the
  items, or insert them, into lst (and update prev)
  >>> res=:''
  >>> ptr=: _1{lst
  >>> (ptr)^:(#lst) res
  >>> |. res
  >>> )
  >>>
  >>> buildEx =: 4 : 0
  >>> res=:y,ptr{r
  >>> ptr=: ptr{prev
  >>> res
  >>>
  )
  >>>
  >>>
  >>>
  NB.===
  >>>
  >>>
  >>> NB. Imperative version. just for
  benchmarking
  >>> lisI =: 3 : 0
  >>> lst =: 0
  >>> r=: y
  >>>
  parent=: (#y)#0
  >>>
  for_i.>:i.<:# r do.
  >>>
  if.((i{r) > ({: lst){r )  do.
  >>> parent=:(_1{lst) i}parent
  >>> lst =: lst, i
  >>> else.
  >>&g

Re: [Jprogramming] Greatest Increasing Subsequence

['Jon Hough' via Programming]

" It appears that  wrote:

 Subject: Re: [Jprogramming] Greatest Increasing Subsequence
 To: programm...@jsoftware.com
 Date: Wednesday, September 7, 2016, 6:05 PM
 
 I noticed this the other
 day.  It appears that  I’m trying to
 rewrite lisM in a readable tacit form but hit something I
 didn’t understand.
 > Supplying i.n to
 ^: works fine, but 
 > 
   (_1+i.5){~^:(i.4)4
 >
 > produces 4 3 2 1, but
 >
 >   
 (_1+i.5){~^:(<4)4
 >
 > exhausts all the memory with J804 and
 J805beta.
 >
 > The
 dictionary says
 >
 > 
   If n is boxed it must be an atom, and u^:(<m)
 >     ↔ u^:(i.m) y     
     if m is a non-negative integer
 >
 > so the above two
 should be the same.  What’s going on here?
 >
 >> On Sep 5, 2016,
 at 3:17 AM, 'Mike Day' via Programming <programm...@jsoftware.com>
 wrote:
 >>
 >>
 Thanks Jon
 >>
 >>
 lisM isn't really "my" version - I was just
 translating the pseudo-code...
 >> I
 expect -without checking! - that its advantage over lisl
 resides in avoiding the do-it-yourself binary search by
 using J's built-in dyadic I. , albeit at the expense of
 an explicit sorted array, which I called mx .   I
 tried limiting the I. search to only the first L items of
 mx,  but with no benefit,  at least for the sizes I
 tried.
 >> The time taken to recover
 the result is fairly trivial,  so I don't suppose my
 use of
 >> |. x{~(p{~])^:(i.L) L{m
 >> is particularly interesting,  but it
 avoided that explicit while loop.
 >>
 >> Mike
 >>
 >> Please reply
 to mike_liz@tiscali.co.uk.
 >> Sent from my iPad
 >>
 >>> On 5 Sep
 2016, at 08:07, 'Jon Hough' via Programming <programm...@jsoftware.com>
 wrote:
 >>>
 >>> Just out of interest, I compared
 the various results.
 >>> I wrote a
 fully imperative version, which uses in-place modification
 of the results array.
 >>>
 >>> I also wrote a version that avoids
 any while / for loops (because I wanted to avoid using
 them), and ended up putting
 >>>
 most of the logic in anonymous verbs. Which is probably a
 big mistake because that gets very slow. Also barely
 readable.
 >>>
 >>>
 NB.===
 >>>
 >>> NB.
 Jon - bizarre version. Uses anonymous verbs for most of the
 logic.
 >>> NB. Slow and, uses huge
 amounts of memory.
 >>>
 appendOrInsert=:(3 : 'insert max' [ 3 :
 '(max=:<:#lst)[(min=:0)[val=:i{r[i=:y')`(3 :
 '(lst=:lst,y)[prev=:(_1{lst) y} prev')@.(3 :
 '(val>({:lst){r)[val=:y{r')
 >>> insert=:(3 : '(prev=:
 ((y-1){lst)i}prev)[(lst=: i y }lst)' ] ])@:(3 :
 'mid'`(3 : 'min=: mid+1')@.(3 :
 '(val>(mid{lst){r)[(mid=:<.(min+y)%2)')^:(0&<)^:_)
 >>>
 >>> lisJ
 =: 3 : 0
 >>> r=:y           
   NB. array
 >>>
 [val=:0[max=:0[mid=:0[min=:0  NB. useful numbers
 >>> lst=:0            NB. list
 of indices
 >>> prev=: (#y)#0   
     NB. previous indices
 >>>
 i=:0            NB. current index
 >>>
 >>>
 appendOrInsert"0 >: i.<: # y    NB. append the
 items, or insert them, into lst (and update prev)
 >>> res=:''
 >>> ptr=: _1{lst
 >>> (ptr)^:(#lst) res
 >>> |. res
 >>> )
 >>>
 >>> buildEx =: 4 : 0
 >>> res=:y,ptr{r
 >>> ptr=: ptr{prev
 >>> res
 >>>
 )
 >>>
 >>>
 >>>
 NB.===
 >>>
 >>>
 >>> NB. Imperative version. just for
 benchmarking
 >>> lisI =: 3 : 0
 >>> lst =: 0
 >>> r=: y
 >>>
 parent=: (#y)#0
 >>>
 for_i.>:i.<:# r do.
 >>>
 if.((i{r) > ({: lst){r )  do.
 >>> parent=:(_1{lst) i}parent
 >>> lst =: lst, i
 >>> else.
 >>>
 min=: 0
 >>> max =: <:#lst
 >>> while. min < max do.
 >>> mid =: <. (min + max) % 2
 >>> if. (i{r) > ((mid { lst{r)) do.
 min =: mid + 1
 >>> else. max =: mid
 end.
 >>> end.
 >>> lst=: (i) max} lst
 >>> parent=: ((max-1){lst)(i})
 parent
 >>> end.
 >>> end.
 >>>
 res=: ''
 >>> ptr=:
 _1{lst
 >>> while. (# res) < #
 lst do.
 >>> res=:res,ptr{r
 >>> ptr=:ptr{parent
 >>> end.
 >>>
 I. res
 >>> )
 >>>
 >>>
 >>>
 >>>
 NB.===
 >>>
 >>>
 >>> NB. Mike's version.
 >>>
 >>> lisM
 =: 3 : 0
 >>> n

Re: [Jprogramming] Greatest Increasing Subsequence

[Henry Rich]

) 1 } (<:<./x), n#>:>./x
for_i. i.n do.
  xi=. i{x
  lo=. mx I. xi
  p =. (m{~<:lo) i } p NB. better than appending to short p for 
larger x

  m =. i  lo } m
  mx=. xi lo } mx
end.
|. x{~(p{~])^:(i.L) m{~ L =. <: m i. _1
)

NB.=== 



NB. Louis' version.
p=: ] , [ ,&.> ] #~ (< {.&>) (= >./)@:* #&>@]
e=: }:@>@(#~ (= >./)@:(#&>))@>

s=: [: e (<<_) p&.>/@,~ <"0
pi=: ] , [ ,&.> ] {~ (< {.&>) (i. >./)@:* #&>@]
lisL =: [: e (<<_) pi&.>/@,~ 
<"0  NB. <- this one.


f=: ((] >: (-~ >./)) #&>) # ]

P=: ] , [ ,&.> ] #~ (< {.&>) (,@[ #^:_1 (= >./)@#) #&>@]
sp=: [: e (<<_) ({:@[ f {.@[ P ])&.>/@,~ (,&.> i.@#)



NB.=== 




NB. Xiao's version with Raul's modifications. Renamed verbs to 
avoid clashing.


NB. dyads
  exr=:  (1 + {:@[ < ]) {. [ ; ,
  hxr=:  [: ; exr&.>

NB. monads
  gxr=: (}.@] ;~ {.@] ; (hxr {.))&>/
  cxr=: ({::~ [: (i. >./) #@>)@>@{.
  dxr=: (<_) ; ]
  lisXR=: ([: cxr gxr^:(#@(>@{:)))@dxr

NB.=== 



a=: 25 ? 25
timespacex 'lisI a'
timespacex 'lisJ a'
timespacex 'lisM a'
timespacex 'lisL a'
timespacex 'lisXR a' NB. comment out for larger arrays,a.

Playing around with various arrays, it seems lisM is the most 
efficient in time and space (more than the imperative version).
lisM and lisI can handle array larger than 1. The others 
struggle or give up with them.




On Sun, 9/4/16, 'Mike Day' via Programming 
<programm...@jsoftware.com> wrote:


Subject: Re: [Jprogramming] Greatest Increasing Subsequence
To: programm...@jsoftware.com
Date: Sunday, September 4, 2016, 4:30 AM

This version of
"lis" is a bit more J-like,  especially in using
dyadic I.
instead of the diy binary search,
at the expense of a slightly more
complicated set-up for the m and mx arrays.

lis =: 3 : 0
n   =. #x   =. y
if. 2>#x do. x return. end.
   NB. special case empty or singleton array
if. (-:/:~)x do. ~.x return. end. NB. special
case sorted arrays
if. (-:\:~)x do. {.x
return. end.
p   =. n#0
NB. seed m with trailing _1 so that final L (as
in wiki algorithm) can
be found
m   =. n 0 } _1#~>:n
NB. set up sorted mx, with just the first
element of x, so that I. works
mx  =.
({.x) 1 } (<:<./x), n#>:>./x
for_i. i.n do.
xi=.
i{x
lo=. mx I. xi
p =. (m{~<:lo) i } p
NB. better than appending to short p for
larger x
m
   =. i  lo } m
mx=.
xi lo } mx
end.
|.
x{~(p{~])^:(i.L) m{~ L =. <: m i. _1
)

Mike


On 02/09/2016 20:45, 'Mike
Day' via Programming wrote:

Well,

assuming for now that it does work,  here's an attempt
at a J

version of

the pseudo-code listed at
https://en.wikipedia.org/wiki/Longest_increasing_subsequence#Efficient_algorithms 



lis =: 3 : 0   NB. longest

increasing subsequence

m

   =. 0#~>:n   =.
#x   =. y

L

   =. #p   =. ''

mx  =. m{x NB. added this vector

for better look-up of x{~mid{m

for_i.

i.n do.

   'lo hi' =.

1, L

xi =. i{x
while. lo <: hi do.
   mid=. >.@-: lo + hi

NB.   if. xi > x{~ mid{m do. NB. next
line a bit better
   if. xi > mid{mx do.
lo =. >: mid
   else.

  hi =.

<: mid

   end.
end.
p

   =. p, m{~<:lo

m

   =. i  lo } m

mx

  =. xi lo } mxNB. update my additional array

L =. L >. lo
NB. smoutput i; (x{.~ >:i);

L{.m   NB. diagnostic
end.

|. x{~(p{~])^:(i.L) L{m
)

It's reasonably fast on ?1#5000 -

but possibly wrong!It does

fail on an

empty array.
Mike



On 02/09/2016 17:30, Raul Miller wrote:
It seems to me that the

"efficient algorithm" documented on the

wikipedia page would have an analogous

flaw. It is performing binary
searches on unsorted lists. That said, it does perform
correctly for

this example.

Thanks,


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


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

-

Re: [Jprogramming] Greatest Increasing Subsequence

['Mike Day' via Programming]

@,~ <"0  NB. 
<- this one.

f=: ((] >: (-~ >./)) #&>) # ]

P=: ] , [ ,&.> ] #~ (< {.&>) (,@[ #^:_1 (= >./)@#) #&>@]
sp=: [: e (<<_) ({:@[ f {.@[ P ])&.>/@,~ (,&.> i.@#)



NB.===


NB. Xiao's version with Raul's modifications. Renamed verbs to avoid clashing.

NB. dyads
  exr=:  (1 + {:@[ < ]) {. [ ; ,
  hxr=:  [: ; exr&.>

NB. monads
  gxr=: (}.@] ;~ {.@] ; (hxr {.))&>/
  cxr=: ({::~ [: (i. >./) #@>)@>@{.
  dxr=: (<_) ; ]
  lisXR=: ([: cxr gxr^:(#@(>@{:)))@dxr

NB.===

a=: 25 ? 25
timespacex 'lisI a'
timespacex 'lisJ a'
timespacex 'lisM a'
timespacex 'lisL a'
timespacex 'lisXR a' NB. comment out for larger arrays,a.

Playing around with various arrays, it seems lisM is the most efficient in time 
and space (more than the imperative version).
lisM and lisI can handle array larger than 1. The others struggle or give 
up with them.



On Sun, 9/4/16, 'Mike Day' via Programming <programm...@jsoftware.com> wrote:

Subject: Re: [Jprogramming] Greatest Increasing Subsequence
To: programm...@jsoftware.com
Date: Sunday, September 4, 2016, 4:30 AM

This version of
"lis" is a bit more J-like,  especially in using
dyadic I.
instead of the diy binary search,
at the expense of a slightly more
complicated set-up for the m and mx arrays.

lis =: 3 : 0
n   =. #x   =. y
if. 2>#x do. x return. end.
   NB. special case empty or singleton array
if. (-:/:~)x do. ~.x return. end. NB. special
case sorted arrays
if. (-:\:~)x do. {.x
return. end.
p   =. n#0
NB. seed m with trailing _1 so that final L (as
in wiki algorithm) can
be found
m   =. n 0 } _1#~>:n
NB. set up sorted mx, with just the first
element of x, so that I. works
mx  =.
({.x) 1 } (<:<./x), n#>:>./x
for_i. i.n do.
xi=.
i{x
lo=. mx I. xi
p =. (m{~<:lo) i } p
NB. better than appending to short p for
larger x
m
   =. i  lo } m
mx=.
xi lo } mx
end.
|.
x{~(p{~])^:(i.L) m{~ L =. <: m i. _1
)

Mike


On 02/09/2016 20:45, 'Mike
Day' via Programming wrote:

Well,

assuming for now that it does work,  here's an attempt
at a J

version of

the pseudo-code listed at

https://en.wikipedia.org/wiki/Longest_increasing_subsequence#Efficient_algorithms

lis =: 3 : 0   NB. longest

increasing subsequence

m

   =. 0#~>:n   =.
#x   =. y

L

   =. #p   =. ''

mx  =. m{x NB. added this vector

for better look-up of x{~mid{m

for_i.

i.n do.

   'lo hi' =.

1, L

xi =. i{x
while. lo <: hi do.
   mid=. >.@-: lo + hi

NB.   if. xi > x{~ mid{m do. NB. next
line a bit better
   if. xi > mid{mx do.
lo =. >: mid
   else.

  hi =.

<: mid

   end.
end.
p

   =. p, m{~<:lo

m

   =. i  lo } m

mx

  =. xi lo } mxNB. update my additional array

L =. L >. lo
NB. smoutput i; (x{.~ >:i);

L{.m   NB. diagnostic
end.

|. x{~(p{~])^:(i.L) L{m
)

It's reasonably fast on ?1#5000 -

but possibly wrong!It does

fail on an

empty array.
Mike



On 02/09/2016 17:30, Raul Miller wrote:
It seems to me that the

"efficient algorithm" documented on the

wikipedia page would have an analogous

flaw. It is performing binary
searches on unsorted lists. That said, it does perform
correctly for

this example.

Thanks,


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


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

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

Re: [Jprogramming] Greatest Increasing Subsequence

[Henry Rich]

=

a=: 25 ? 25
timespacex 'lisI a'
timespacex 'lisJ a'
timespacex 'lisM a'
timespacex 'lisL a'
timespacex 'lisXR a' NB. comment out for larger arrays,a.

Playing around with various arrays, it seems lisM is the most efficient in time 
and space (more than the imperative version).
lisM and lisI can handle array larger than 1. The others struggle or give 
up with them.



On Sun, 9/4/16, 'Mike Day' via Programming <programm...@jsoftware.com> wrote:

Subject: Re: [Jprogramming] Greatest Increasing Subsequence
To: programm...@jsoftware.com
Date: Sunday, September 4, 2016, 4:30 AM

This version of
"lis" is a bit more J-like,  especially in using
dyadic I.
instead of the diy binary search,
at the expense of a slightly more
complicated set-up for the m and mx arrays.

lis =: 3 : 0
n   =. #x   =. y
if. 2>#x do. x return. end.
   NB. special case empty or singleton array
if. (-:/:~)x do. ~.x return. end. NB. special
case sorted arrays
if. (-:\:~)x do. {.x
return. end.
p   =. n#0
NB. seed m with trailing _1 so that final L (as
in wiki algorithm) can
be found
m   =. n 0 } _1#~>:n
NB. set up sorted mx, with just the first
element of x, so that I. works
mx  =.
({.x) 1 } (<:<./x), n#>:>./x
for_i. i.n do.
xi=.
i{x
lo=. mx I. xi
p =. (m{~<:lo) i } p
NB. better than appending to short p for
larger x
m
   =. i  lo } m
mx=.
xi lo } mx
end.
|.
x{~(p{~])^:(i.L) m{~ L =. <: m i. _1
)

Mike


On 02/09/2016 20:45, 'Mike
Day' via Programming wrote:

Well,

assuming for now that it does work,  here's an attempt
at a J

version of

the pseudo-code listed at

https://en.wikipedia.org/wiki/Longest_increasing_subsequence#Efficient_algorithms

lis =: 3 : 0   NB. longest

increasing subsequence

m

   =. 0#~>:n   =.
#x   =. y

L

   =. #p   =. ''

mx  =. m{x NB. added this vector

for better look-up of x{~mid{m

for_i.

i.n do.

   'lo hi' =.

1, L

xi =. i{x
while. lo <: hi do.
   mid=. >.@-: lo + hi

NB.   if. xi > x{~ mid{m do. NB. next
line a bit better
   if. xi > mid{mx do.
lo =. >: mid
   else.

  hi =.

<: mid

   end.
end.
p

   =. p, m{~<:lo

m

   =. i  lo } m

mx

  =. xi lo } mxNB. update my additional array

L =. L >. lo
NB. smoutput i; (x{.~ >:i);

L{.m   NB. diagnostic
end.

|. x{~(p{~])^:(i.L) L{m
)

It's reasonably fast on ?1#5000 -

but possibly wrong!It does

fail on an

empty array.
Mike



On 02/09/2016 17:30, Raul Miller wrote:
It seems to me that the

"efficient algorithm" documented on the

wikipedia page would have an analogous

flaw. It is performing binary
searches on unsorted lists. That said, it does perform
correctly for

this example.

Thanks,


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


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

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


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

Re: [Jprogramming] Greatest Increasing Subsequence

[Erling Hellenäs]

I have the same problem in J8.0.4, Win 64, Library 8.04.15 on Windows 
10. /Erling



On 2016-09-07 07:32, 'Jon Hough' via Programming wrote:

This also works
  (_1+i.5)&{~^:(<4)
so you could have used the & conjunction. I'm not sure what you version was 
actually doing, or how it got stuck in a loop.



On Wed, 9/7/16, 'Jon Hough' via Programming <programm...@jsoftware.com> wrote:

  Subject: Re: [Jprogramming] Greatest Increasing Subsequence
  To: programm...@jsoftware.com
  Date: Wednesday, September 7, 2016, 2:26 PM
  
  Someone more knowledgeable than I can

  probably give a reason why this works, whereas yours
  didn't:
  {&(_1+i.5)^:(<4) 4
  
  4 3 2 1
  
  
  

  On Wed, 9/7/16, Xiao-Yong Jin <jinxiaoy...@gmail.com>
  wrote:
  
   Subject: Re: [Jprogramming] Greatest Increasing

  Subsequence
   To: programm...@jsoftware.com
   Date: Wednesday, September 7, 2016, 12:53 PM
   
   I’m trying to rewrite

   lisM in a readable tacit form but hit something I didn’t
   understand.
   Supplying i.n to ^: works fine,
   but

   (_1+i.5){~^:(i.4)4
   
   produces

   4 3 2 1, but
   

   (_1+i.5){~^:(<4)4
   
   exhausts all the memory with J804 and

   J805beta.
   
   The dictionary

   says
   
 If n is boxed it

   must be an atom, and u^:(<m)
  ↔ u^:(i.m) y  if
   m is a non-negative integer
   
   so the above two should be the same.  What’s

   going on here?
   
   > On Sep

   5, 2016, at 3:17 AM, 'Mike Day' via Programming
   <programm...@jsoftware.com>
   wrote:
   >
   > Thanks
   Jon
   >
   > lisM
   isn't really "my" version - I was just
   translating the pseudo-code...
   > I expect
   -without checking! - that its advantage over lisl resides
  in
   avoiding the do-it-yourself binary search by using J's
   built-in dyadic I. , albeit at the expense of an explicit
   sorted array, which I called mx .   I tried
   limiting the I. search to only the first L items of mx,
   but with no benefit,  at least for the sizes I tried.
   > The time taken to recover the result is
   fairly trivial,  so I don't suppose my use of
   > |. x{~(p{~])^:(i.L) L{m
   > is particularly interesting,  but it
   avoided that explicit while loop.
   >
   > Mike
   >
   > Please reply to mike_liz@tiscali.co.uk.
   
   > Sent from my iPad

   >
   >> On 5 Sep 2016,
   at 08:07, 'Jon Hough' via Programming <programm...@jsoftware.com>
   wrote:
   >>
   >>
   Just out of interest, I compared the various results.
   >> I wrote a fully imperative version,
   which uses in-place modification of the results array.
   >>
   >> I also wrote
   a version that avoids any while / for loops (because I
   wanted to avoid using them), and ended up putting
   >> most of the logic in anonymous verbs.
   Which is probably a big mistake because that gets very
  slow.
   Also barely readable.
   >>
   >>
   
NB.===
   >>
   >> NB. Jon -
   bizarre version. Uses anonymous verbs for most of the
  logic.
   
   >> NB. Slow and, uses huge amounts of

   memory.
   >> appendOrInsert=:(3 :
   'insert max' [ 3 :
   '(max=:<:#lst)[(min=:0)[val=:i{r[i=:y')`(3 :
   '(lst=:lst,y)[prev=:(_1{lst) y} prev')@.(3 :
   '(val>({:lst){r)[val=:y{r')
   >> insert=:(3 : '(prev=:
   ((y-1){lst)i}prev)[(lst=: i y }lst)' ] ])@:(3 :
   'mid'`(3 : 'min=: mid+1')@.(3 :
   '(val>(mid{lst){r)[(mid=:<.(min+y)%2)')^:(0&<)^:_)
   >>
   >> lisJ =: 3 :
   0
   >> r=:y  NB.
   array
   >>
   [val=:0[max=:0[mid=:0[min=:0  NB. useful numbers
   >> lst=:0NB. list of
   indices
   >> prev=: (#y)#0
   NB. previous indices
   >> i=:0
 NB. current index
   >>
   >> appendOrInsert"0 >: i.<: #
   yNB. append the items, or insert them, into lst (and
   update prev)
   >> res=:''
   >> ptr=: _1{lst
   >>
   (ptr)^:(#lst) res
   >> |.
   res
   >> )
   >>
   >> buildEx =: 4 : 0
   >> res=:y,ptr{r
   >>
   ptr=: ptr{prev
   >> res
   >> )
   >>
   >>
   >>
   
NB.===
   >>
   >>
   >> NB. Imperative version. just for
   benchmarking
   >> lisI =: 3 : 0
   >> lst =: 0
   >> r=:
   y
   >> parent=: (#y)#0
   >> for_i.>:i.<:# r do.
   >> if.((i{r) > ({: lst){r )  do.
   >> parent=:(_1{lst) i}parent
   >> lst =: lst, i
   >>
   else.
   >> min=: 0
   >> max =: <:#lst
   >> while. min < max do.
   >> mid =: <. (min + max) % 2
  

Re: [Jprogramming] Greatest Increasing Subsequence

['Jon Hough' via Programming]

This also works
 (_1+i.5)&{~^:(<4)
so you could have used the & conjunction. I'm not sure what you version was 
actually doing, or how it got stuck in a loop. 



On Wed, 9/7/16, 'Jon Hough' via Programming <programm...@jsoftware.com> wrote:

 Subject: Re: [Jprogramming] Greatest Increasing Subsequence
 To: programm...@jsoftware.com
 Date: Wednesday, September 7, 2016, 2:26 PM
 
 Someone more knowledgeable than I can
 probably give a reason why this works, whereas yours
 didn't:
 {&(_1+i.5)^:(<4) 4
 
 4 3 2 1
 
 
 
 On Wed, 9/7/16, Xiao-Yong Jin <jinxiaoy...@gmail.com>
 wrote:
 
  Subject: Re: [Jprogramming] Greatest Increasing
 Subsequence
  To: programm...@jsoftware.com
  Date: Wednesday, September 7, 2016, 12:53 PM
  
  I’m trying to rewrite
  lisM in a readable tacit form but hit something I didn’t
  understand.
  Supplying i.n to ^: works fine,
  but  On Sep
  5, 2016, at 3:17 AM, 'Mike Day' via Programming
  <programm...@jsoftware.com>
  wrote:
  > 
  > Thanks
  Jon
  > 
  > lisM
  isn't really "my" version - I was just
  translating the pseudo-code...
  > I expect
  -without checking! - that its advantage over lisl resides
 in
  avoiding the do-it-yourself binary search by using J's
  built-in dyadic I. , albeit at the expense of an explicit
  sorted array, which I called mx .   I tried
  limiting the I. search to only the first L items of mx, 
  but with no benefit,  at least for the sizes I tried.  
  > The time taken to recover the result is
  fairly trivial,  so I don't suppose my use of 
  > |. x{~(p{~])^:(i.L) L{m 
  > is particularly interesting,  but it
  avoided that explicit while loop.
  > 
  > Mike
  > 
  > Please reply to mike_liz@tiscali.co.uk. 
      
  > Sent from my iPad
  > 
  >> On 5 Sep 2016,
  at 08:07, 'Jon Hough' via Programming <programm...@jsoftware.com>
  wrote:
  >> 
  >>
  Just out of interest, I compared the various results. 
  >> I wrote a fully imperative version,
  which uses in-place modification of the results array.
  >> 
  >> I also wrote
  a version that avoids any while / for loops (because I
  wanted to avoid using them), and ended up putting
  >> most of the logic in anonymous verbs.
  Which is probably a big mistake because that gets very
 slow.
  Also barely readable.
  >> 
  >>
  NB.===
  >> 
  >> NB. Jon -
  bizarre version. Uses anonymous verbs for most of the
 logic.
  
  >> NB. Slow and, uses huge amounts of
  memory.
  >> appendOrInsert=:(3 :
  'insert max' [ 3 :
  '(max=:<:#lst)[(min=:0)[val=:i{r[i=:y')`(3 :
  '(lst=:lst,y)[prev=:(_1{lst) y} prev')@.(3 :
  '(val>({:lst){r)[val=:y{r')
  >> insert=:(3 : '(prev=:
  ((y-1){lst)i}prev)[(lst=: i y }lst)' ] ])@:(3 :
  'mid'`(3 : 'min=: mid+1')@.(3 :
  '(val>(mid{lst){r)[(mid=:<.(min+y)%2)')^:(0&<)^:_)
  >> 
  >> lisJ =: 3 :
  0
  >> r=:y              NB.
  array
  >>
  [val=:0[max=:0[mid=:0[min=:0  NB. useful numbers
  >> lst=:0            NB. list of
  indices
  >> prev=: (#y)#0       
  NB. previous indices
  >> i=:0     
        NB. current index
  >> 
  >> appendOrInsert"0 >: i.<: #
  y    NB. append the items, or insert them, into lst (and
  update prev)
  >> res=:''
  >> ptr=: _1{lst
  >>
  (ptr)^:(#lst) res
  >> |.
  res
  >> )
  >> 
  >> buildEx =: 4 : 0
  >> res=:y,ptr{r
  >>
  ptr=: ptr{prev
  >> res
  >> )
  >> 
  >> 
  >>
  NB.===
  >> 
  >> 
  >> NB. Imperative version. just for
  benchmarking
  >> lisI =: 3 : 0
  >> lst =: 0
  >> r=:
  y
  >> parent=: (#y)#0
  >> for_i.>:i.<:# r do.
  >> if.((i{r) > ({: lst){r )  do.
  >> parent=:(_1{lst) i}parent
  >> lst =: lst, i
  >>
  else.
  >> min=: 0
  >> max =: <:#lst
  >> while. min < max do.
  >> mid =: <. (min + max) % 2
  >> if. (i{r) > ((mid { lst{r)) do. min
  =: mid + 1
  >> else. max =: mid end.
  >> end.
  >> lst=:
  (i) max} lst
  >> parent=:
  ((max-1){lst)(i}) parent
  >> end.
  >> end.
  >> res=:
  ''
  >> ptr=: _1{lst
  >> while. (# res) < # lst do.
  >> res=:res,ptr{r
  >> ptr=:ptr{parent
  >> end.
  >> I.
  res
  >> )
  >> 
  >> 
  >> 
  >>
  NB.===
  >> 
  >> 
  >> NB. Mike's version. 
  >> 
  >> lisM =: 3 :
  0
  >> n  

Re: [Jprogramming] Greatest Increasing Subsequence

['Jon Hough' via Programming]

Someone more knowledgeable than I can probably give a reason why this works, 
whereas yours didn't:
{&(_1+i.5)^:(<4) 4

4 3 2 1



On Wed, 9/7/16, Xiao-Yong Jin <jinxiaoy...@gmail.com> wrote:

 Subject: Re: [Jprogramming] Greatest Increasing Subsequence
 To: programm...@jsoftware.com
 Date: Wednesday, September 7, 2016, 12:53 PM
 
 I’m trying to rewrite
 lisM in a readable tacit form but hit something I didn’t
 understand.
 Supplying i.n to ^: works fine,
 but  On Sep
 5, 2016, at 3:17 AM, 'Mike Day' via Programming
 <programm...@jsoftware.com>
 wrote:
 > 
 > Thanks
 Jon
 > 
 > lisM
 isn't really "my" version - I was just
 translating the pseudo-code...
 > I expect
 -without checking! - that its advantage over lisl resides in
 avoiding the do-it-yourself binary search by using J's
 built-in dyadic I. , albeit at the expense of an explicit
 sorted array, which I called mx .   I tried
 limiting the I. search to only the first L items of mx, 
 but with no benefit,  at least for the sizes I tried.  
 > The time taken to recover the result is
 fairly trivial,  so I don't suppose my use of 
 > |. x{~(p{~])^:(i.L) L{m 
 > is particularly interesting,  but it
 avoided that explicit while loop.
 > 
 > Mike
 > 
 > Please reply to mike_liz@tiscali.co.uk. 
     
 > Sent from my iPad
 > 
 >> On 5 Sep 2016,
 at 08:07, 'Jon Hough' via Programming <programm...@jsoftware.com>
 wrote:
 >> 
 >>
 Just out of interest, I compared the various results. 
 >> I wrote a fully imperative version,
 which uses in-place modification of the results array.
 >> 
 >> I also wrote
 a version that avoids any while / for loops (because I
 wanted to avoid using them), and ended up putting
 >> most of the logic in anonymous verbs.
 Which is probably a big mistake because that gets very slow.
 Also barely readable.
 >> 
 >>
 NB.===
 >> 
 >> NB. Jon -
 bizarre version. Uses anonymous verbs for most of the logic.
 
 >> NB. Slow and, uses huge amounts of
 memory.
 >> appendOrInsert=:(3 :
 'insert max' [ 3 :
 '(max=:<:#lst)[(min=:0)[val=:i{r[i=:y')`(3 :
 '(lst=:lst,y)[prev=:(_1{lst) y} prev')@.(3 :
 '(val>({:lst){r)[val=:y{r')
 >> insert=:(3 : '(prev=:
 ((y-1){lst)i}prev)[(lst=: i y }lst)' ] ])@:(3 :
 'mid'`(3 : 'min=: mid+1')@.(3 :
 '(val>(mid{lst){r)[(mid=:<.(min+y)%2)')^:(0&<)^:_)
 >> 
 >> lisJ =: 3 :
 0
 >> r=:y              NB.
 array
 >>
 [val=:0[max=:0[mid=:0[min=:0  NB. useful numbers
 >> lst=:0            NB. list of
 indices
 >> prev=: (#y)#0       
 NB. previous indices
 >> i=:0     
       NB. current index
 >> 
 >> appendOrInsert"0 >: i.<: #
 y    NB. append the items, or insert them, into lst (and
 update prev)
 >> res=:''
 >> ptr=: _1{lst
 >>
 (ptr)^:(#lst) res
 >> |.
 res
 >> )
 >> 
 >> buildEx =: 4 : 0
 >> res=:y,ptr{r
 >>
 ptr=: ptr{prev
 >> res
 >> )
 >> 
 >> 
 >>
 NB.===
 >> 
 >> 
 >> NB. Imperative version. just for
 benchmarking
 >> lisI =: 3 : 0
 >> lst =: 0
 >> r=:
 y
 >> parent=: (#y)#0
 >> for_i.>:i.<:# r do.
 >> if.((i{r) > ({: lst){r )  do.
 >> parent=:(_1{lst) i}parent
 >> lst =: lst, i
 >>
 else.
 >> min=: 0
 >> max =: <:#lst
 >> while. min < max do.
 >> mid =: <. (min + max) % 2
 >> if. (i{r) > ((mid { lst{r)) do. min
 =: mid + 1
 >> else. max =: mid end.
 >> end.
 >> lst=:
 (i) max} lst
 >> parent=:
 ((max-1){lst)(i}) parent
 >> end.
 >> end.
 >> res=:
 ''
 >> ptr=: _1{lst
 >> while. (# res) < # lst do.
 >> res=:res,ptr{r
 >> ptr=:ptr{parent
 >> end.
 >> I.
 res
 >> )
 >> 
 >> 
 >> 
 >>
 NB.===
 >> 
 >> 
 >> NB. Mike's version. 
 >> 
 >> lisM =: 3 :
 0
 >> n       =.
 #x   =. y
 >> if. 2>#x
 do. x return. end.       NB. special case empty
 or singleton array
 >> if. (-:/:~)x do.
 ~.x return. end. NB. special case sorted arrays
 >> if. (-:\:~)x do. {.x return. end.
 >> p       =. n#0
 >> NB. seed m with trailing _1 so that
 final L (as in wiki algorithm) can be found
 >> m       =. n 0 }
 _1#~>:n
 >> NB. set up sorted mx,
 with just the first element of x, so that I. works
 >> mx      =. ({.x) 1 }
 (<:<./x), n#>:>./x
 >>
 for_i. i.n do.
 >>  xi    =. i{x
 >>  lo    =. mx I. xi

Re: [Jprogramming] Greatest Increasing Subsequence

[Xiao-Yong Jin]

amp;>) (= >./)@:* #&>@]
>> e=: }:@>@(#~ (= >./)@:(#&>))@>
>> 
>> s=: [: e (<<_) p&.>/@,~ <"0
>> pi=: ] , [ ,&.> ] {~ (< {.&>) (i. >./)@:* #&>@]
>> lisL =: [: e (<<_) pi&.>/@,~ <"0  NB. 
>> <- this one.
>> 
>> f=: ((] >: (-~ >./)) #&>) # ]
>> 
>> P=: ] , [ ,&.> ] #~ (< {.&>) (,@[ #^:_1 (= >./)@#) #&>@]
>> sp=: [: e (<<_) ({:@[ f {.@[ P ])&.>/@,~ (,&.> i.@#)
>> 
>> 
>> 
>> NB.=======
>> 
>> 
>> NB. Xiao's version with Raul's modifications. Renamed verbs to avoid 
>> clashing.
>> 
>> NB. dyads
>>  exr=:  (1 + {:@[ < ]) {. [ ; ,
>>  hxr=:  [: ; exr&.>
>> 
>> NB. monads
>>  gxr=: (}.@] ;~ {.@] ; (hxr {.))&>/
>>  cxr=: ({::~ [: (i. >./) #@>)@>@{.
>>  dxr=: (<_) ; ]
>>  lisXR=: ([: cxr gxr^:(#@(>@{:)))@dxr
>> 
>> NB.===
>> 
>> a=: 25 ? 25
>> timespacex 'lisI a'
>> timespacex 'lisJ a'
>> timespacex 'lisM a'
>> timespacex 'lisL a'
>> timespacex 'lisXR a' NB. comment out for larger arrays,a.
>> 
>> Playing around with various arrays, it seems lisM is the most efficient in 
>> time and space (more than the imperative version).
>> lisM and lisI can handle array larger than 1. The others struggle or 
>> give up with them. 
>> 
>> 
>> 
>> On Sun, 9/4/16, 'Mike Day' via Programming <programm...@jsoftware.com> wrote:
>> 
>> Subject: Re: [Jprogramming] Greatest Increasing Subsequence
>> To: programm...@jsoftware.com
>> Date: Sunday, September 4, 2016, 4:30 AM
>> 
>> This version of
>> "lis" is a bit more J-like,  especially in using
>> dyadic I.
>> instead of the diy binary search,
>> at the expense of a slightly more
>> complicated set-up for the m and mx arrays.
>> 
>> lis =: 3 : 0
>> n   =. #x   =. y
>> if. 2>#x do. x return. end.   
>>   NB. special case empty or singleton array
>> if. (-:/:~)x do. ~.x return. end. NB. special
>> case sorted arrays
>> if. (-:\:~)x do. {.x
>> return. end.
>> p   =. n#0
>> NB. seed m with trailing _1 so that final L (as
>> in wiki algorithm) can 
>> be found
>> m   =. n 0 } _1#~>:n
>> NB. set up sorted mx, with just the first
>> element of x, so that I. works
>> mx  =.
>> ({.x) 1 } (<:<./x), n#>:>./x
>> for_i. i.n do.
>>xi=.
>> i{x
>>lo=. mx I. xi
>>p =. (m{~<:lo) i } p
>> NB. better than appending to short p for 
>> larger x
>>m 
>>   =. i  lo } m
>>mx=.
>> xi lo } mx
>> end.
>> |.
>> x{~(p{~])^:(i.L) m{~ L =. <: m i. _1
>> )
>> 
>> Mike
>> 
>> 
>> On 02/09/2016 20:45, 'Mike
>> Day' via Programming wrote:
>>> Well,
>> assuming for now that it does work,  here's an attempt
>> at a J 
>>> version of
>> the pseudo-code listed at
>>> https://en.wikipedia.org/wiki/Longest_increasing_subsequence#Efficient_algorithms
>> 
>>> 
>>> 
>>> lis =: 3 : 0   NB. longest
>> increasing subsequence
>>> m   
>>   =. 0#~>:n   =.
>> #x   =. y
>>> L   
>>   =. #p   =. ''
>>> mx  =. m{x NB. added this vector
>> for better look-up of x{~mid{m
>>> for_i.
>> i.n do.
>>>   'lo hi' =.
>> 1, L
>>>xi =. i{x
>>>while. lo <: hi do.
>>>   mid=. >.@-: lo + hi
>> NB.   if. xi > x{~ mid{m do. NB. next
>> line a bit better
>>   if. xi > mid{mx do.
>>lo =. >: mid
>>   else.
>>>  hi =.
>> <: mid
>>>   end.
>>>end.
>>>p 
>>   =. p, m{~<:lo
>>>m 
>>   =. i  lo } m
>>>mx 
>>  =. xi lo } mxNB. update my additional array
>>>L =. L >. lo
>>> NB. smoutput i; (x{.~ >:i);
>> L{.m   NB. diagnostic
>> end.
>>> |. x{~(p{~])^:(i.L) L{m
>>> )
>>> 
>>> It's reasonably fast on ?1#5000 -
>> but possibly wrong!It does
>>> fail on an
>> empty array.
>> Mike
>>> 
>>> 
>>>> On 02/09/2016 17:30, Raul Miller wrote:
>>>> It seems to me that the
>> "efficient algorithm" documented on the
>>>> wikipedia page would have an analogous
>> flaw. It is performing binary
>> searches on unsorted lists. That said, it does perform
>> correctly for
>>>> this example.
>>>> 
>>>> Thanks,
>>> 
>>> 
>>> ---
>>> 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
>> 
>> 
>> ---
>> 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

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

Re: [Jprogramming] Greatest Increasing Subsequence

['Mike Day' via Programming]

> NB. dyads
>   exr=:  (1 + {:@[ < ]) {. [ ; ,
>   hxr=:  [: ; exr&.>
> 
> NB. monads
>   gxr=: (}.@] ;~ {.@] ; (hxr {.))&>/
>   cxr=: ({::~ [: (i. >./) #@>)@>@{.
>   dxr=: (<_) ; ]
>   lisXR=: ([: cxr gxr^:(#@(>@{:)))@dxr
> 
> NB.===
> 
> a=: 25 ? 25
> timespacex 'lisI a'
> timespacex 'lisJ a'
> timespacex 'lisM a'
> timespacex 'lisL a'
> timespacex 'lisXR a' NB. comment out for larger arrays,a.
> 
> Playing around with various arrays, it seems lisM is the most efficient in 
> time and space (more than the imperative version).
> lisM and lisI can handle array larger than 1. The others struggle or give 
> up with them. 
> 
> 
> 
> On Sun, 9/4/16, 'Mike Day' via Programming <programm...@jsoftware.com> wrote:
> 
> Subject: Re: [Jprogramming] Greatest Increasing Subsequence
> To: programm...@jsoftware.com
> Date: Sunday, September 4, 2016, 4:30 AM
> 
> This version of
> "lis" is a bit more J-like,  especially in using
> dyadic I.
> instead of the diy binary search,
> at the expense of a slightly more
> complicated set-up for the m and mx arrays.
> 
> lis =: 3 : 0
> n   =. #x   =. y
> if. 2>#x do. x return. end.   
>NB. special case empty or singleton array
> if. (-:/:~)x do. ~.x return. end. NB. special
> case sorted arrays
> if. (-:\:~)x do. {.x
> return. end.
> p   =. n#0
> NB. seed m with trailing _1 so that final L (as
> in wiki algorithm) can 
> be found
> m   =. n 0 } _1#~>:n
> NB. set up sorted mx, with just the first
> element of x, so that I. works
> mx  =.
> ({.x) 1 } (<:<./x), n#>:>./x
> for_i. i.n do.
> xi=.
> i{x
> lo=. mx I. xi
> p =. (m{~<:lo) i } p
> NB. better than appending to short p for 
> larger x
> m 
>=. i  lo } m
> mx=.
> xi lo } mx
> end.
> |.
> x{~(p{~])^:(i.L) m{~ L =. <: m i. _1
> )
> 
> Mike
> 
> 
> On 02/09/2016 20:45, 'Mike
> Day' via Programming wrote:
>> Well,
> assuming for now that it does work,  here's an attempt
> at a J 
>> version of
> the pseudo-code listed at
>> https://en.wikipedia.org/wiki/Longest_increasing_subsequence#Efficient_algorithms
> 
>> 
>> 
>> lis =: 3 : 0   NB. longest
> increasing subsequence
>> m   
>=. 0#~>:n   =.
> #x   =. y
>> L   
>=. #p   =. ''
>> mx  =. m{x NB. added this vector
> for better look-up of x{~mid{m
>> for_i.
> i.n do.
>>'lo hi' =.
> 1, L
>> xi =. i{x
>> while. lo <: hi do.
>>mid=. >.@-: lo + hi
> NB.   if. xi > x{~ mid{m do. NB. next
> line a bit better
>if. xi > mid{mx do.
> lo =. >: mid
>else.
>>   hi =.
> <: mid
>>end.
>> end.
>> p 
>=. p, m{~<:lo
>> m 
>=. i  lo } m
>> mx 
>   =. xi lo } mxNB. update my additional array
>> L =. L >. lo
>> NB. smoutput i; (x{.~ >:i);
> L{.m   NB. diagnostic
> end.
>> |. x{~(p{~])^:(i.L) L{m
>> )
>> 
>> It's reasonably fast on ?1#5000 -
> but possibly wrong!It does
>> fail on an
> empty array.
> Mike
>> 
>> 
>>> On 02/09/2016 17:30, Raul Miller wrote:
>>> It seems to me that the
> "efficient algorithm" documented on the
>>> wikipedia page would have an analogous
> flaw. It is performing binary
> searches on unsorted lists. That said, it does perform
> correctly for
>>> this example.
>>> 
>>> Thanks,
>> 
>> 
>> ---
>> 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
> 
> 
> ---
> 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

Re: [Jprogramming] Greatest Increasing Subsequence

['Mike Day' via Programming]

This version of "lis" is a bit more J-like,  especially in using dyadic I.
instead of the diy binary search, at the expense of a slightly more
complicated set-up for the m and mx arrays.

lis =: 3 : 0
n   =. #x   =. y
if. 2>#x do. x return. end.   NB. special case empty or singleton array
if. (-:/:~)x do. ~.x return. end. NB. special case sorted arrays
if. (-:\:~)x do. {.x return. end.
p   =. n#0
NB. seed m with trailing _1 so that final L (as in wiki algorithm) can 
be found

m   =. n 0 } _1#~>:n
NB. set up sorted mx, with just the first element of x, so that I. works
mx  =. ({.x) 1 } (<:<./x), n#>:>./x
for_i. i.n do.
   xi=. i{x
   lo=. mx I. xi
   p =. (m{~<:lo) i } p NB. better than appending to short p for 
larger x

   m =. i  lo } m
   mx=. xi lo } mx
end.
|. x{~(p{~])^:(i.L) m{~ L =. <: m i. _1
)

Mike


On 02/09/2016 20:45, 'Mike Day' via Programming wrote:
Well, assuming for now that it does work,  here's an attempt at a J 
version of

the pseudo-code listed at
https://en.wikipedia.org/wiki/Longest_increasing_subsequence#Efficient_algorithms 



lis =: 3 : 0   NB. longest increasing subsequence
m   =. 0#~>:n   =. #x   =. y
L   =. #p   =. ''
mx  =. m{x NB. added this vector for better look-up of x{~mid{m
for_i. i.n do.
  'lo hi' =. 1, L
   xi =. i{x
   while. lo <: hi do.
  mid=. >.@-: lo + hi
NB.   if. xi > x{~ mid{m do. NB. next line a bit better
  if. xi > mid{mx do.
 lo =. >: mid
  else.
 hi =. <: mid
  end.
   end.
   p =. p, m{~<:lo
   m =. i  lo } m
   mx=. xi lo } mxNB. update my additional array
   L =. L >. lo
NB. smoutput i; (x{.~ >:i); L{.m   NB. diagnostic
end.
|. x{~(p{~])^:(i.L) L{m
)

It's reasonably fast on ?1#5000 - but possibly wrong!It does
fail on an empty array.

Mike


On 02/09/2016 17:30, Raul Miller wrote:

It seems to me that the "efficient algorithm" documented on the
wikipedia page would have an analogous flaw. It is performing binary
searches on unsorted lists. That said, it does perform correctly for
this example.

Thanks,




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



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

Re: [Jprogramming] Greatest Increasing Subsequence

[Louis de Forcrand]

The best me and my father could come up with is:

s=: [: e (<<_) p&.>/@,~ <"0
p=: ] , [ ,&.> ] #~ (< {.&>) (= >./)@:* #&>@]
e=: }:@>@(#~ (= >./)@:(#&>))@>

si=: [: e (<<_) pi&.>/@,~ <"0
pi=: ] , [ ,&.> ] {~ (< {.&>) (i. >./)@:* #&>@]

Let v be a valid increasing subsequence. If n < {.v then n,v is also a valid 
subsequence,
except of course if 0 = #v. This is solved by beginning the operation with a 
single
subsequence containing only infinity. This also acts as a catch for numbers 
which fit
in front of no longer subsequences.
s uses a basic breadth-first search, while it saves intermediate parent nodes 
as well.
This is because, even if n,v is a valid subsequence, if m is much greater than 
n but still
smaller than {.v, then chances are that m,v will lead to longer final 
subsequences than
n,v.

Because it uses a breadth-first search, s finds all subsequences of maximal 
(and equal)
length. This leads to a slow-down, and can be fixed by appending n to only the 
first
subsequence found which satisfies all the conditions. However, this new 
function si will
only find some of the possible subsequences. That is, if pi has to choose 
between
prepending n to v1 or v2, it will only prepend it to v1. Duplicate subsequences 
are still
possible if a number appears twice in the original sequence.

Another independent optimisation could be to keep track of how many elements 
are left
in the total sequence, and eliminate subsequences which are shorter than the 
length of
the longest subsequence minus the number of elements left, as they cannot 
possibly
catch up with the longest subsequence even if it stays the same length and they 
get
appended to all elements left.
I did try this however, and the resources necessary to do the filtering ended 
up being
more costly than simply keeping all subsequences. Nevertheless, here are the 
functions:

NB. with compression
sp=: [: e (<<_) ({:@[ f {.@[ P ])&.>/@,~ (,&.> i.@#)
P=: ] , [ ,&.> ] #~ (< {.&>) (,@[ #^:_1 (= >./)@#) #&>@]
f=: ((] >: (-~ >./)) #&>) # ]

NB. with indexing
spi=: [: e (<<_) ({:@[ f {.@[ Pi ])&.>/@,~ (,&.> i.@#)
Pi=: ] , [ ,&.> ] {~ (< {.&>) ([: {.^:(*@#)@I. ,@[ #^:_1 (= >./)@#) #&>@]


si is the fastest, and I can run it fast enough with arguments of up to 2000 
elements,
but beyond that the version from Wikipedia is much faster and more economical 
in space.

Cheers,
Louis

> On 02 Sep 2016, at 22:21, Raul Miller  wrote:
> 
> NB. dyads
>   e=:  (1 + {:@[ < ]) {. [ ; ,
>   h=:  [: ; e&.>
> 
> NB. monads
>   g=: (}.@] ;~ {.@] ; (h {.))&>/
>   c=: ({::~ [: (i. >./) #@>)@>@{.
>   d=: (<_) ; ]
>   f=: ([: c g^:(#@(>@{:)))@d

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

Re: [Jprogramming] Greatest Increasing Subsequence

[Raul Miller]

That blew up for me, and I did not feel motivated to dump my existing
j session, so I rewrote it a bit:

NB. dyads
   e=:  (1 + {:@[ < ]) {. [ ; ,
   h=:  [: ; e&.>

NB. monads
   g=: (}.@] ;~ {.@] ; (h {.))&>/
   c=: ({::~ [: (i. >./) #@>)@>@{.
   d=: (<_) ; ]
   f=: ([: c g^:(#@(>@{:)))@d

I don't think this is much faster. But it seems to still work.

Those sub-expressions could use better names.

Thanks,

-- 
Raul

On Fri, Sep 2, 2016 at 2:06 PM, Xiao-Yong Jin <jinxiaoy...@gmail.com> wrote:
> Came up with this:
>
>f=.u@d
>u=.[: c g^:(#@n)
>d=.(<_) ; ]
>c=.[: > s {~ [: {.@\: #@>@s
>g=.}.@n ;~ {.@n ; s h {.@n
>n=.>@{:
>s=.>&{.
>h=.[: ; e&.>
>e=.<@[`([ ; [ , ])@.t
>t=.{:@[ < ]
>f 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
> 1 2 3 4 5 7 11 19
>
> Let me know if you can optimize it.
>
>> On Sep 2, 2016, at 11:30 AM, Raul Miller <rauldmil...@gmail.com> wrote:
>>
>> It seems to me that the "efficient algorithm" documented on the
>> wikipedia page would have an analogous flaw. It is performing binary
>> searches on unsorted lists. That said, it does perform correctly for
>> this example.
>>
>> Thanks,
>>
>> --
>> Raul
>>
>>
>>
>> On Fri, Sep 2, 2016 at 12:18 PM, jonghough via Programming
>> <programm...@jsoftware.com> wrote:
>>>
>>>
>>> Yes, Raul is absolutely correct. And the flaw (in my solution, at least) is 
>>> obvious now. I'll try for a correct solution again tomorrow.
>>>
>>>
>>>
>>>
>>> From: 'Mike Day' via Programming
>>>
>>> Sent: Saturday, September 3, 00:26
>>>
>>> Subject: Re: [Jprogramming] Greatest Increasing Subsequence
>>>
>>> To: 'Mike Day' via Programming
>>>
>>>
>>>
>>> Same problem with my version, which was faster but equally wrong! Mike On 
>>> 02/09/2016 14:57, Raul Miller wrote: > Actually, if we try your approach on 
>>> -8 2 4 3 1 6 we get _8 _2 _1 > instead of _8 _4 _3 _1. > > Here's a brute 
>>> force O(2^n) approach that I hacked up earlier - it > obviously only works 
>>> on short lists: > > increasing=: (-: /:~)@#~"1 #:@i.@^~&2@# > longestinc=: 
>>> ] #~ [: (#~ ([: (= >./) +/"1)) #:@I.@increasing > > We can do better, of 
>>> course, but I have some other things I want to > deal with, first. > > 
>>> Thanks, > --- 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
>
> --
> For information about J forums see http://www.jsoftware.com/forums.htm
--
For information about J forums see http://www.jsoftware.com/forums.htm

Re: [Jprogramming] Greatest Increasing Subsequence

['Mike Day' via Programming]

Well, assuming for now that it does work,  here's an attempt at a J 
version of

the pseudo-code listed at
https://en.wikipedia.org/wiki/Longest_increasing_subsequence#Efficient_algorithms

lis =: 3 : 0   NB. longest increasing subsequence
m   =. 0#~>:n   =. #x   =. y
L   =. #p   =. ''
mx  =. m{x NB. added this vector for better look-up of x{~mid{m
for_i. i.n do.
  'lo hi' =. 1, L
   xi =. i{x
   while. lo <: hi do.
  mid=. >.@-: lo + hi
NB.   if. xi > x{~ mid{m do. NB. next line a bit better
  if. xi > mid{mx do.
 lo =. >: mid
  else.
 hi =. <: mid
  end.
   end.
   p =. p, m{~<:lo
   m =. i  lo } m
   mx=. xi lo } mxNB. update my additional array
   L =. L >. lo
NB. smoutput i; (x{.~ >:i); L{.m   NB. diagnostic
end.
|. x{~(p{~])^:(i.L) L{m
)

It's reasonably fast on ?1#5000 - but possibly wrong!It does
fail on an empty array.

Mike


On 02/09/2016 17:30, Raul Miller wrote:

It seems to me that the "efficient algorithm" documented on the
wikipedia page would have an analogous flaw. It is performing binary
searches on unsorted lists. That said, it does perform correctly for
this example.

Thanks,




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

Re: [Jprogramming] Greatest Increasing Subsequence

[Xiao-Yong Jin]

Came up with this:

   f=.u@d
   u=.[: c g^:(#@n)
   d=.(<_) ; ]
   c=.[: > s {~ [: {.@\: #@>@s
   g=.}.@n ;~ {.@n ; s h {.@n
   n=.>@{:
   s=.>&{.
   h=.[: ; e&.>
   e=.<@[`([ ; [ , ])@.t
   t=.{:@[ < ]
   f 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
1 2 3 4 5 7 11 19

Let me know if you can optimize it.

> On Sep 2, 2016, at 11:30 AM, Raul Miller <rauldmil...@gmail.com> wrote:
> 
> It seems to me that the "efficient algorithm" documented on the
> wikipedia page would have an analogous flaw. It is performing binary
> searches on unsorted lists. That said, it does perform correctly for
> this example.
> 
> Thanks,
> 
> -- 
> Raul
> 
> 
> 
> On Fri, Sep 2, 2016 at 12:18 PM, jonghough via Programming
> <programm...@jsoftware.com> wrote:
>> 
>> 
>> Yes, Raul is absolutely correct. And the flaw (in my solution, at least) is 
>> obvious now. I'll try for a correct solution again tomorrow.
>> 
>> 
>> 
>> 
>> From: 'Mike Day' via Programming
>> 
>> Sent: Saturday, September 3, 00:26
>> 
>> Subject: Re: [Jprogramming] Greatest Increasing Subsequence
>> 
>> To: 'Mike Day' via Programming
>> 
>> 
>> 
>> Same problem with my version, which was faster but equally wrong! Mike On 
>> 02/09/2016 14:57, Raul Miller wrote: > Actually, if we try your approach on 
>> -8 2 4 3 1 6 we get _8 _2 _1 > instead of _8 _4 _3 _1. > > Here's a brute 
>> force O(2^n) approach that I hacked up earlier - it > obviously only works 
>> on short lists: > > increasing=: (-: /:~)@#~"1 #:@i.@^~&2@# > longestinc=: ] 
>> #~ [: (#~ ([: (= >./) +/"1)) #:@I.@increasing > > We can do better, of 
>> course, but I have some other things I want to > deal with, first. > > 
>> Thanks, > --- 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

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

Re: [Jprogramming] Greatest Increasing Subsequence

[Raul Miller]

It seems to me that the "efficient algorithm" documented on the
wikipedia page would have an analogous flaw. It is performing binary
searches on unsorted lists. That said, it does perform correctly for
this example.

Thanks,

-- 
Raul



On Fri, Sep 2, 2016 at 12:18 PM, jonghough via Programming
<programm...@jsoftware.com> wrote:
>
>
> Yes, Raul is absolutely correct. And the flaw (in my solution, at least) is 
> obvious now. I'll try for a correct solution again tomorrow.
>
>
>
>
> From: 'Mike Day' via Programming
>
> Sent: Saturday, September 3, 00:26
>
> Subject: Re: [Jprogramming] Greatest Increasing Subsequence
>
> To: 'Mike Day' via Programming
>
>
>
> Same problem with my version, which was faster but equally wrong! Mike On 
> 02/09/2016 14:57, Raul Miller wrote: > Actually, if we try your approach on 
> -8 2 4 3 1 6 we get _8 _2 _1 > instead of _8 _4 _3 _1. > > Here's a brute 
> force O(2^n) approach that I hacked up earlier - it > obviously only works on 
> short lists: > > increasing=: (-: /:~)@#~"1 #:@i.@^~&2@# > longestinc=: ] #~ 
> [: (#~ ([: (= >./) +/"1)) #:@I.@increasing > > We can do better, of course, 
> but I have some other things I want to > deal with, first. > > Thanks, > --- 
> 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

Re: [Jprogramming] Greatest Increasing Subsequence

[jonghough via Programming]

Yes, Raul is absolutely correct. And the flaw (in my solution, at least) is 
obvious now. I'll try for a correct solution again tomorrow.




From: 'Mike Day' via Programming

Sent: Saturday, September 3, 00:26

Subject: Re: [Jprogramming] Greatest Increasing Subsequence

To: 'Mike Day' via Programming



Same problem with my version, which was faster but equally wrong! Mike On 
02/09/2016 14:57, Raul Miller wrote: > Actually, if we try your approach on -8 
2 4 3 1 6 we get _8 _2 _1 > instead of _8 _4 _3 _1. > > Here's a brute force 
O(2^n) approach that I hacked up earlier - it > obviously only works on short 
lists: > > increasing=: (-: /:~)@#~"1 #:@i.@^~&2@# > longestinc=: ] #~ [: (#~ 
([: (= >./) +/"1)) #:@I.@increasing > > We can do better, of course, but I have 
some other things I want to > deal with, first. > > Thanks, > --- 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

Re: [Jprogramming] Greatest Increasing Subsequence

['Mike Day' via Programming]

Same problem with my version,  which was faster but equally wrong!

Mike


On 02/09/2016 14:57, Raul Miller wrote:

Actually, if we try your approach on -8 2 4 3 1 6 we get _8 _2 _1
instead of _8 _4 _3 _1.

Here's a brute force O(2^n) approach that I hacked up earlier - it
obviously only works on short lists:

increasing=: (-: /:~)@#~"1 #:@i.@^~&2@#
longestinc=: ] #~ [: (#~ ([: (= >./) +/"1)) #:@I.@increasing

We can do better, of course, but I have some other things I want to
deal with, first.

Thanks,




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

Re: [Jprogramming] Greatest Increasing Subsequence

[Raul Miller]

Actually, if we try your approach on -8 2 4 3 1 6 we get _8 _2 _1
instead of _8 _4 _3 _1.

Here's a brute force O(2^n) approach that I hacked up earlier - it
obviously only works on short lists:

increasing=: (-: /:~)@#~"1 #:@i.@^~&2@#
longestinc=: ] #~ [: (#~ ([: (= >./) +/"1)) #:@I.@increasing

We can do better, of course, but I have some other things I want to
deal with, first.

Thanks,

-- 
Raul

On Thu, Sep 1, 2016 at 10:38 PM, 'Jon Hough' via Programming
 wrote:
> Given a list of numbers, find the greatest increasing subsequence of the list.
>
> e.g if list  is 6 1 3 4 2 8 then the greatest increasing subsequence is 1 3 4 
> 8.
>
> My solution:
>
> NB. find greatest increasing subsequence of number list.
>
> NB. example list
> 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
>
> NB. running max
> max =: __
>
> NB. verb tests for new max, returns 1 if
> NB. y is greater than current max, 0 otherwise.
> g =: 3 : 0
> gr =: 0
> if. y > max do.
> max =: y
> gr=. 1
> end.
> gr
> )
>
>
>
> NB. find the indices in increasing subsequence
> inc =: ((3 : 'max =: __')](g"0)&.>)"0(]@:<)\. l
>
> NB. get the items with max index count. take the first item.
> getmax =: I.@:(= >./)@:>@:(+/&.>) (I.@:>@:{.@:{ + {.@:[) ]
> indices =: getmax inc
> NB. return the items at given indices.
> indices { l
>
>
> This works fine, but seems overly complicated... and ugly. Any better 
> solutions?
> Also this algorithm is O(n^2) in time, but the most efficient algorithm can 
> be O(n log n).( https://en.wikipedia.org/wiki/Longest_increasing_subsequence )
> --
> For information about J forums see http://www.jsoftware.com/forums.htm
--
For information about J forums see http://www.jsoftware.com/forums.htm

Re: [Jprogramming] Greatest Increasing Subsequence

['Mike Day' via Programming]

I came up with this.

f =: (;@:{~ (i. >./)@:(#&>))@:(<@~.@:(>./\)\.)

NB. The main ingredient is ~.@:(>./\)
   ~.@:(>./\) l
7 8 13 15 19
   ~.@:(>./\) }.l
4 5 7 8 13 15 19

   f l
4 5 7 8 13 15 19

NB. If there are more than one different subseqs
NB. of equal length, it returns the first.
NB. It fails on i.0
NB. I haven't checked it thoroughly.

NB. time and space on your l,
NB. 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


   ts'l{~getmax ((3 : ''max =: __'')](g"0)&.>)"0(]@:<)\. l'
0.000665763 28416
   ts'f l'
7.39736e_5 13696

NB. Timer does what it says on the box,  showing the result, but
NB. not the space requirement.
NB. Boxes will probably line-wrap...

bigl =: ?1#5000   NB. repeat rate approx 2

timer'bigl{~getmax ((3 : ''max =: __'')](g"0)&.>)"0(]@:<)\. bigl'
+--+-+
|45.864|214 2236 2865 3360 3513 3821 3838 4080 4224 4587 4663 4755 4959 
4965 4969 4970 4994 4997 4999|

+--+-+

timer'f bigl'
++-+
|0.622002|214 2236 2865 3360 3513 3821 3838 4080 4224 4587 4663 4755 
4959 4965 4969 4970 4994 4997 4999|

++-+

Quicker but is it quick enough?  Is this what you were after?

Mike

On 02/09/2016 03:38, 'Jon Hough' via Programming wrote:

Given a list of numbers, find the greatest increasing subsequence of the list.

e.g if list  is 6 1 3 4 2 8 then the greatest increasing subsequence is 1 3 4 8.

My solution:

NB. find greatest increasing subsequence of number list.

NB. example list
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

NB. running max
max =: __

NB. verb tests for new max, returns 1 if
NB. y is greater than current max, 0 otherwise.
g =: 3 : 0
gr =: 0
if. y > max do.
max =: y
gr=. 1
end.
gr
)



NB. find the indices in increasing subsequence
inc =: ((3 : 'max =: __')](g"0)&.>)"0(]@:<)\. l

NB. get the items with max index count. take the first item.
getmax =: I.@:(= >./)@:>@:(+/&.>) (I.@:>@:{.@:{ + {.@:[) ]
indices =: getmax inc
NB. return the items at given indices.
indices { l


This works fine, but seems overly complicated... and ugly. Any better solutions?
Also this algorithm is O(n^2) in time, but the most efficient algorithm can be 
O(n log n).( https://en.wikipedia.org/wiki/Longest_increasing_subsequence )
--
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