Longest increasing subsequence: Difference between revisions

{{trans|Python}}

V n = x.len

V P = [0] * n

L(d) [[3, 2, 6, 4, 5, 1], [0, 8, 4, 12, 2, 10, 6, 14, 1, 9, 5, 13, 3, 11, 7, 15]]

{{out}}

=={{header|360 Assembly}}==

{{trans|VBScript}}

LNGINSQ CSECT

USING LNGINSQ,R13 base register

XDEC DS CL12 temp for xdeco

YREGS

{{out}}

<pre>

{{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.

script o

property inputList : aList

set end of output to {finds:longestIncreasingSubsequences(input's contents)}

end repeat

{{output}}

=={{header|Arturo}}==

l: new [[]]

loop d 'num [

] 'seq [

print ["LIS of" seq "=>" lis seq]

{{out}}

=={{header|AutoHotkey}}==

for k, v in Lists {

}

return, D

'''Output:'''

<pre>3, 4, 5

=={{header|C}}==

Using an array that doubles as linked list (more like reversed trees really). O(n) memory and O(n²) runtime.

#include <stdlib.h>

lis(y, sizeof(y) / sizeof(int));

return 0;

{{out}}

<pre>

===Recursive===

{{works with|C sharp|6}}

using System.Collections;

using System.Collections.Generic;

IEnumerator IEnumerable.GetEnumerator() => GetEnumerator();

}

===Patience sorting===

{{works with|C sharp|7}}

{

public static T[] Find<T>(IList<T> values, IComparer<T> comparer = null) {

Console.WriteLine(string.Join(",", LIS.Find(new [] { 0, 8, 4, 12, 2, 10, 6, 14, 1, 9, 5, 13, 3, 11, 7, 15 })));

}

{{out}}

<pre>

Patience sorting

=== C++11 ===

#include <list>

#include <algorithm>

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 });

=== C++98 ===

#include <list>

#include <algorithm>

show_lis(vec1);

show_lis(vec2);

{{out}}

<pre>2 4 5

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))

(println (a-longest [3 2 6 4 5 1]))

{{out}}

=={{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)

(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)))

{{out}}

<pre>(2 4 5)

===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)

(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)))

{{out}}

<pre>(2 4 5)

===Common Lisp: Using the Patience Sort approach (alternative)===

This is a different version of the code above.

(multiple-value-bind

(i prev)

(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)))

{{out}}

<pre>(2 4 5)

{{trans|Haskell}}

Uses the second powerSet function from the Power Set Task.

T[] lis(T)(T[] items) pure nothrow {

[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]

{{trans|Python}}

From the second Python entry, using the Patience sorting method.

/// Return one of the Longest Increasing Subsequence of

[0,8,4,12,2,10,6,14,1,9,5,13,3,11,7,15]])

d.lis.writeln;

The output is the same.

{{trans|Java}}

With some more optimizations.

T[] lis(T)(in T[] items) pure nothrow

[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

!. lis [ 3 2 6 4 5 1 ]

!. lis [ 0 8 4 12 2 10 6 14 1 9 5 13 3 11 7 15 ]

{{out}}

===Naive version===

very slow

# Naive implementation

def lis(l) do

IO.inspect Longest_increasing_subsequence.lis([3,2,6,4,5,1])

{{out}}

===Patience sort version===

# Patience sort implementation

def patience_lis(l), do: patience_lis(l, [])

IO.inspect Longest_increasing_subsequence.patience_lis([3,2,6,4,5,1])

{{out}}

Function ''memo'' and ''patience2'' by [https://www.linkedin.com/in/find-roman/ Roman Rabinovich].

-module(longest_increasing_subsequence).

% **************************************************

Output naive:

=={{header|Go}}==

Patience sorting

import (

fmt.Printf("an L.I.S. of %v is %v\n", d, lis(d))

}

{{out}}

=={{header|Haskell}}==

===Naive implementation===

import Data.List ( maximumBy, subsequences )

import Data.List.Ordered ( isSorted, nub )

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]

{{out}}

===Patience sorting===

module Main (main, lis) where

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]

{{out}}

The following works in both languages:

every writes((!lis(A)||" ") | "\n")

end

