Longest increasing subsequence: Difference between revisions

From Rosetta Code
Content added Content deleted
(→‎{{header|Perl 6}}: adding output)
m (→‎{{header|Perl 6}}: useless newline)
Line 210: Line 210:
=={{header|Perl 6}}==
=={{header|Perl 6}}==
Straight-forward implementation of the algorithm described in the video.
Straight-forward implementation of the algorithm described in the video.
<lang Perl 6>
<lang Perl 6>sub lis(@d) {
sub lis(@d) {
my @l = [].item xx @d;
my @l = [].item xx @d;
@l[0].push: @d[0];
@l[0].push: @d[0];

Revision as of 03:38, 18 August 2013

Task
Longest increasing subsequence
You are encouraged to solve this task according to the task description, using any language you may know.

Calculate and show here a longest increasing subsequence of the list:

And of the list:

Note that a list may have more than one subsequence that is of the maximum length.

Ref
  1. Dynamic Programming #1: Longest Increasing Subsequence on Youtube
  2. An efficient solution can be based on Patience sorting.

Common Lisp

Using the method in the video <lang lisp>(defun longest-increasing-subseq (list) 

 (let ((subseqs nil))
   (dolist (item list)
     (let ((longest-so-far (longest-list-in-lists (remove-if-not #'(lambda (l) (> item (car l))) subseqs))))

(push (cons item longest-so-far) subseqs))) 

   (reverse (longest-list-in-lists subseqs))))

(defun longest-list-in-lists (lists) 

 (let ((longest nil)

(longest-len 0)) 

   (dolist (list lists)
     (let ((len (length list)))

(when (> len longest-len) (setf longest list longest-len len)))) 

   longest))

(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))))</lang>
Output:
(2 4 5)
(0 2 6 9 11 15)

D

Translation of: Python

From the second Python entry, using the Patience sorting method. <lang d>import std.stdio, std.algorithm, std.array;

/// Return one of the Longest Increasing Subsequence of /// items using patience sorting. T[] lis(T)(in T[] items) pure nothrow if (__traits(compiles, T.init < T.init)) { 

   if (items.empty)
       return null;

   static struct Node { T val; Node* back; }
   auto pile = [[new Node(items[0])]];

   OUTER: foreach (immutable di; items[1 .. $]) {
       foreach (immutable j, ref pj; pile)
           if (pj[$ - 1].val > di) {
               pj ~= new Node(di, j ? pile[j - 1][$ - 1] : null);
               continue OUTER;
           }
       pile ~= [new Node(di, pile[$ - 1][$ - 1])];
   }

   T[] result;
   for (auto ptr = pile[$ - 1][$ - 1]; ptr != null; ptr = ptr.back)
       result ~= ptr.val;
   result.reverse();
   return result;

}

void main() { 

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

}</lang>

Output:
[2, 4, 5]
[0, 2, 6, 9, 11, 15]

Déjà Vu

Translation of: Python

<lang dejavu>in-pair: if = :nil dup: false drop else: @in-pair &> swap &< dup

get-last lst: get-from lst -- len lst

lis-sub pile i di: for j range 0 -- len pile: local :pj get-from pile j if > &< get-last pj di: push-to pj & di if j get-last get-from pile -- j :nil return push-to pile [ & di get-last get-last pile ]

lis d: local :pile [ [ & get-from d 0 :nil ] ] for i range 1 -- len d: lis-sub pile i get-from d i [ for in-pair get-last get-last pile ]

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

Output:
[ 2 4 5 ]
[ 0 2 6 9 11 15 ]

Icon and Unicon

The following works in both languages:

<lang unicon>procedure main(A) 

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

end

procedure lis(A) 

   r := [A[1]] | fail
   every (put(pt := [], [v := !A]), p := !pt) do
       if put(p, p[-1] < v) then r := (*p > *r, p)
       else p[-1] := (p[-2] < v)
   return r

end</lang>

Sample runs: 

->lis 3 2 6 4 5 1
 3 4 5
->lis 0 8 4 12 2 10 6 14 1 9 5 13 3 11 7 15
 0 4 6 9 11 15
->

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. <lang java>import java.util.*;

public class LIS { 

   public static <E extends Comparable<? super E>> List<E> lis(List<E> n) {
       List<Node<E>> pileTops = new ArrayList<Node<E>>();
       // sort into piles
       for (E x : n) {

Node<E> node = new Node<E>(); node.value = x; 

           int i = Collections.binarySearch(pileTops, node);
           if (i < 0) i = ~i;

if (i != 0) node.pointer = pileTops.get(i-1); 

           if (i != pileTops.size())
               pileTops.set(i, node);
           else
               pileTops.add(node);
       }

// extract LIS from nodes List<E> result = new ArrayList<E>(); for (Node<E> node = pileTops.get(pileTops.size()-1); node != null; node = node.pointer) result.add(node.value); Collections.reverse(result); return result; 

   }

   private static class Node<E extends Comparable<? super E>> implements Comparable<Node<E>> {

public E value; public Node<E> pointer; 

       public int compareTo(Node<E> y) { return value.compareTo(y.value); }
   }

   public static void main(String[] args) {

List<Integer> d = Arrays.asList(3,2,6,4,5,1); System.out.printf("an L.I.S. of %s is %s\n", d, lis(d)); 

       d = Arrays.asList(0, 8, 4, 12, 2, 10, 6, 14, 1, 9, 5, 13, 3, 11, 7, 15);

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

   }

}</lang>

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

Perl

Translation of: Perl 6

<lang Perl>sub lis { 

   my @l = map [], 1 .. @_;
   push @{$l[0]}, +$_[0];
   for my $i (1 .. @_-1) {
       for my $j (0 .. $i - 1) {
           if ($_[$j] < $_[$i] and @{$l[$i]} < @{$l[$j]} + 1) {
               $l[$i] = [ @{$l[$j]} ];
           }
       }
       push @{$l[$i]}, $_[$i];
   }
   my ($max, $l) = 0, [];
   for (@l) {
       ($max, $l) = (scalar(@$_), $_) if @$_ > $max;
   }
   return @$l;

}

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; </lang>

Output:
2 4 5
0 2 6 9 11 15

Perl 6

Straight-forward implementation of the algorithm described in the video. <lang Perl 6>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].elems < @l[$j].elems + 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>

Output:
2 4 5
0 2 6 9 11 15

Python

Python: Method from video

<lang python>def longest_increasing_subsequence(d): 

   'Return one of the L.I.S. of list d'
   l = []
   for i in range(len(d)):
       l.append(max([l[j] for j in range(i) if l[j][-1] < d[i]] or [[]], key=len) 
                 + [d[i]])
   return max(l, key=len)

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)))</lang>
Output:
a L.I.S. of [3, 2, 6, 4, 5, 1] is [3, 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, 4, 6, 9, 13, 15]

