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 {. <i.0
2 AddGroupWIthLeftIfNoGroups , <1 2
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
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
LongestIncreasingSubsequence 1000?1000
On 2016-09-08 14:14, 'Mike Day' via Programming wrote:
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 10000 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 {. <i.0
2 AddGroupWIthLeftIfNoGroups , <1 2
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
----------------------------------------------------------------------
For information about J forums see http://www.jsoftware.com/forums.htm
