Longest increasing subsequence: Difference between revisions
(remove plural) |
(added java patience sorting solution) |
||
Line 9: | Line 9: | ||
;Ref: |
;Ref: |
||
# [http://www.youtube.com/watch?v=4fQJGoeW5VE Dynamic Programming #1: Longest Increasing Subsequence] on Youtube |
# [http://www.youtube.com/watch?v=4fQJGoeW5VE Dynamic Programming #1: Longest Increasing Subsequence] on Youtube |
||
An efficient solution is based on [[wp:Patience sorting|Patience sorting]]. |
|||
=={{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. |
|||
<lang java>import java.util.*; |
|||
public class LIS2 { |
|||
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> |
|||
{{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|Python}}== |
=={{header|Python}}== |
Revision as of 10:48, 16 August 2013
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
An efficient solution is based on Patience sorting.
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 LIS2 {
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
<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]