Python: Patience sorting method

<lang python>from collections import namedtuple

class Node(namedtuple('Node_', 'val back')): 

   def __iter__(self):
       while self is not None:
           yield self.val
           self = self.back

def lis(d): 

   """Return one of the L.I.S. of list d using patience sorting."""
   if not d:
       return []
   pile = [[Node(d[0], None)]]
   for di in d[1:]:
       for j, pj in enumerate(pile):
           if pj[-1].val > di:
               pj.append(Node(di, None if not j else pile[j - 1][-1]))
               break
       else:
           pile.append([Node(di, pile[-1][-1])])

   return [val for val in pile[-1][-1]] [::-1]

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, lis(d)))</lang>
Output:
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]

Swym

Translation of: Python

Based on the Python video solution. Interpreter at [[1]] <lang swym>Array.'lis' { 

 'stems' = Number.Array.mutableArray[ [] ]

 forEach(this) 'value'->
 {
   'bestStem' = stems.where{==[] || .last < value}.max{.length}

   stems.push( bestStem + [value] )
 }

 return stems.max{.length}

}

[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</lang>

Output:
[3,4,5]
[0,4,6,9,13,15]

Tcl

Works with: Tcl version 8.6

<lang tcl>package require Tcl 8.6

proc longestIncreasingSubsequence {sequence} { 

   # Get the increasing subsequences (and their lengths)
   set subseq [list 1 [lindex $sequence 0]]
   foreach value $sequence {

set max {} foreach {len item} $subseq { if {[lindex $item end] < $value} { if {[llength [lappend item $value]] > [llength $max]} { set max $item } } elseif {![llength $max]} { set max [list $value] } } lappend subseq [llength $max] $max 

   }
   # Pick the longest subsequence; -stride requires Tcl 8.6
   return [lindex [lsort -stride 2 -index 0 $subseq] end]

}</lang> Demonstrating: <lang tcl>puts [longestIncreasingSubsequence {3 2 6 4 5 1}] puts [longestIncreasingSubsequence {0 8 4 12 2 10 6 14 1 9 5 13 3 11 7 15}]</lang>

Output:
3 4 5
0 4 6 9 13 15
Retrieved from "https://rosettacode.org/wiki/Longest_increasing_subsequence?oldid=234436"