Longest increasing subsequence: Difference between revisions
Added Easylang
(Added Easylang) |
|||
(29 intermediate revisions by 20 users not shown) | |||
Line 6:
Note that a list may have more than one subsequence that is of the maximum length.
{{Template:Strings}}
;Ref:
Line 11 ⟶ 14:
# An efficient solution can be based on [[wp:Patience sorting|Patience sorting]].
<br><br>
=={{header|11l}}==
{{trans|Python}}
<syntaxhighlight lang="11l">F longest_increasing_subsequence(x)
V n = x.len
V P = [0] * n
V M = [0] * (n + 1)
V l = 0
L(i) 0 .< n
V lo = 1
V hi = l
L lo <= hi
V mid = (lo + hi) I/ 2
I (x[M[mid]] < x[i])
lo = mid + 1
E
hi = mid - 1
V newl = lo
P[i] = M[newl - 1]
M[newl] = i
I (newl > l)
l = newl
[Int] s
V k = M[l]
L(i) (l - 1 .. 0).step(-1)
s.append(x[k])
k = P[k]
R reversed(s)
L(d) [[3, 2, 6, 4, 5, 1], [0, 8, 4, 12, 2, 10, 6, 14, 1, 9, 5, 13, 3, 11, 7, 15]]
print(‘a L.I.S. of #. is #.’.format(d, longest_increasing_subsequence(d)))</syntaxhighlight>
{{out}}
<pre>
a L.I.S. of [3, 2, 6, 4, 5, 1] is [2, 4, 5]
a 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|360 Assembly}}==
{{trans|VBScript}}
<
LNGINSQ CSECT
USING LNGINSQ,R13 base register
Line 134 ⟶ 177:
XDEC DS CL12 temp for xdeco
YREGS
END LNGINSQ</
{{out}}
<pre>
Line 142 ⟶ 185:
> 0 2 6 9 11 15
</pre>
=={{header|AppleScript}}==
{{Trans|Phix}} … modified to return ''multiple'' co-longest sequences where found. It's not clear how equal values should be treated. Here the behaviour happens to be as in the demo code at the end.
<syntaxhighlight lang="applescript">on longestIncreasingSubsequences(aList)
script o
property inputList : aList
property m : {} -- End indices of identified subsequences.
property p : {} -- 'Predecessor' indices for each point in each subsequence.
property subsequence : {} -- Reconstructed longest sequence.
end script
-- Set m and p to lists of the same length as the input. Their initial contents don't matter!
copy aList to o's m
copy aList to o's p
set bestLength to 0
repeat with i from 1 to (count o's inputList)
-- Comments adapted from those in the Wikipedia article — as far as they can be understood!
-- Binary search for the largest possible 'lo' ≤ bestLength such that inputList[m[lo]] ≤ inputList[i].
set lo to 1
set hi to bestLength
repeat until (lo > hi)
set mid to (lo + hi + 1) div 2
if (item (item mid of o's m) of o's inputList < item i of o's inputList) then
set lo to mid + 1
else
set hi to mid - 1
end if
end repeat
-- After searching, lo is 1 greater than the length of the longest prefix of inputList[i].
-- The predecessor of inputList[i] is the last index of the subsequence of length lo - 1.
if (lo > 1) then set item i of o's p to item (lo - 1) of o's m
set item lo of o's m to i
-- If we found a subsequence longer than or the same length as any we've found yet,
-- update bestLength and store the end index associated with it.
if (lo > bestLength) then
set bestLength to lo
set bestEndIndices to {item bestLength of o's m}
else if (lo = bestLength) then
set end of bestEndIndices to item bestLength of o's m
end if
end repeat
-- Reconstruct the longest increasing subsequence(s).
set output to {}
if (bestLength > 0) then
repeat with k in bestEndIndices
set o's subsequence to {}
repeat bestLength times
set beginning of o's subsequence to item k of o's inputList
set k to item k of o's p
end repeat
set end of output to o's subsequence
end repeat
end if
return output
end longestIncreasingSubsequences
-- Task code and other tests:
local tests, output, input
set tests to {{3, 2, 6, 4, 5, 1}, {0, 8, 4, 12, 2, 10, 6, 14, 1, 9, 5, 13, 3, 11, 7, 15}, ¬
{9, 10, 11, 3, 8, 9, 6, 7, 4, 5}, {4, 5, 5, 6}, {5, 5}}
set output to {}
repeat with input in tests
set end of output to {finds:longestIncreasingSubsequences(input's contents)}
end repeat
return output</syntaxhighlight>
{{output}}
<syntaxhighlight lang="applescript">{{finds:{{2, 4, 5}}}, {finds:{{0, 2, 6, 9, 11, 15}}}, {finds:{{9, 10, 11}, {3, 8, 9}, {3, 6, 7}, {3, 4, 5}}}, {finds:{{4, 5, 6}}}, {finds:{{5}, {5}}}}</syntaxhighlight>
=={{header|Arturo}}==
<syntaxhighlight lang="rebol">lis: function [d][
l: new [[]]
loop d 'num [
x: []
loop l 'seq [
if positive? size seq [
if and? num > last seq
(size seq) > size x ->
x: seq
]
]
'l ++ @[x ++ @[num]]
]
result: []
loop l 'x [
if (size x) > size result ->
result: x
]
return result
]
loop [
[3 2 6 4 5 1]
[0 8 4 12 2 10 6 14 1 9 5 13 3 11 7 15]
] 'seq [
print ["LIS of" seq "=>" lis seq]
]</syntaxhighlight>
{{out}}
<pre>LIS of [3 2 6 4 5 1] => [3 4 5]
LIS of [0 8 4 12 2 10 6 14 1 9 5 13 3 11 7 15] => [0 4 6 9 13 15]</pre>
=={{header|AutoHotkey}}==
<
for k, v in Lists {
Line 165 ⟶ 313:
}
return, D
}</
'''Output:'''
<pre>3, 4, 5
Line 172 ⟶ 320:
=={{header|C}}==
Using an array that doubles as linked list (more like reversed trees really). O(n) memory and O(n<sup>2</sup>) runtime.
<
#include <stdlib.h>
Line 215 ⟶ 363:
lis(y, sizeof(y) / sizeof(int));
return 0;
}</
{{out}}
<pre>
Line 221 ⟶ 369:
0 4 6 9 13 15
</pre>
=={{header|C sharp}}==
===Recursive===
{{works with|C sharp|6}}
<
using System.Collections;
using System.Collections.Generic;
Line 340 ⟶ 420:
IEnumerator IEnumerable.GetEnumerator() => GetEnumerator();
}
}</
===Patience sorting===
{{works with|C sharp|7}}
<
{
public static T[] Find<T>(IList<T> values, IComparer<T> comparer = null) {
Line 364 ⟶ 444:
return result;
}
public static void Main() {
Console.WriteLine(string.Join(",", LIS.Find(new [] { 3, 2, 6, 4, 5, 1 })));
Console.WriteLine(string.Join(",", LIS.Find(new [] { 0, 8, 4, 12, 2, 10, 6, 14, 1, 9, 5, 13, 3, 11, 7, 15 })));
}
}</syntaxhighlight>
{{out}}
<pre>
2, 4, 5
0, 2, 6, 9, 11, 15</pre>
=={{header|C++}}==
Patience sorting
=== C++11 ===
<syntaxhighlight lang="cpp">#include <vector>
#include <list>
#include <algorithm>
#include <iostream>
template <typename T>
struct Node {
T value;
Node* prev_node;
};
template <typename Container>
Container lis(const Container& values) {
using E = typename Container::value_type;
using NodePtr = Node<E>*;
using ConstNodePtr = const NodePtr;
std::vector<NodePtr> pileTops;
std::vector<Node<E>> nodes(values.size());
// sort into piles
auto cur_node = std::begin(nodes);
for (auto cur_value = std::begin(values); cur_value != std::end(values); ++cur_value, ++cur_node)
{
auto node = &*cur_node;
node->value = *cur_value;
// lower_bound returns the first element that is not less than 'node->value'
auto lb = std::lower_bound(pileTops.begin(), pileTops.end(), node,
[](ConstNodePtr& node1, ConstNodePtr& node2) -> bool { return node1->value < node2->value; });
if (lb != pileTops.begin())
node->prev_node = *std::prev(lb);
if (lb == pileTops.end())
pileTops.push_back(node);
else
*lb = node;
}
// extract LIS from piles
// note that LIS length is equal to the number of piles
Container result(pileTops.size());
auto r = std::rbegin(result);
for (NodePtr node = pileTops.back(); node != nullptr; node = node->prev_node, ++r)
*r = node->value;
return result;
}
template <typename Container>
void show_lis(const Container& values)
{
auto&& result = lis(values);
for (auto& r : result) {
std::cout << r << ' ';
}
std::cout << std::endl;
}
int main()
{
show_lis(std::list<int> { 3, 2, 6, 4, 5, 1 });
show_lis(std::vector<int> { 0, 8, 4, 12, 2, 10, 6, 14, 1, 9, 5, 13, 3, 11, 7, 15 });
}</syntaxhighlight>
=== C++98 ===
<syntaxhighlight lang="cpp">#include <vector>
#include <list>
#include <algorithm>
#include <iostream>
template <typename T>
struct Node {
T value;
Node* prev_node;
};
template <typename T>
bool compare (const T& node1, const T& node2)
{
return node1->value < node2->value;
}
template <typename Container>
Container lis(const Container& values) {
typedef typename Container::value_type E;
typedef typename Container::const_iterator ValueConstIter;
typedef typename Container::iterator ValueIter;
typedef Node<E>* NodePtr;
typedef const NodePtr ConstNodePtr;
typedef std::vector<Node<E> > NodeVector;
typedef std::vector<NodePtr> NodePtrVector;
typedef typename NodeVector::iterator NodeVectorIter;
typedef typename NodePtrVector::iterator NodePtrVectorIter;
std::vector<NodePtr> pileTops;
std::vector<Node<E> > nodes(values.size());
// sort into piles
NodeVectorIter cur_node = nodes.begin();
for (ValueConstIter cur_value = values.begin(); cur_value != values.end(); ++cur_value, ++cur_node)
{
NodePtr node = &*cur_node;
node->value = *cur_value;
// lower_bound returns the first element that is not less than 'node->value'
NodePtrVectorIter lb = std::lower_bound(pileTops.begin(), pileTops.end(), node, compare<NodePtr>);
if (lb != pileTops.begin())
node->prev_node = *(lb - 1);
if (lb == pileTops.end())
pileTops.push_back(node);
else
*lb = node;
}
// extract LIS from piles
// note that LIS length is equal to the number of piles
Container result(pileTops.size());
std::reverse_iterator<ValueIter> r = std::reverse_iterator<ValueIter>(result.rbegin());
for (NodePtr node = pileTops.back(); node; node = node->prev_node, ++r)
*r = node->value;
return result;
}
template <typename Container>
void show_lis(const Container& values)
{
const Container& result = lis(values);
for (typename Container::const_iterator it = result.begin(); it != result.end(); ++it) {
std::cout << *it << ' ';
}
std::cout << std::endl;
}
int main()
{
const int arr1[] = { 3, 2, 6, 4, 5, 1 };
const int arr2[] = { 0, 8, 4, 12, 2, 10, 6, 14, 1, 9, 5, 13, 3, 11, 7, 15 };
std::vector<int> vec1(arr1, arr1 + sizeof(arr1) / sizeof(arr1[0]));
std::vector<int> vec2(arr2, arr2 + sizeof(arr2) / sizeof(arr2[0]));
show_lis(vec1);
show_lis(vec2);
}</syntaxhighlight>
{{out}}
<pre>2 4 5
0 2 6 9 11 15 </pre>
=={{header|Clojure}}==
Line 371 ⟶ 617:
The combination is done using ''cons'', so what gets put on a pile is a list -- a descending subsequence.
<
(let [[les gts] (->> piles (split-with #(<= (ffirst %) card)))
newelem (cons card (->> les last first))
Line 382 ⟶ 628:
(println (a-longest [3 2 6 4 5 1]))
(println (a-longest [0 8 4 12 2 10 6 14 1 9 5 13 3 11 7 15]))</
{{out}}
<syntaxhighlight lang="text">(2 4 5)
(0 2 6 9 11 15)</
=={{header|Common Lisp}}==
===Common Lisp: Using the method in the video===
Slower and more memory usage compared to the patience sort method.
<
(let ((subseqs nil))
(dolist (item list)
Line 409 ⟶ 655:
(dolist (l (list (list 3 2 6 4 5 1)
(list 0 8 4 12 2 10 6 14 1 9 5 13 3 11 7 15)))
(format t "~A~%" (longest-increasing-subseq l))))</
{{out}}
<pre>(2 4 5)
Line 415 ⟶ 661:
===Common Lisp: Using the Patience Sort approach===
This is 5 times faster and and uses a third of the memory compared to the approach in the video.
<
(let ((piles nil))
(dolist (item input-list)
Line 437 ⟶ 683:
(dolist (l (list (list 3 2 6 4 5 1)
(list 0 8 4 12 2 10 6 14 1 9 5 13 3 11 7 15)))
(format t "~A~%" (lis-patience-sort l)))</
{{out}}
<pre>(2 4 5)
Line 443 ⟶ 689:
===Common Lisp: Using the Patience Sort approach (alternative)===
This is a different version of the code above.
<
(multiple-value-bind
(i prev)
Line 462 ⟶ 708:
(dolist (l (list (list 3 2 6 4 5 1)
(list 0 8 4 12 2 10 6 14 1 9 5 13 3 11 7 15)))
(format t "~A~%" (longest-inc-seq l)))</
{{out}}
<pre>(2 4 5)
Line 471 ⟶ 717:
{{trans|Haskell}}
Uses the second powerSet function from the Power Set Task.
<
T[] lis(T)(T[] items) pure nothrow {
Line 485 ⟶ 731:
[3, 2, 6, 4, 5, 1].lis.writeln;
[0, 8, 4, 12, 2, 10, 6, 14, 1, 9, 5, 13, 3, 11, 7, 15].lis.writeln;
}</
{{out}}
<pre>[2, 4, 5]
Line 493 ⟶ 739:
{{trans|Python}}
From the second Python entry, using the Patience sorting method.
<
/// Return one of the Longest Increasing Subsequence of
Line 530 ⟶ 776:
[0,8,4,12,2,10,6,14,1,9,5,13,3,11,7,15]])
d.lis.writeln;
}</
The output is the same.
Line 536 ⟶ 782:
{{trans|Java}}
With some more optimizations.
<
T[] lis(T)(in T[] items) pure nothrow
Line 585 ⟶ 831:
[0,8,4,12,2,10,6,14,1,9,5,13,3,11,7,15]])
d.writeln;
}</
The output is the same.
=={{header|Déjà Vu}}==
{{trans|Python}}
<
if = :nil dup:
false drop
Line 615 ⟶ 861:
!. lis [ 3 2 6 4 5 1 ]
!. lis [ 0 8 4 12 2 10 6 14 1 9 5 13 3 11 7 15 ]
</syntaxhighlight>
{{out}}
<pre>[ 2 4 5 ]
[ 0 2 6 9 11 15 ]</pre>
=={{header|EasyLang}}==
{{trans|Ring}}
<syntaxhighlight>
func[] lis x[] .
n = len x[]
len p[] n
len m[] n
for i to n
lo = 1
hi = lng
while lo <= hi
mid = (lo + hi) div 2
if x[m[mid]] < x[i]
lo = mid + 1
else
hi = mid - 1
.
.
if lo > 1
p[i] = m[lo - 1]
.
m[lo] = i
if lo > lng
lng = lo
.
.
len res[] lng
if lng > 0
k = m[lng]
for i = lng downto 1
res[i] = x[k]
k = p[k]
.
.
return res[]
.
tests[][] = [ [ 3 2 6 4 5 1 ] [ 0 8 4 12 2 10 6 14 1 9 5 13 3 11 7 15 ] ]
for x to len tests[][]
print lis tests[x][]
.
</syntaxhighlight>
{{out}}
<pre>
[ 2 4 5 ]
[ 0 2 6 9 11 15 ]
</pre>
=={{header|Elixir}}==
Line 625 ⟶ 918:
===Naive version===
very slow
<
# Naive implementation
def lis(l) do
Line 643 ⟶ 936:
IO.inspect Longest_increasing_subsequence.lis([3,2,6,4,5,1])
IO.inspect Longest_increasing_subsequence.lis([0,8,4,12,2,10,6,14,1,9,5,13,3,11,7,15])</
{{out}}
Line 652 ⟶ 945:
===Patience sort version===
<
# Patience sort implementation
def patience_lis(l), do: patience_lis(l, [])
Line 679 ⟶ 972:
IO.inspect Longest_increasing_subsequence.patience_lis([3,2,6,4,5,1])
IO.inspect Longest_increasing_subsequence.patience_lis([0,8,4,12,2,10,6,14,1,9,5,13,3,11,7,15])</
{{out}}
Line 688 ⟶ 981:
=={{header|Erlang}}==
- Naive version{{trans|Haskell}}
- Memoization
- Patience sort version
- Patience sort version2
Function ''combos'' is copied from [http://panduwana.wordpress.com/2010/04/21/combination-in-erlang/ panduwana blog].
Line 696 ⟶ 994:
Function ''maxBy'' is copied from [http://stackoverflow.com/a/4762387/4162959 Hynek -Pichi- Vychodil's answer].
Function ''memo'' and ''patience2'' by [https://www.linkedin.com/in/find-roman/ Roman Rabinovich].
<syntaxhighlight lang="erlang">
-module(longest_increasing_subsequence).
-export([test_naive/0, test_memo/0, test_patience/0, test_patience2/0, test_compare/1]).
% **************************************************
% Interface to test the implementation
% **************************************************
test_compare(N) when N =< 20 ->
Funs = [
{"Naive", fun lis/1},
{"Memo", fun memo/1},
{"Patience", fun patience_lis/1},
{"Patience2", fun patience2/1}
],
do_compare(Funs, N);
test_compare(N) when N =< 500 ->
Funs = [
{"Memo", fun memo/1},
{"Patience", fun patience_lis/1},
{"Patience2", fun patience2/1}
],
do_compare(Funs, N);
test_compare(N) ->
Funs = [
{"Patience", fun patience_lis/1},
{"Patience2", fun patience2/1}
],
do_compare(Funs, N).
do_compare(Funs, N) ->
List = [rand:uniform(1000) || _ <- lists:seq(1,N)],
Results = [{Name, timer:tc(fun() -> F(List) end)} || {Name,F} <- Funs],
Times = [{Name, Time} || {Name, {Time, _Result}} <- Results],
io:format("Result Times: ~p~n", [Times]).
test_naive() ->
test_gen(fun lis/1).
test_memo() ->
test_gen(fun memo/1).
test_patience() ->
test_gen(fun patience_lis/1).
test_patience2() ->
test_gen(fun patience2/1).
test_gen(F) ->
Line 731 ⟶ 1,065:
SS == lists:sort(SS)]
).
% **************************************************
% Copied from http://stackoverflow.com/a/4762387/4162959
% **************************************************
maxBy(F, L) ->
element(
2,
lists:max([ {F(X), X} || X <- L])
).
% **************************************************
% Copied from https://panduwana.wordpress.com/2010/04/21/combination-in-erlang/
% **************************************************
combos(L) ->
lists:foldl(
fun(K, Acc) -> Acc++(combos(K, L)) end,
[[]],
lists:seq(1, length(L))
).
combos(1, L) ->
[[X] || X <- L];
combos(K, L) when K == length(L) ->
[L];
combos(K, [H|T]) ->
[[H | Subcombos]
|| Subcombos <- combos(K-1, T)]
++ (combos(K, T)).
% **************************************************
% **************************************************
% Memoization implementation, Roman Rabinovich
% **************************************************
memo(S) ->
put(test, #{}),
memo(S, -1).
memo([], _) -> [];
memo([H | Tail] = S, Min) when H > Min ->
case maps:get({S,Min}, get(test), undefined) of
undefined ->
L1 = [H | memo(Tail, H)],
L2 = memo(Tail, Min),
case length(L1) >= length(L2) of
true ->
Map = get(test),
put(test, Map#{{S, Min} => L1}),
L1;
_ ->
Map = get(test),
put(test, Map#{{S, Min} => L2}),
L2
end;
X -> X
end;
memo([_|Tail], Min) ->
memo(Tail, Min).
% **************************************************
Line 778 ⟶ 1,172:
% **************************************************
% Patience2 by Roman Rabinovich, improved performance over above
% **************************************************
patience2([]) -> [];
patience2([H|L]) ->
Piles = [[{H, undefined}]],
patience2(L, Piles, []).
get_seq(lists:reverse(Piles));
patience2([H|T], [[{PE,_}|_Rest] = Pile| Piles], PrevPiles) when H =< PE ->
case PrevPiles of
[] -> patience2(T, [[{H, undefined}|Pile]|Piles], []);
[[{K,_}|_]|_] -> patience2(T, lists:reverse(PrevPiles) ++ [[{H, K}|Pile]|Piles], [])
end;
patience2([H|_T] = L, [[{PE,_}|_Rest] = Pile| Piles], PrevPiles) when H > PE ->
patience2(L, Piles, [Pile|PrevPiles]);
patience2([H|T], [], [[{K,_}|_]|_]=PrevPiles) ->
patience2(T, lists:reverse([[{H,K}]|PrevPiles]), []).
get_seq([[{K,P}|_]|Rest]) ->
get_seq(P, Rest, [K]).
get_seq(K, [Pile|Rest], Seq) ->
case
{K, P} -> get_seq(P, Rest, [K|Seq])
end.
% **************************************************
</syntaxhighlight>
Output naive:
<pre>
[3,4,5]
[0,4,6,9,13,15]
</pre>
Output memoization:
<pre>
[3,4,5]
Line 823 ⟶ 1,225:
[0,2,6,9,11,15]
</pre>
Output patience2:
<pre>
[2,4,5]
[0,2,6,9,11,15]
</pre>
=={{header|FreeBASIC}}==
<syntaxhighlight lang="vb">Sub Lis(arr() As Integer)
Dim As Integer lb = Lbound(arr), ub = Ubound(arr)
Dim As Integer i, lo, hi, mitad, newl, l = 0
Dim As Integer p(ub), m(ub)
For i = lb To ub
lo = 1
hi = l
Do While lo <= hi
mitad = Int((lo+hi)/2)
If arr(m(mitad)) < arr(i) Then
lo = mitad + 1
Else
hi = mitad - 1
End If
Loop
newl = lo
p(i) = m(newl-1)
m(newl) = i
If newL > l Then l = newl
Next i
Dim As Integer res(l)
Dim As Integer k = m(l)
For i = l-1 To 0 Step - 1
res(i) = arr(k)
k = p(k)
Next i
For i = Lbound(res) To Ubound(res)-1
Print res(i); " ";
Next i
End Sub
Dim As Integer arrA(5) => {3,2,6,4,5,1}
Lis(arrA())
Print
Dim As Integer arrB(15) => {0,8,4,12,2,10,6,14,1,9,5,13,3,11,7,15}
Lis(arrB())
Sleep</syntaxhighlight>
{{out}}
<pre>2 4 5
0 2 6 9 11 15</pre>
=={{header|Go}}==
Patience sorting
<
import (
Line 868 ⟶ 1,322:
fmt.Printf("an L.I.S. of %v is %v\n", d, lis(d))
}
}</
{{out}}
Line 876 ⟶ 1,330:
=={{header|Haskell}}==
===Naive implementation===
<
import Data.List ( maximumBy, subsequences )
import Data.List.Ordered ( isSorted, nub )
Line 887 ⟶ 1,341:
print $ lis [3,2,6,4,5,1]
print $ lis [0,8,4,12,2,10,6,14,1,9,5,13,3,11,7,15]
print $ lis [1,1,1,1]</
{{out}}
Line 895 ⟶ 1,349:
===Patience sorting===
<
module Main (main, lis) where
Line 946 ⟶ 1,400:
print $ lis [3, 2, 6, 4, 5, 1]
print $ lis [0, 8, 4, 12, 2, 10, 6, 14, 1, 9, 5, 13, 3, 11, 7, 15]
print $ lis [1, 1, 1, 1]</
{{out}}
Line 957 ⟶ 1,411:
The following works in both languages:
<
every writes((!lis(A)||" ") | "\n")
end
Line 967 ⟶ 1,421:
else p[-1] := (p[-2] < v)
return r
end</
Sample runs:
Line 982 ⟶ 1,436:
These examples are simple enough for brute force to be reasonable:
<
longestinc=: ] #~ [: (#~ ([: (= >./) +/"1)) #:@I.@increasing</
In other words: consider all 2^n bitmasks of length n, and select those which strictly select increasing sequences. Find the length of the longest of these and use the masks of that length to select from the original sequence.
Line 989 ⟶ 1,443:
Example use:
<syntaxhighlight lang="j">
longestinc 3,2,6,4,5,1
2 4 5
Line 997 ⟶ 1,451:
0 2 6 9 13 15
0 4 6 9 11 15
0 4 6 9 13 15</
=={{header|Java}}==
A solution based on patience sorting, except that it is not necessary to keep the whole pile, only the top (in solitaire, bottom) of the pile, along with pointers from each "card" to the top of its "previous" pile.
<
public class LIS {
Line 1,040 ⟶ 1,494:
System.out.printf("an L.I.S. of %s is %s\n", d, lis(d));
}
}</
{{out}}
Line 1,047 ⟶ 1,501:
=={{header|JavaScript}}==
<
if (input.length === 0) {
return [];
Line 1,080 ⟶ 1,534:
console.log(getLongestIncreasingSubsequence([0, 7, 8, 4, 12, 2, 10, 6, 14, 1, 9, 5, 13, 3, 11, 7, 15]));
console.log(getLongestIncreasingSubsequence([3, 2, 6, 4, 5, 1]));
</syntaxhighlight>
{{out}}
<pre>
[ 0, 2, 6, 9, 11, 15 ]
[ 2, 4, 5 ]
</pre>
===Patience sorting===
<syntaxhighlight lang="javascript">function getLIS(input) {
if (input.length === 0) {
return 0;
}
const piles = [input[0]];
for (let i = 1; i < input.length; i++) {
const leftPileIdx = binarySearch(piles, input[i]);
if (leftPileIdx !== -1) {
piles[leftPileIdx] = input[i];
} else {
piles.push(input[i]);
}
}
return piles.length;
}
function binarySearch(arr, target) {
let lo = 0;
let hi = arr.length - 1;
while (lo <= hi) {
const mid = lo + Math.floor((hi - lo) / 2);
if (arr[mid] >= target) {
hi = mid - 1;
} else {
lo = mid + 1;
}
}
return lo < arr.length ? lo : -1;
}
console.log(getLongestIncreasingSubsequence([0, 7, 8, 4, 12, 2, 10, 6, 14, 1, 9, 5, 13, 3, 11, 7, 15]));
console.log(getLongestIncreasingSubsequence([3, 2, 6, 4, 5, 1]));
</syntaxhighlight>
{{out}}
Line 1,095 ⟶ 1,597:
Recent versions of jq have functions that obviate the need for the two generic functions defined in this subsection.
<
def _until:
if cond then . else (update | _until) end;
Line 1,111 ⟶ 1,613:
else .[0] = $mid + 1
end )
| .[0];</
'''lis:'''
<
# Helper function:
Line 1,130 ⟶ 1,632:
)
| .[length - 1]
| reverse( recurse(.back) | .val ) ; </
'''Examples:'''
<
[0,8,4,12,2,10,6,14,1,9,5,13,3,11,7,15]
) | lis</
{{out}}
<
[2,4,5]
[0,2,6,9,11,15]
</syntaxhighlight>
=={{header|Julia}}==
{{works with|Julia|0.6}}
<
function lis(arr::Vector)
if length(arr) == 0 return copy(arr) end
Line 1,165 ⟶ 1,667:
@show lis([3, 2, 6, 4, 5, 1])
@show lis([0, 8, 4, 12, 2, 10, 6, 14, 1, 9, 5, 13, 3, 11, 7, 15])</
{{out}}
Line 1,173 ⟶ 1,675:
=={{header|Kotlin}}==
Uses the algorithm in the Wikipedia L.I.S. article:
<
fun longestIncreasingSubsequence(x: IntArray): IntArray =
Line 1,213 ⟶ 1,715:
)
lists.forEach { println(longestIncreasingSubsequence(it).asList()) }
}</
{{out}}
Line 1,222 ⟶ 1,724:
=={{header|Lua}}==
<
local piles = { { {table.remove(seq, 1), nil} } }
while #seq>0 do
Line 1,248 ⟶ 1,750:
buildLIS({3,2,6,4,5,1})
buildLIS({0,8,4,12,2,10,6,14,1,9,5,13,3,11,7,15})
</syntaxhighlight>
{{out}}
Line 1,259 ⟶ 1,761:
stack:=stackitem(L(i)), ! stack(L(j)) returns a refence to a new stack object, with the first item on L(i) (which is a reference to stack object) and merge using ! the copy of L(j) stack.
<syntaxhighlight lang="m2000 interpreter">
Module LIS_example {
Function LIS {
Line 1,297 ⟶ 1,799:
}
LIS_example
</syntaxhighlight>
===Using arrays in an array===
<syntaxhighlight lang="m2000 interpreter">
Module LIS_example {
Function LIS {
Line 1,340 ⟶ 1,842:
}
LIS_example
</syntaxhighlight>
{{out}}
Line 1,350 ⟶ 1,852:
</pre >
=={{header|
<syntaxhighlight lang="maple"># dynamic programming:
LIS := proc(L)
local i, j;
local index := 1;
local output := Array(1..numelems(L), i -> Array(1..0));
for i from 1 to numelems(L) do
for j from 1 to i - 1 do
if (L[j] < L[i]) and (upperbound(output[j]) > upperbound(output[i])) then
output[i] := copy(output[j]);
end if;
end do;
# append current value
output[i] ,= L[i];
end do;
#output longest subsequence using loop
for i from 2 to numelems(L) do
if (upperbound(output[i]) > upperbound(output[index])) then
index := i;
end if;
end do;
return output[index];
end proc:</syntaxhighlight>
Alternatively, output the longest subsequence using built-in command max:
<syntaxhighlight lang="maple">i := max[index](map(numelems,output));
output[i];</syntaxhighlight>
<syntaxhighlight lang="maple">L := [3, 2, 6, 4, 5, 1];
M := [0, 8, 4, 12, 2, 10, 6, 14, 1, 9, 5, 13, 3, 11, 7, 15];
LIS(L);
LIS(M);</syntaxhighlight>
{{out}}
<pre>
[3 4 5]
[0 4 6 9 13 15]
</pre>
=={{header|Mathematica}}/{{header|Wolfram Language}}==
Although undocumented, Mathematica has the function LongestAscendingSequence which exactly does what the Task asks for:
<
{{out}}
<pre>{{2,4,5},{0,2,6,9,11,15}}</pre>
=={{header|
{{trans|Python}}
<
var l:
for i in 0 ..
var x:
for j in 0 ..
if l[j][l[j].high] < d[i] and l[j].len > x.len:
x = l[j]
l.add x & @[d[i]]
for x in l:
if x.len > result.len:
Line 1,372 ⟶ 1,915:
for d in [@[3,2,6,4,5,1], @[0, 8, 4, 12, 2, 10, 6, 14, 1, 9, 5, 13, 3, 11, 7, 15]]:
echo "
{{out}}
<pre>
=={{header|Objective-C}}==
Patience sorting
<
@interface Node : NSObject {
Line 1,431 ⟶ 1,974:
}
return 0;
}</
{{out}}
<pre>an L.I.S. of (
Line 1,473 ⟶ 2,016:
=={{header|OCaml}}==
===Naïve implementation===
<
then x
else acc) [] l
Line 1,495 ⟶ 2,038:
in
List.map (fun x -> print_endline (String.concat " " (List.map string_of_int
(lis x)))) sequences</
{{out}}
<pre>
Line 1,503 ⟶ 2,046:
===Patience sorting===
<
let pile_tops = Array.make (List.length list) [] in
let bsearch_piles x len =
Line 1,524 ⟶ 2,067:
in
let len = List.fold_left f 0 list in
List.rev pile_tops.(len-1)</
Usage:
<pre># lis compare [3; 2; 6; 4; 5; 1];;
Line 1,530 ⟶ 2,073:
# lis compare [0; 8; 4; 12; 2; 10; 6; 14; 1; 9; 5; 13; 3; 11; 7; 15];;
- : int list = [0; 2; 6; 9; 11; 15]</pre>
=={{header|Pascal}}==
{{works with|FPC}}
O(NLogN) version.
<syntaxhighlight lang="pascal">
program LisDemo;
{$mode objfpc}{$h+}
uses
SysUtils;
function Lis(const A: array of Integer): specialize TArray<Integer>;
var
TailIndex: array of Integer;
function CeilIndex(Value, R: Integer): Integer;
var
L, M: Integer;
begin
L := 0;
while L < R do begin
{$PUSH}{$Q-}{$R-}M := (L + R) shr 1;{$POP}
if A[TailIndex[M]] < Value then L := M + 1
else R := M;
end;
Result := R;
end;
var
I, J, Len: Integer;
Parents: array of Integer;
begin
Result := nil;
if Length(A) = 0 then exit;
SetLength(TailIndex, Length(A));
SetLength(Parents, Length(A));
Len := 1;
for I := 1 to High(A) do
if A[I] < A[TailIndex[0]] then
TailIndex[0] := I
else
if A[TailIndex[Len-1]] < A[I] then begin
Parents[I] := TailIndex[Len - 1];
TailIndex[Len] := I;
Inc(Len);
end else begin
J := CeilIndex(A[I], Len - 1);
Parents[I] := TailIndex[J - 1];
TailIndex[J] := I;
end;
if Len < 2 then exit([A[0]]);
SetLength(Result, Len);
J := TailIndex[Len - 1];
for I := Len - 1 downto 0 do begin
Result[I] := A[J];
J := Parents[J];
end;
end;
procedure PrintArray(const A: array of Integer);
var
I: SizeInt;
begin
Write('[');
for I := 0 to High(A) - 1 do
Write(A[I], ', ');
WriteLn(A[High(A)], ']');
end;
begin
PrintArray(Lis([3, 2, 6, 4, 5, 1]));
PrintArray(Lis([0, 8, 4, 12, 2, 10, 6, 14, 1, 9, 5, 13, 3, 11, 7, 15]));
PrintArray(Lis([1, 1, 1, 1, 1, 0]));
end.
</syntaxhighlight>
{{out}}
<pre>
[2, 4, 5]
[0, 2, 6, 9, 11, 15]
[1]
</pre>
=={{header|Perl}}==
===Dynamic programming===
{{trans|
<
sub lis {
Line 1,555 ⟶ 2,176:
print join ' ', lis 3, 2, 6, 4, 5, 1;
print join ' ', lis 0,8,4,12,2,10,6,14,1,9,5,13,3,11,7,15;</
{{out}}
<pre>2 4 5
Line 1,561 ⟶ 2,182:
===Patience sorting===
<
my @pileTops;
# sort into piles
Line 1,594 ⟶ 2,215:
print "an L.I.S. of [@d] is [@lis]\n";
}</
{{out}}
<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}}==
Using the Wikipedia algorithm (converted to 1-based indexing)
<!--<syntaxhighlight lang="phix">(phixonline)-->
<span style="color: #008080;">with</span> <span style="color: #008080;">javascript_semantics</span>
<span style="color: #008080;">function</span> <span style="color: #000000;">lis</span><span style="color: #0000FF;">(</span><span style="color: #004080;">sequence</span> <span style="color: #000000;">x</span><span style="color: #0000FF;">,</span> <span style="color: #004080;">integer</span> <span style="color: #000000;">n</span> <span style="color: #0000FF;">=</span> <span style="color: #7060A8;">length</span><span style="color: #0000FF;">(</span><span style="color: #000000;">x</span><span style="color: #0000FF;">))</span>
<span style="color: #004080;">sequence</span> <span style="color: #000000;">p</span> <span style="color: #0000FF;">=</span> <span style="color: #7060A8;">repeat</span><span style="color: #0000FF;">(</span><span style="color: #000000;">0</span><span style="color: #0000FF;">,</span><span style="color: #000000;">n</span><span style="color: #0000FF;">),</span>
<span style="color: #000000;">m</span> <span style="color: #0000FF;">=</span> <span style="color: #7060A8;">repeat</span><span style="color: #0000FF;">(</span><span style="color: #000000;">0</span><span style="color: #0000FF;">,</span><span style="color: #000000;">n</span><span style="color: #0000FF;">)</span>
<span style="color: #004080;">integer</span> <span style="color: #000000;">len</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">0</span>
<span style="color: #008080;">for</span> <span style="color: #000000;">i</span><span style="color: #0000FF;">=</span><span style="color: #000000;">1</span> <span style="color: #008080;">to</span> <span style="color: #000000;">n</span> <span style="color: #008080;">do</span>
<span style="color: #004080;">integer</span> <span style="color: #000000;">lo</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">1</span>
<span style="color: #004080;">integer</span> <span style="color: #000000;">hi</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">len</span>
<span style="color: #008080;">while</span> <span style="color: #000000;">lo</span><span style="color: #0000FF;"><=</span><span style="color: #000000;">hi</span> <span style="color: #008080;">do</span>
<span style="color: #004080;">integer</span> <span style="color: #000000;">mid</span> <span style="color: #0000FF;">=</span> <span style="color: #7060A8;">ceil</span><span style="color: #0000FF;">((</span><span style="color: #000000;">lo</span><span style="color: #0000FF;">+</span><span style="color: #000000;">hi</span><span style="color: #0000FF;">)/</span><span style="color: #000000;">2</span><span style="color: #0000FF;">)</span>
<span style="color: #008080;">if</span> <span style="color: #000000;">x</span><span style="color: #0000FF;">[</span><span style="color: #000000;">m</span><span style="color: #0000FF;">[</span><span style="color: #000000;">mid</span><span style="color: #0000FF;">]]<</span><span style="color: #000000;">x</span><span style="color: #0000FF;">[</span><span style="color: #000000;">i</span><span style="color: #0000FF;">]</span> <span style="color: #008080;">then</span>
<span style="color: #000000;">lo</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">mid</span> <span style="color: #0000FF;">+</span> <span style="color: #000000;">1</span>
<span style="color: #000000;">hi</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">mid</span> <span style="color: #0000FF;">-</span> <span style="color: #000000;">1</span>
<span style="color: #008080;">end</span> <span style="color: #008080;">if</span>
<span style="color: #008080;">end</span> <span style="color: #008080;">while</span>
<span style="color: #008080;">if</span> <span style="color: #000000;">lo</span><span style="color: #0000FF;">></span><span style="color: #000000;">1</span> <span style="color: #008080;">then</span>
<span style="color: #000000;">p</span><span style="color: #0000FF;">[</span><span style="color: #000000;">i</span><span style="color: #0000FF;">]</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">m</span><span style="color: #0000FF;">[</span><span style="color: #000000;">lo</span><span style="color: #0000FF;">-</span><span style="color: #000000;">1</span><span style="color: #0000FF;">]</span>
<span style="color: #008080;">end</span> <span style="color: #008080;">if</span>
<span style="color: #000000;">m</span><span style="color: #0000FF;">[</span><span style="color: #000000;">lo</span><span style="color: #0000FF;">]</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">i</span>
<span style="color: #008080;">if</span> <span style="color: #000000;">lo</span><span style="color: #0000FF;">></span><span style="color: #000000;">len</span> <span style="color: #008080;">then</span> <span style="color: #000000;">len</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">lo</span> <span style="color: #008080;">end</span> <span style="color: #008080;">if</span>
<span style="color: #008080;">end</span> <span style="color: #008080;">for</span>
<span style="color: #004080;">sequence</span> <span style="color: #000000;">res</span> <span style="color: #0000FF;">=</span> <span style="color: #7060A8;">repeat</span><span style="color: #0000FF;">(</span><span style="color: #000000;">0</span><span style="color: #0000FF;">,</span><span style="color: #000000;">len</span><span style="color: #0000FF;">)</span>
<span style="color: #008080;">if</span> <span style="color: #000000;">len</span><span style="color: #0000FF;">></span><span style="color: #000000;">0</span> <span style="color: #008080;">then</span>
<span style="color: #004080;">integer</span> <span style="color: #000000;">k</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">m</span><span style="color: #0000FF;">[</span><span style="color: #000000;">len</span><span style="color: #0000FF;">]</span>
<span style="color: #008080;">for</span> <span style="color: #000000;">i</span><span style="color: #0000FF;">=</span><span style="color: #000000;">len</span> <span style="color: #008080;">to</span> <span style="color: #000000;">1</span> <span style="color: #008080;">by</span> <span style="color: #0000FF;">-</span><span style="color: #000000;">1</span> <span style="color: #008080;">do</span>
<span style="color: #000000;">res</span><span style="color: #0000FF;">[</span><span style="color: #000000;">i</span><span style="color: #0000FF;">]</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">x</span><span style="color: #0000FF;">[</span><span style="color: #000000;">k</span><span style="color: #0000FF;">]</span>
<span style="color: #000000;">k</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">p</span><span style="color: #0000FF;">[</span><span style="color: #000000;">k</span><span style="color: #0000FF;">]</span>
<span style="color: #008080;">end</span> <span style="color: #008080;">for</span>
<span style="color: #008080;">end</span> <span style="color: #008080;">if</span>
<span style="color: #008080;">return</span> <span style="color: #000000;">res</span>
<span style="color: #008080;">end</span> <span style="color: #008080;">function</span>
<span style="color: #008080;">constant</span> <span style="color: #000000;">tests</span> <span style="color: #0000FF;">=</span> <span style="color: #0000FF;">{{</span><span style="color: #000000;">3</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">2</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">6</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">4</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">5</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">1</span><span style="color: #0000FF;">},</span>
<span style="color: #0000FF;">{</span><span style="color: #000000;">0</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">8</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">4</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">12</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">2</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">10</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">6</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">14</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">1</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">9</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">5</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">13</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">3</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">11</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">7</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">15</span><span style="color: #0000FF;">}}</span>
<span style="color: #008080;">for</span> <span style="color: #000000;">i</span><span style="color: #0000FF;">=</span><span style="color: #000000;">1</span> <span style="color: #008080;">to</span> <span style="color: #7060A8;">length</span><span style="color: #0000FF;">(</span><span style="color: #000000;">tests</span><span style="color: #0000FF;">)</span> <span style="color: #008080;">do</span>
<span style="color: #0000FF;">?</span><span style="color: #000000;">lis</span><span style="color: #0000FF;">(</span><span style="color: #000000;">tests</span><span style="color: #0000FF;">[</span><span style="color: #000000;">i</span><span style="color: #0000FF;">])</span>
<span style="color: #008080;">end</span> <span style="color: #008080;">for</span>
<!--</syntaxhighlight>-->
{{out}}
<pre>
Line 1,692 ⟶ 2,270:
=={{header|PHP}}==
Patience sorting
<
class Node {
public $val;
Line 1,728 ⟶ 2,306:
print_r(lis(array(3, 2, 6, 4, 5, 1)));
print_r(lis(array(0, 8, 4, 12, 2, 10, 6, 14, 1, 9, 5, 13, 3, 11, 7, 15)));
?></
{{out}}
<pre>Array
Line 1,745 ⟶ 2,323:
[5] => 15
)</pre>
=={{header|Picat}}==
===Mode-directed tabling===
{{trans|Prolog}}
<syntaxhighlight lang="picat">table(+,+,max)
lis_mode(In, Out,OutLen) =>
one_is(In, [], Is),
Out = reverse(Is),
OutLen = Out.length.
one_is([], Current, Current2) => Current = Current2.
one_is([H|T], Current, Final) =>
( Current = [], one_is(T, [H], Final));
( Current = [H1|_], H1 @< H, one_is(T, [H|Current], Final));
one_is(T, Current, Final).</syntaxhighlight>
===Constraint modelling approach===
For larger instances, the sat solver is generally faster than the cp solver.
<syntaxhighlight lang="picat">lis_cp(S, Res,Z) =>
Len = S.len,
X = new_list(Len),
X :: 0..1,
increasing_except_0($[X[I]*S[I] : I in 1..Len]),
Z #= sum(X),
solve($[max(Z)],X),
% Extract the found LIS
Res = [S[I] : I in 1..Len, X[I] == 1].
%
% Ensures that array A is (strictly) increasing if we disregard any 0's
%
increasing_except_0(A) =>
N = A.len,
foreach(I in 1..N, J in I+1..N)
(A[I] #!= 0 #/\ A[J] #!= 0) #=> (A[I] #< A[J])
end.</syntaxhighlight>
===Test===
<syntaxhighlight lang="picat">import sat. % for lis_cp
% import cp. % Slower than sat on larger instances.
go =>
nolog,
Tests = [
[3,2,6,4,5,1],
[0,8,4,12,2,10,6,14,1,9,5,13,3,11,7,15],
[1,1,1,1],
[4,65,2,-31,0,99,83,782,1]
],
Funs = [lis_mode, lis_cp],
foreach(Fun in Funs)
println(fun=Fun),
foreach(Test in Tests)
call(Fun,Test,Lis,Len),
printf("%w: LIS=%w (len=%d)\n",Test, Lis,Len)
end,
nl,
end,
nl.</syntaxhighlight>
{{out}}
<pre>[3,2,6,4,5,1]: LIS=[3,4,5] (len=3)
[0,8,4,12,2,10,6,14,1,9,5,13,3,11,7,15]: LIS=[0,4,6,9,13,15] (len=6)
[1,1,1,1]: LIS=[1] (len=1)
[4,65,2,-31,0,99,83,782,1]: LIS=[4,65,99,782] (len=4)</pre>
The mode directed tabling tends to be the fastest of the two methods.
=={{header|PicoLisp}}==
Adapted patience sorting approach:
<
(let (D NIL R NIL)
(for I Lst
Line 1,760 ⟶ 2,408:
(T (when R (queue 'D (car R)))
(push 'R I) ) ) )
(flip R) ) )</
Original recursive glutton:
<
(let N (pop 'L)
(maxi length
Line 1,783 ⟶ 2,431:
(test (-31 0 83 782)
(glutton (4 65 2 -31 0 99 83 782 1)) )</
=={{header|PowerShell}}==
{{works with|PowerShell|2}}
<
{
If ( $A.Count -lt 2 ) { return $A }
Line 1,834 ⟶ 2,482:
# Return the series (reversed into the correct order)
return $S[$Last..0]
}</
<
( Get-LongestSubsequence 0, 8, 4, 12, 2, 10, 6, 16, 14, 1, 9, 5, 13, 3, 11, 7, 15 ) -join ', '</
{{out}}
<pre>2, 4, 5
Line 1,846 ⟶ 2,494:
<
% we ask Prolog to find the longest sequence
aggregate(max(N,Is), (one_is(In, [], Is), length(Is, N)), max(_, Res)),
Line 1,860 ⟶ 2,508:
( Current = [H1 | _], H1 < H, one_is(T, [H | Current], Final));
one_is(T, Current, Final).
</syntaxhighlight>
Prolog finds the first longest subsequence
<pre> ?- lis([0,8,4,12,2,10,6,14,1,9,5,13,3,11,7,15], Out).
Line 1,872 ⟶ 2,520:
===Python: O(nlogn) Method from Wikipedia's LIS Article[https://en.wikipedia.org/wiki/Longest_increasing_subsequence#Efficient_algorithms]===
<
"""Returns the Longest Increasing Subsequence in the Given List/Array"""
N = len(X)
Line 1,904 ⟶ 2,552:
if __name__ == '__main__':
for d in [[3,2,6,4,5,1], [0, 8, 4, 12, 2, 10, 6, 14, 1, 9, 5, 13, 3, 11, 7, 15]]:
print('a L.I.S. of %s is %s' % (d, longest_increasing_subsequence(d)))</
{{out}}
Line 1,911 ⟶ 2,559:
===Python: Method from video===
<
'Return one of the L.I.S. of list d'
l = []
Line 1,921 ⟶ 2,569:
if __name__ == '__main__':
for d in [[3,2,6,4,5,1], [0, 8, 4, 12, 2, 10, 6, 14, 1, 9, 5, 13, 3, 11, 7, 15]]:
print('a L.I.S. of %s is %s' % (d, longest_increasing_subsequence(d)))</
{{out}}
Line 1,928 ⟶ 2,576:
===Python: Patience sorting method===
<
from functools import total_ordering
from bisect import bisect_left
Line 1,950 ⟶ 2,598:
for di in d:
j = bisect_left(pileTops, Node(di, None))
return list(pileTops[-1])[::-1]
Line 1,961 ⟶ 2,604:
for d in [[3,2,6,4,5,1],
[0, 8, 4, 12, 2, 10, 6, 14, 1, 9, 5, 13, 3, 11, 7, 15]]:
print('a L.I.S. of %s is %s' % (d, lis(d)))</
{{out}}
Line 1,969 ⟶ 2,612:
=={{header|Racket}}==
Patience sorting. The program saves only the top card of each pile, with a link (cons) to the top of the previous pile at the time it was inserted. It uses binary search to find the correct pile.
<
(require data/gvector)
Line 1,995 ⟶ 2,638:
(if (<= item (car (gvector-ref piles middle)))
(loop first middle)
(loop (add1 middle) last)))))])))</
{{out}}
<pre>'(2 4 5)
'(0 2 6 9 11 15)</pre>
=={{header|Raku}}==
(formerly Perl 6)
{{works with|Rakudo|2018.03}}
===Dynamic programming===
Straight-forward implementation of the algorithm described in the video.
<syntaxhighlight lang="raku" line>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]);</syntaxhighlight>
{{out}}
<pre>[2 4 5]
[0 2 6 9 11 15]</pre>
===Patience sorting===
<syntaxhighlight lang="raku" line>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>;</syntaxhighlight>
{{out}}
<pre>[2 4 5]
[0 2 6 9 11 15]</pre>
=={{header|REXX}}==
{{trans|VBScript}}
<
$.=; $.1= 3 2 6 4 5 1 /*define the 1st list to be examined. */
$.2= 0 8 4 12 2 10 6 14 1 9 5 13 3 11 7 15 /* " " 2nd " " " " */
Line 2,034 ⟶ 2,724:
do L; $= @.k $; k= p.k /*perform this DO loop L times. */
end /*i*/
return strip($) /*the result has an extra leading blank*/</
{{out|output|text= when using the internal default input:}}
<pre>
Line 2,045 ⟶ 2,735:
=={{header|Ring}}==
<
# Project : Longest increasing subsequence
Line 2,104 ⟶ 2,794:
see svect
see "}" + nl
</syntaxhighlight>
Output:
<pre>
Line 2,113 ⟶ 2,803:
=={{header|Ruby}}==
Patience sorting
<
def lis(n)
Line 2,145 ⟶ 2,835:
p lis([3, 2, 6, 4, 5, 1])
p lis([0, 8, 4, 12, 2, 10, 6, 14, 1, 9, 5, 13, 3, 11, 7, 15])</
{{out}}
<pre>[2, 4, 5]
[0, 2, 6, 9, 11, 15]</pre>
=={{header|Rust}}==
<syntaxhighlight lang="rust">
fn lis(x: &[i32])-> Vec<i32> {
let n =
let mut m = vec![0; n];
let mut
let mut
for i in 0..n {
let mut
while lo <= hi
let mid = (lo + hi) / 2;
if x[m[mid]] <= x[i] {
lo = mid + 1;
} else {
hi = mid - 1;
}
}
let new_l = lo;
p[i] = m[new_l - 1];
l = new_l;
}
}
let mut o = vec![0; l];
let mut k = m[l];
for i in (0..l).rev() {
o[i] = x[k];
k = p[k];
}
o
}
Line 2,190 ⟶ 2,887:
let list = vec![0, 8, 4, 12, 2, 10, 6, 14, 1, 9, 5, 13, 3, 11, 7, 15];
println!("{:?}", lis(&list));
}</
{{out}}
<pre>[
[0,
=={{header|Scala}}==
===Patience sorting===
{{Out}}See it in running in your browser by [https://scalafiddle.io/sf/Wx8DsUO/1 ScalaFiddle (JavaScript)] or by [https://scastie.scala-lang.org/FtLHeaAwSrO6VXVOTTZ7FQ Scastie (JVM)].
<
val tests = Map(
"3,2,6,4,5,1" -> Seq("2,4,5", "3,4,5"),
Line 2,231 ⟶ 2,928:
allLongests.forall(lis => expect.contains(lis.mkString(",")))
})
}</
{{Out}}
<pre>3,2,6,4,5,1 has 2 longest increasing subsequences, e.g. 2,4,5
Line 2,237 ⟶ 2,934:
===Brute force solution===
<
def isSorted(l:List[Int])(f: (Int, Int) => Boolean) = l.view.zip(l.tail).forall(x => f(x._1,x._2))
def sequence(set: List[Int])(f: (Int, Int) => Boolean) = powerset(set).filter(_.nonEmpty).filter(x => isSorted(x)(f)).toList.maxBy(_.length)
sequence(set)(_<_)
sequence(set)(_>_)</
=={{header|Scheme}}==
Patience sorting
<
(define pile-tops (make-vector (length lst)))
(define (bsearch-piles x len)
Line 2,268 ⟶ 2,966:
(display (lis < '(3 2 6 4 5 1))) (newline)
(display (lis < '(0 8 4 12 2 10 6 14 1 9 5 13 3 11 7 15))) (newline)</
{{out}}
Line 2,276 ⟶ 2,974:
=={{header|Sidef}}==
Dynamic programming:
<
var l = a.len.of { [] }
l[0] << a[0]
Line 2,291 ⟶ 2,989:
say lis(%i<3 2 6 4 5 1>)
say lis(%i<0 8 4 12 2 10 6 14 1 9 5 13 3 11 7 15>)</
Patience sorting:
<
var pileTops = []
deck.each { |x|
Line 2,320 ⟶ 3,018:
say lis(%i<3 2 6 4 5 1>)
say lis(%i<0 8 4 12 2 10 6 14 1 9 5 13 3 11 7 15>)</
{{out}}
Line 2,331 ⟶ 3,029:
Patience sorting
{{works with|SML/NJ}}
<
let
val pile_tops = DynamicArray.array (length n, [])
Line 2,361 ⟶ 3,059:
app f n;
rev (DynamicArray.sub (pile_tops, DynamicArray.bound pile_tops))
end</
Usage:
<pre>- lis Int.compare [3, 2, 6, 4, 5, 1];
Line 2,370 ⟶ 3,068:
=={{header|Swift}}==
<
extension Array where Element: Comparable {
Line 2,417 ⟶ 3,115:
print("\(l1) = \(l1.longestIncreasingSubsequence())")
print("\(l2) = \(l2.longestIncreasingSubsequence())")</
{{out}}
Line 2,427 ⟶ 3,125:
{{trans|Python}}
Based on the Python video solution. Interpreter at [[http://cheersgames.com/swym/SwymInterpreter.html?Array.%27lis%27%0A%7B%0A%20%20%27stems%27%20%3D%20Number.Array.mutableArray%5B%20%5B%5D%20%5D%0A%20%0A%20%20forEach%28this%29%20%27value%27-%3E%0A%20%20%7B%0A%20%20%20%20%27bestStem%27%20%3D%20stems.where%7B%3D%3D%5B%5D%20%7C%7C%20.last%20%3C%20value%7D.max%7B.length%7D%0A%20%0A%20%20%20%20stems.push%28%20bestStem%20+%20%5Bvalue%5D%20%29%0A%20%20%7D%0A%20%0A%20%20return%20stems.max%7B.length%7D%0A%7D%0A%20%0A%5B3%2C2%2C6%2C4%2C5%2C1%5D.lis.trace%0A%5B0%2C8%2C4%2C12%2C2%2C10%2C6%2C14%2C1%2C9%2C5%2C13%2C3%2C11%2C7%2C15%5D.lis.trace]]
<
{
'stems' = Number.Array.mutableArray[ [] ]
Line 2,442 ⟶ 3,140:
[3,2,6,4,5,1].lis.trace
[0,8,4,12,2,10,6,14,1,9,5,13,3,11,7,15].lis.trace</
{{out}}
<pre>
Line 2,451 ⟶ 3,149:
=={{header|Tcl}}==
{{works with|Tcl|8.6}}
<
proc longestIncreasingSubsequence {sequence} {
Line 2,471 ⟶ 3,169:
# Pick the longest subsequence; -stride requires Tcl 8.6
return [lindex [lsort -stride 2 -index 0 $subseq] end]
}</
Demonstrating:
<
puts [longestIncreasingSubsequence {0 8 4 12 2 10 6 14 1 9 5 13 3 11 7 15}]</
{{out}}
<pre>
Line 2,482 ⟶ 3,180:
=={{header|VBScript}}==
<syntaxhighlight lang="vb">
Function LIS(arr)
n = UBound(arr)
Line 2,520 ⟶ 3,218:
WScript.StdOut.WriteLine LIS(Array(3,2,6,4,5,1))
WScript.StdOut.WriteLine LIS(Array(0,8,4,12,2,10,6,14,1,9,5,13,3,11,7,15))
</syntaxhighlight>
{{Out}}
Line 2,526 ⟶ 3,224:
2,4,5,
0,2,6,9,11,15,
</pre>
=={{header|Wren}}==
{{trans|Kotlin}}
<syntaxhighlight lang="wren">var longestIncreasingSubsequence = Fn.new { |x|
var n = x.count
if (n == 0) return []
if (n == 1) return x
var p = List.filled(n, 0)
var m = List.filled(n+1, 0)
var len = 0
for (i in 0...n) {
var lo = 1
var hi = len
while (lo <= hi) {
var mid = ((lo + hi)/2).ceil
if (x[m[mid]] < x[i]) {
lo = mid + 1
} else {
hi = mid - 1
}
}
var newLen = lo
p[i] = m[newLen - 1]
m[newLen] = i
if (newLen > len) len = newLen
}
var s = List.filled(len, 0)
var k = m[len]
for (i in len-1..0) {
s[i] = x[k]
k = p[k]
}
return s
}
var lists = [
[3, 2, 6, 4, 5, 1],
[0, 8, 4, 12, 2, 10, 6, 14, 1, 9, 5, 13, 3, 11, 7, 15]
]
lists.each { |l| System.print(longestIncreasingSubsequence.call(l)) }</syntaxhighlight>
{{out}}
<pre>
[2, 4, 5]
[0, 2, 6, 9, 11, 15]
</pre>
=={{header|zkl}}==
<
piles:=L();
backPtr:='wrap(np){ return(np-1,if(np) piles[np-1].len()-1 else -1) }; // maybe (-1,-1)
Line 2,545 ⟶ 3,289:
do{ n,p=piles[p][n]; r.write(n); p,n=p; }while(p!=-1);
r.reverse()
}</
<
T(0,8,4,12,2,10,6,14,1,9,5,13,3,11,7,15),"foobar")){
s:=longestSequence(ns);
println(s.len(),": ",s," from ",ns);
}</
{{out}}
<pre>
|