else p[-1] := (p[-2] < v)

return r

Sample runs:

These examples are simple enough for brute force to be reasonable:

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.

Example use:

longestinc 3,2,6,4,5,1

2 4 5

0 2 6 9 13 15

0 4 6 9 11 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 {

System.out.printf("an L.I.S. of %s is %s\n", d, lis(d));

}

{{out}}

=={{header|JavaScript}}==

if (input.length === 0) {

return [];

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]));

{{out}}

===Patience sorting===

if (input.length === 0) {

return 0;

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]));

{{out}}

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;

else .[0] = $mid + 1

end )

'''lis:'''

# Helper function:

)

| .[length - 1]

'''Examples:'''

[0,8,4,12,2,10,6,14,1,9,5,13,3,11,7,15]

{{out}}

[2,4,5]

[0,2,6,9,11,15]

=={{header|Julia}}==

{{works with|Julia|0.6}}

function lis(arr::Vector)

if length(arr) == 0 return copy(arr) end

@show lis([3, 2, 6, 4, 5, 1])

{{out}}

=={{header|Kotlin}}==

Uses the algorithm in the Wikipedia L.I.S. article:

fun longestIncreasingSubsequence(x: IntArray): IntArray =

)

lists.forEach { println(longestIncreasingSubsequence(it).asList()) }

{{out}}

=={{header|Lua}}==

local piles = { { {table.remove(seq, 1), nil} } }

while #seq>0 do

buildLIS({3,2,6,4,5,1})

buildLIS({0,8,4,12,2,10,6,14,1,9,5,13,3,11,7,15})

{{out}}

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.

Module LIS_example {

Function LIS {

}

LIS_example

===Using arrays in an array===

Module LIS_example {

Function LIS {

}

LIS_example

{{out}}

=={{header|Maple}}==

LIS := proc(L)

local i, j;

return output[index];

Alternatively, output the longest subsequence using built-in command max:

M := [0, 8, 4, 12, 2, 10, 6, 14, 1, 9, 5, 13, 3, 11, 7, 15];

LIS(L);

{{out}}

<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|Nim}}==

{{trans|Python}}

var l: seq[seq[T]]

for i in 0 .. d.high:

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]]:

{{out}}

<pre>A L.I.S. of @[3, 2, 6, 4, 5, 1] is @[3, 4, 5]

=={{header|Objective-C}}==

Patience sorting

@interface Node : NSObject {

}

return 0;

{{out}}

<pre>an L.I.S. of (

=={{header|OCaml}}==

===Naïve implementation===

then x

else acc) [] l

in

