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 10000?10000'
2.40974 3.808e6
ts'LongestIncreasingSubsequence ?10000$10000'
2.46657 3.41504e6
It still uses a lot of memory. Handles 100 000 with quite some struggle.
ts'LongestIncreasingSubsequence ?100000$100000'
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 {. <i.0
2 AddGroupWithLeftIfNoGroups , <1 2
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 10000?10000'
ts'LongestIncreasingSubsequence ?10000$10000'
----------------------------------------------------------------------
For information about J forums see http://www.jsoftware.com/forums.htm
----------------------------------------------------------------------
For information about J forums see http://www.jsoftware.com/forums.htm
