Longest increasing subsequence: Difference between revisions
m (→{{header|Déjà Vu}}: That enter at the top of the example didn't belong) |
(Promote from draft to full task status) |
||
Line 1: | Line 1: | ||
{{ |
{{task}} |
||
Calculate and show here a [[wp:Longest increasing subsequence|longest increasing subsequence]] of the list: |
Calculate and show here a [[wp:Longest increasing subsequence|longest increasing subsequence]] of the list: |
||
:<math>\{3, 2, 6, 4, 5, 1\}</math> |
:<math>\{3, 2, 6, 4, 5, 1\}</math> |
Revision as of 11:35, 17 August 2013
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
- Dynamic Programming #1: Longest Increasing Subsequence on Youtube
- An efficient solution can be based on Patience sorting.
Déjà Vu
<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 ]
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]
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 P(namedtuple('_P', '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' pile = [[P(d[0], None)]] for i, di in enumerate(d[1:], 1): for j, pj in enumerate(pile): if pj[-1].val > di: pj.append(P(di, None if not j else pile[j-1][-1])) break else: pile.append([P(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]
Tcl
<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