64 lines
2.6 KiB
AppleScript
64 lines
2.6 KiB
AppleScript
on longestIncreasingSubsequences(aList)
|
|
script o
|
|
property inputList : aList
|
|
property m : {} -- End indices of identified subsequences.
|
|
property p : {} -- 'Predecessor' indices for each point in each subsequence.
|
|
property subsequence : {} -- Reconstructed longest sequence.
|
|
end script
|
|
-- Set m and p to lists of the same length as the input. Their initial contents don't matter!
|
|
copy aList to o's m
|
|
copy aList to o's p
|
|
|
|
set bestLength to 0
|
|
repeat with i from 1 to (count o's inputList)
|
|
-- Comments adapted from those in the Wikipedia article — as far as they can be understood!
|
|
-- Binary search for the largest possible 'lo' ≤ bestLength such that inputList[m[lo]] ≤ inputList[i].
|
|
set lo to 1
|
|
set hi to bestLength
|
|
repeat until (lo > hi)
|
|
set mid to (lo + hi + 1) div 2
|
|
if (item (item mid of o's m) of o's inputList < item i of o's inputList) then
|
|
set lo to mid + 1
|
|
else
|
|
set hi to mid - 1
|
|
end if
|
|
end repeat
|
|
-- After searching, lo is 1 greater than the length of the longest prefix of inputList[i].
|
|
-- The predecessor of inputList[i] is the last index of the subsequence of length lo - 1.
|
|
if (lo > 1) then set item i of o's p to item (lo - 1) of o's m
|
|
set item lo of o's m to i
|
|
-- If we found a subsequence longer than or the same length as any we've found yet,
|
|
-- update bestLength and store the end index associated with it.
|
|
if (lo > bestLength) then
|
|
set bestLength to lo
|
|
set bestEndIndices to {item bestLength of o's m}
|
|
else if (lo = bestLength) then
|
|
set end of bestEndIndices to item bestLength of o's m
|
|
end if
|
|
end repeat
|
|
-- Reconstruct the longest increasing subsequence(s).
|
|
set output to {}
|
|
if (bestLength > 0) then
|
|
repeat with k in bestEndIndices
|
|
set o's subsequence to {}
|
|
repeat bestLength times
|
|
set beginning of o's subsequence to item k of o's inputList
|
|
set k to item k of o's p
|
|
end repeat
|
|
set end of output to o's subsequence
|
|
end repeat
|
|
end if
|
|
|
|
return output
|
|
end longestIncreasingSubsequences
|
|
|
|
-- Task code and other tests:
|
|
local tests, output, input
|
|
set tests to {{3, 2, 6, 4, 5, 1}, {0, 8, 4, 12, 2, 10, 6, 14, 1, 9, 5, 13, 3, 11, 7, 15}, ¬
|
|
{9, 10, 11, 3, 8, 9, 6, 7, 4, 5}, {4, 5, 5, 6}, {5, 5}}
|
|
set output to {}
|
|
repeat with input in tests
|
|
set end of output to {finds:longestIncreasingSubsequences(input's contents)}
|
|
end repeat
|
|
return output
|