Longest increasing subsequence: Difference between revisions
Content added Content deleted
(+ third D version) |
m (→Patience sorting: s/@d/@deck/ # being a bit more explicit) |
||
Line 357: | Line 357: | ||
===Patience sorting=== |
===Patience sorting=== |
||
<lang Perl 6>sub patience(@ |
<lang Perl 6>sub patience(@deck is copy) { |
||
my @S = [@ |
my @S = [@deck.shift() => Mu].item; |
||
for @ |
for @deck -> $card { |
||
if defined my $i = first { @S[$_][*-1].key > $card }, ^@S { |
if defined my $i = first { @S[$_][*-1].key > $card }, ^@S { |
||
@S[$i].push: $card => @S[$i-1][*-1] // Mu |
@S[$i].push: $card => @S[$i-1][*-1] // Mu |
||
Line 368: | Line 368: | ||
return @S |
return @S |
||
} |
} |
||
sub lis(@S) { |
sub lis(@S) { |
||
reverse map *.key, ( |
reverse map *.key, ( |
||
@S[*-1][*-1], *.value ...^ !*.defined |
|||
) |
) |
||
} |
} |
||
say lis patience(<3 2 6 4 5 1>); |
say lis patience(<3 2 6 4 5 1>); |
||
say lis patience(<0 8 4 12 2 10 6 14 1 9 5 13 3 11 7 15>); |
say lis patience(<0 8 4 12 2 10 6 14 1 9 5 13 3 11 7 15>);</lang> |
||
</lang> |
|||
{{out}} |
{{out}} |
||
<pre>2 4 5 |
<pre>2 4 5 |