Yes, that seems to get similar results. Cheers, Mike Please reply to [email protected]. Sent from my iPad
> On 8 Sep 2016, at 13:33, Erling Hellenäs <[email protected]> wrote: > > 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 ---------------------------------------------------------------------- For information about J forums see http://www.jsoftware.com/forums.htm
