Longest increasing subsequence: Difference between revisions
Content added Content deleted
Thundergnat (talk | contribs) (Rename Perl 6 -> Raku, alphabetize, minor clean-up) |
|||
Line 221: | Line 221: | ||
0 4 6 9 13 15 |
0 4 6 9 13 15 |
||
</pre> |
</pre> |
||
=={{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|C sharp}}== |
=={{header|C sharp}}== |
||
Line 365: | Line 297: | ||
} |
} |
||
}</lang> |
}</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}}== |
=={{header|Clojure}}== |
||
Line 1,598: | Line 1,598: | ||
<pre>an L.I.S. of [3 2 6 4 5 1] is [2 4 5] |
<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> |
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|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|Phix}}== |
=={{header|Phix}}== |
||
Line 1,999: | Line 1,953: | ||
<pre>'(2 4 5) |
<pre>'(2 4 5) |
||
'(0 2 6 9 11 15)</pre> |
'(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}}== |
=={{header|REXX}}== |
||
Line 2,149: | Line 2,150: | ||
<pre>[2, 4, 5] |
<pre>[2, 4, 5] |
||
[0, 2, 6, 9, 11, 15]</pre> |
[0, 2, 6, 9, 11, 15]</pre> |
||
=={{header|Rust}}== |
=={{header|Rust}}== |
||
Line 2,243: | Line 2,245: | ||
sequence(set)(_<_) |
sequence(set)(_<_) |
||
sequence(set)(_>_)</lang> |
sequence(set)(_>_)</lang> |
||
=={{header|Scheme}}== |
=={{header|Scheme}}== |
||
Patience sorting |
Patience sorting |