Beefy Boxes and Bandwidth Generously Provided by pair Networks
Welcome to the Monastery
 
PerlMonks  

Re^2: Patience Sorting To Find Longest Increasing Subsequence

by Limbic~Region (Chancellor)
on May 04, 2006 at 12:40 UTC ( #547403=note: print w/ replies, xml ) Need Help??


in reply to Re: Patience Sorting To Find Longest Increasing Subsequence
in thread Patience Sorting To Find Longest Increasing Subsequence

TedPride,
Per our /msg conversation, here is a version of my implementation that uses a binary search:

sub Long_Inc_Sub { my @list = @_; my (@pile, @seq); for my $num (@list) { if (@pile) { if ($num < $pile[-1][-1][VAL]) { my ($beg, $end) = (0, $#pile); while ($beg <= $end) { my $mid = int(($beg + $end) / 2); if ($num < $pile[$mid][-1][VAL]) { $end = $mid - 1; } else { $beg = $mid + 1; } } my $prev = $beg ? $#{$pile[$beg - 1]} : undef; push @{$pile[$beg]}, [$num, $prev]; } else { push @pile, [[$num, $#{$pile[-1]}]]; } } else { push @pile, [[$num, undef]]; } } my ($prev, $len) = ($#{$pile[-1]}, scalar @pile); while ($len--) { $seq[$len] = $pile[$len][$prev][VAL]; $prev = $pile[$len][$prev][PREV]; } return @seq; }
It does not currently handle exact matches since there should not be any duplicates in the list (1..N). I did leave this open as a question to ponder and it should be fairly trivial to adapt if you decide it is safe to do so ;-)

Cheers - L~R


Comment on Re^2: Patience Sorting To Find Longest Increasing Subsequence
Download Code

Log In?
Username:
Password:

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

How do I use this? | Other CB clients
Other Users?
Others surveying the Monastery: (6)
As of 2015-07-04 23:00 GMT
Sections?
Information?
Find Nodes?
Leftovers?
    Voting Booth?

    The top three priorities of my open tasks are (in descending order of likelihood to be worked on) ...









    Results (60 votes), past polls