List.map (fun x -> print_endline (String.concat " " (List.map string_of_int

{{out}}

<pre>

===Patience sorting===

let pile_tops = Array.make (List.length list) [] in

let bsearch_piles x len =

in

let len = List.fold_left f 0 list in

Usage:

<pre># lis compare [3; 2; 6; 4; 5; 1];;

===Dynamic programming===

{{trans|Raku}}

sub lis {

print join ' ', lis 3, 2, 6, 4, 5, 1;

{{out}}

<pre>2 4 5

===Patience sorting===

my @pileTops;

# sort into piles

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]

=={{header|Phix}}==

Using the Wikipedia algorithm (converted to 1-based indexing)

<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: #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>

{{out}}

<pre>

=={{header|PHP}}==

Patience sorting

class Node {

public $val;

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

===Mode-directed tabling===

{{trans|Prolog}}

lis_mode(In, Out,OutLen) =>

one_is(In, [], Is),

( Current = [], one_is(T, [H], Final));

( Current = [H1|_], H1 @< H, one_is(T, [H|Current], Final));

===Constraint modelling approach===

For larger instances, the sat solver is generally faster than the cp solver.

Len = S.len,

X = new_list(Len),

foreach(I in 1..N, J in I+1..N)

(A[I] #!= 0 #/\ A[J] #!= 0) #=> (A[I] #< A[J])

===Test===

% import cp. % Slower than sat on larger instances.

nl,

end,

{{out}}

=={{header|PicoLisp}}==

Adapted patience sorting approach:

(let (D NIL R NIL)

(for I Lst

(T (when R (queue 'D (car R)))

(push 'R I) ) ) )

Original recursive glutton:

(let N (pop 'L)

(maxi length

(test (-31 0 83 782)

=={{header|PowerShell}}==

{{works with|PowerShell|2}}

{

If ( $A.Count -lt 2 ) { return $A }

# Return the series (reversed into the correct order)

return $S[$Last..0]

{{out}}

<pre>2, 4, 5

% we ask Prolog to find the longest sequence

aggregate(max(N,Is), (one_is(In, [], Is), length(Is, N)), max(_, Res)),

( Current = [H1 | _], H1 < H, one_is(T, [H | Current], Final));

one_is(T, Current, Final).

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).

===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)

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]]:

{{out}}

===Python: Method from video===

'Return one of the L.I.S. of list d'

l = []

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]]:

{{out}}

===Python: Patience sorting method===

from functools import total_ordering

from bisect import bisect_left

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]]:

{{out}}

=={{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)

(if (<= item (car (gvector-ref piles middle)))

(loop first middle)

{{out}}

<pre>'(2 4 5)

Straight-forward implementation of the algorithm described in the video.

my @l = [].item xx @d;

@l[0].push: @d[0];

say lis([3,2,6,4,5,1]);

{{out}}

<pre>[2 4 5]

===Patience sorting===

my @S = [@deck.shift() => Nil].item;

for @deck -> $card {

say lis <3 2 6 4 5 1>;

{{out}}

<pre>[2 4 5]

=={{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 " " " " */

do L; $= @.k $; k= p.k /*perform this DO loop L times. */

end /*i*/

{{out|output|text=&nbsp; when using the internal default input:}}

<pre>

=={{header|Ring}}==

# Project : Longest increasing subsequence

see svect

see "}" + nl

Output:

<pre>

=={{header|Ruby}}==

Patience sorting

def lis(n)

p lis([3, 2, 6, 4, 5, 1])

{{out}}

<pre>[2, 4, 5]

=={{header|Rust}}==

fn lis(x: &[i32])-> Vec<i32> {

let n = x.len();

let list = vec![0, 8, 4, 12, 2, 10, 6, 14, 1, 9, 5, 13, 3, 11, 7, 15];

println!("{:?}", lis(&list));

{{out}}

===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"),

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

===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)(_<_)

=={{header|Scheme}}==

Patience sorting

(define pile-tops (make-vector (length lst)))

(define (bsearch-piles x len)

(display (lis < '(3 2 6 4 5 1))) (newline)

{{out}}

=={{header|Sidef}}==

Dynamic programming:

var l = a.len.of { [] }

l[0] << a[0]

say lis(%i<3 2 6 4 5 1>)

Patience sorting:

var pileTops = []

deck.each { |x|

say lis(%i<3 2 6 4 5 1>)

{{out}}

Patience sorting

{{works with|SML/NJ}}

let

val pile_tops = DynamicArray.array (length n, [])

app f n;

rev (DynamicArray.sub (pile_tops, DynamicArray.bound pile_tops))

Usage:

<pre>- lis Int.compare [3, 2, 6, 4, 5, 1];

=={{header|Swift}}==

extension Array where Element: Comparable {

print("\(l1) = \(l1.longestIncreasingSubsequence())")

{{out}}

{{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[ [] ]

[3,2,6,4,5,1].lis.trace

{{out}}

<pre>

=={{header|Tcl}}==

{{works with|Tcl|8.6}}

proc longestIncreasingSubsequence {sequence} {

# Pick the longest subsequence; -stride requires Tcl 8.6

return [lindex [lsort -stride 2 -index 0 $subseq] end]

Demonstrating:

{{out}}

<pre>

=={{header|VBScript}}==

Function LIS(arr)

n = UBound(arr)

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))

{{Out}}

=={{header|Wren}}==

{{trans|Kotlin}}

var n = x.count

if (n == 0) return []

[0, 8, 4, 12, 2, 10, 6, 14, 1, 9, 5, 13, 3, 11, 7, 15]

]

{{out}}

=={{header|zkl}}==

piles:=L();

backPtr:='wrap(np){ return(np-1,if(np) piles[np-1].len()-1 else -1) }; // maybe (-1,-1)

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>