Beefy Boxes and Bandwidth Generously Provided by pair Networks
Keep It Simple, Stupid
 
PerlMonks  

Re: Puzzle: Longest Increasing Sequence

by ikegami (Pope)
on Apr 16, 2006 at 08:49 UTC ( #543626=note: print w/ replies, xml ) Need Help??


in reply to Puzzle: Longest Increasing Sequence

This is just a conversion to Perl of this pseudocode. It finds a Longuest Ascending Sequence in O(N log N). The sequence it happens to find is the first sequence when sorted numerically.

# Minimal Longest Ascending Subsequence sub mlas { my $n_las; # Length of output sequence my @las; # Output sequence my @terminals; # Array of terminals my @backptrs; # Array of back pointers $terminals[1] = 0; $backptrs[0] = -1; $n_las = 1; for my $i (1..$#_) { my $low = 1; my $high = $n_las; while ($low <= $high) { my $mid = int(($low + $high) / 2); if ($_[$i] <= $_[$terminals[$mid]]) { $high = $mid - 1; } else { $low = $mid + 1; } } $terminals[$low] = $i; if ($low <= 1) { $backptrs[$i] = -1; } else { $backptrs[$i] = $terminals[$low - 1]; } if ($low > $n_las) { $n_las++; } } for ( my $i = $terminals[$n_las]; $i != -1; $i = $backptrs[$i] ) { unshift(@las, $_[$i]); } return @las; } { my @a = (8, 6, 5, 1, 9, 3, 7, 4, 2, 10); my @mlas = mlas(@a); local $, = ", "; local $\ = "\n"; print(@mlas); # 1, 3, 4, 10 } { my @a = (3, 10, 6, 1, 5, 7, 8, 2, 4, 9); my @mlas = mlas(@a); local $, = ", "; local $\ = "\n"; print(@mlas); # 1, 5, 7, 8, 9 }

The page mentions a secant search would be faster than a binary search although the O() of would still be the same The O() would be slightly better, as noted by jdalbec.


Comment on Re: Puzzle: Longest Increasing Sequence
Download Code
Re^2: Puzzle: Longest Increasing Sequence
by jdalbec (Deacon) on Apr 16, 2006 at 21:55 UTC
    Actually, O(n*log(n)**((sqrt(5)-1)/2)) is strictly less than O(n*log(n)). The difference probably won't be noticeable for reasonable values of n, though, since log(n) grows so slowly anyway.
      oh yeah. I thought it was *, not **
Re^2: Puzzle: Longest Increasing Sequence
by spurperl (Priest) on Apr 17, 2006 at 09:59 UTC
    Just for kicks, here is the same implemented in Ruby. I noticed that the original page has a bug you fixed - towards the end of the main loop, there is:
    if ($low > $n_las) { $n_las++; }
    While in the pseudocode it's "if (low .ge. n_as) n_as += 1" and I presume .ge. means "greater or equal" ?!

    Anyways, here's my implementation. It is notably cleaner than yours, but twice slower:

    def find_lis_greedy(seq) n = seq.length terminals = [0] * (n + 1) backptrs = [-1] + [0] * (n - 1) lis = [] n_lis = 1 1.upto(n - 1) do |i| low = 1 high = n_lis while low <= high mid = (low + high) / 2 if seq[i] <= seq[terminals[mid]] high = mid - 1 else low = mid + 1 end end terminals[low] = i if low <= 1 backptrs[i] = -1 else backptrs[i] = terminals[low - 1] end n_lis += 1 if low > n_lis end lis[n_lis - 1] = seq[terminals[n_lis]] temp = terminals[n_lis] (n_lis - 2).downto(0) do |i| temp = backptrs[temp] lis[i] = seq[temp] end return lis end

      It is indeed a bug fix, not a typo.

      The other thing I did was to clean up the code that builds the return value by using unshift. I no longer needed a counting loop, so I removed the counter variable ("i") and replaced the counting loop with a while loop (implemented as a for loop). "temp" was a bad name — even i, j, etc would be better since temp holds an index — so I renamed it to "i".

Re^2: Puzzle: Longest Increasing Sequence
by demerphq (Chancellor) on May 16, 2006 at 19:11 UTC

    It finds a Longuest Ascending Sequence in O(N log N). The sequence it happens to find is the first sequence when sorted numerically.

    I implemented a variant of this that will find all longest increasing sequences in the list.

    It returns an iterator over all of the LAS'es in the list. The code contains an explanation of how it works.

    ---
    $world=~s/war/peace/g

Log In?
Username:
Password:

What's my password?
Create A New User
Node Status?
node history
Node Type: note [id://543626]
help
Chatterbox?
and the web crawler heard nothing...

How do I use this? | Other CB clients
Other Users?
Others musing on the Monastery: (7)
As of 2014-11-29 06:43 GMT
Sections?
Information?
Find Nodes?
Leftovers?
    Voting Booth?

    My preferred Perl binaries come from:














    Results (203 votes), past polls