Re: 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
}
[download]

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

Replies are listed 'Best First'.
Re^2: Puzzle: Longest Increasing Sequence by jdalbec (Deacon) on Apr 16, 2006 at 21:55 UTC
Actually, O(nlog(n)((sqrt(5)-1)/2)) is strictly less than O(nlog(n)). The difference probably won't be noticeable for reasonable values of n, though, since log(n) grows so slowly anyway.	[reply]
Re^3: Puzzle: Longest Increasing Sequence by ikegami (Patriarch) on Apr 16, 2006 at 22:30 UTC
oh yeah. I thought it was , not *	[reply]
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++; }` [download] 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 [download]	[reply] [d/l] [select]
Re^3: Puzzle: Longest Increasing Sequence by ikegami (Patriarch) on Apr 17, 2006 at 16:41 UTC
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".	[reply] [d/l]
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. Read more... (7 kB) 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	[reply] [d/l]


XP is just a number
	PerlMonks