Anonymous user
Longest increasing subsequence: Difference between revisions
→{{header|Perl}}: added perl patience sorting
(added php) |
(→{{header|Perl}}: added perl patience sorting) |
||
Line 358:
=={{header|Perl}}==
===Dynamic programming===
{{trans|Perl 6}}
<lang Perl>sub lis {
Line 383 ⟶ 384:
<pre>2 4 5
0 2 6 9 11 15</pre>
===Patience sorting===
<lang perl>sub lis {
my @pileTops;
# sort into piles
foreach my $x (@_) {
# binary search
my $low = 0, $high = $#pileTops;
while ($low <= $high) {
my $mid = int(($low + $high) / 2);
if ($pileTops[$mid]{val} >= $x) {
$high = $mid - 1;
} else {
$low = $mid + 1;
}
}
my $i = $low;
my $node = {val => $x};
$node->{back} = $pileTops[$i-1] if $i != 0;
if ($i != @pileTops) {
$pileTops[$i] = $node;
} else {
push @pileTops, $node;
}
}
my @result;
for (my $node = $pileTops[-1]; $node; $node = $node->{back}) {
push @result, $node->{val};
}
return reverse @result;
}
foreach my $r ([3, 2, 6, 4, 5, 1],
[0, 8, 4, 12, 2, 10, 6, 14, 1, 9, 5, 13, 3, 11, 7, 15]) {
my @d = @$r;
my @lis = lis(@d);
print "L.I.S. of [@d] is [@lis]\n";
}</lang>
{{out}}
<pre>L.I.S. of [3 2 6 4 5 1] is [2 4 5]
L.I.S. of [0 8 4 12 2 10 6 14 1 9 5 13 3 11 7 15] is [0 2 6 9 11 15]</pre>
=={{header|Perl 6}}==
| |||