Longest increasing subsequence: Difference between revisions
Rename Perl 6 -> Raku, alphabetize, minor clean-up
Thundergnat (talk | contribs) (Rename Perl 6 -> Raku, alphabetize, minor clean-up) |
|||
Line 221:
0 4 6 9 13 15
</pre>
=={{header|C sharp}}==
Line 365 ⟶ 297:
}
}</lang>
=={{header|C++}}==
Patience sorting
<lang cpp>#include <iostream>
#include <vector>
#include <tr1/memory>
#include <algorithm>
#include <iterator>
template <typename E>
struct Node {
E value;
std::tr1::shared_ptr<Node<E> > pointer;
};
template <class E>
struct node_ptr_less {
bool operator()(const std::tr1::shared_ptr<Node<E> > &node1,
const std::tr1::shared_ptr<Node<E> > &node2) const {
return node1->value < node2->value;
}
};
template <typename E>
std::vector<E> lis(const std::vector<E> &n) {
typedef std::tr1::shared_ptr<Node<E> > NodePtr;
std::vector<NodePtr> pileTops;
// sort into piles
for (typename std::vector<E>::const_iterator it = n.begin(); it != n.end(); it++) {
NodePtr node(new Node<E>());
node->value = *it;
typename std::vector<NodePtr>::iterator j =
std::lower_bound(pileTops.begin(), pileTops.end(), node, node_ptr_less<E>());
if (j != pileTops.begin())
node->pointer = *(j-1);
if (j != pileTops.end())
*j = node;
else
pileTops.push_back(node);
}
// extract LIS from piles
std::vector<E> result;
for (NodePtr node = pileTops.back(); node != NULL; node = node->pointer)
result.push_back(node->value);
std::reverse(result.begin(), result.end());
return result;
}
int main() {
int arr1[] = {3,2,6,4,5,1};
std::vector<int> vec1(arr1, arr1 + sizeof(arr1)/sizeof(*arr1));
std::vector<int> result1 = lis(vec1);
std::copy(result1.begin(), result1.end(), std::ostream_iterator<int>(std::cout, ", "));
std::cout << std::endl;
int arr2[] = {0, 8, 4, 12, 2, 10, 6, 14, 1, 9, 5, 13, 3, 11, 7, 15};
std::vector<int> vec2(arr2, arr2 + sizeof(arr2)/sizeof(*arr2));
std::vector<int> result2 = lis(vec2);
std::copy(result2.begin(), result2.end(), std::ostream_iterator<int>(std::cout, ", "));
std::cout << std::endl;
return 0;
}</lang>
{{out}}
<pre>2, 4, 5,
0, 2, 6, 9, 11, 15, </pre>
=={{header|Clojure}}==
Line 1,598:
<pre>an L.I.S. of [3 2 6 4 5 1] is [2 4 5]
an 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|Phix}}==
Line 1,999 ⟶ 1,953:
<pre>'(2 4 5)
'(0 2 6 9 11 15)</pre>
=={{header|Raku}}==
(formerly Perl 6)
{{works with|rakudo|2018.03}}
===<!--Perl 6-->Dynamic programming===
Straight-forward implementation of the algorithm described in the video.
<lang perl6>sub lis(@d) {
my @l = [].item xx @d;
@l[0].push: @d[0];
for 1 ..^ @d -> $i {
for ^$i -> $j {
if @d[$j] < @d[$i] && @l[$i] < @l[$j] + 1 {
@l[$i] = [ @l[$j][] ]
}
}
@l[$i].push: @d[$i];
}
return max :by(*.elems), @l;
}
say lis([3,2,6,4,5,1]);
say lis([0,8,4,12,2,10,6,14,1,9,5,13,3,11,7,15]);</lang>
{{out}}
<pre>[2 4 5]
[0 2 6 9 11 15]</pre>
===<!--Perl 6-->Patience sorting===
<lang perl6>sub lis(@deck is copy) {
my @S = [@deck.shift() => Nil].item;
for @deck -> $card {
with first { @S[$_][*-1].key > $card }, ^@S -> $i {
@S[$i].push: $card => @S[$i-1][*-1] // Nil
} else {
@S.push: [ $card => @S[*-1][*-1] // Nil ].item
}
}
reverse map *.key, (
@S[*-1][*-1], *.value ...^ !*.defined
)
}
say lis <3 2 6 4 5 1>;
say lis <0 8 4 12 2 10 6 14 1 9 5 13 3 11 7 15>;</lang>
{{out}}
<pre>[2 4 5]
[0 2 6 9 11 15]</pre>
=={{header|REXX}}==
Line 2,149 ⟶ 2,150:
<pre>[2, 4, 5]
[0, 2, 6, 9, 11, 15]</pre>
=={{header|Rust}}==
Line 2,243 ⟶ 2,245:
sequence(set)(_<_)
sequence(set)(_>_)</lang>
=={{header|Scheme}}==
Patience sorting
| |||