StackOverflow2013

Note that there are some explanatory texts on larger screens.

plurals

PO
text
Body
copied!<p>Here's a solution in Python for an arbitrary number of sequences. You could use it to test your solution for 2D, 3D cases. It closely follows <a href="http://en.wikipedia.org/wiki/Longest_common_subsequence_problem#LCS_function_defined" rel="nofollow">Wikipedia's algorithm</a>:</p> <pre><code>#!/usr/bin/env python import functools from itertools import starmap @memoize def lcs(*seqs): """Find longest common subsequence of `seqs` sequences. Complexity: O(len(seqs)*min(seqs, key=len)*reduce(mul,map(len,seqs))) """ if not all(seqs): return () # at least one sequence is empty heads, tails = zip(*[(seq[0], seq[1:]) for seq in seqs]) if all(heads[0] == h for h in heads): # all seqs start with the same element return (heads[0],) + lcs(*tails) return max(starmap(lcs, (seqs[:i]+(tails[i],)+seqs[i+1:] for i in xrange(len(seqs)))), key=len) def memoize(func): cache = {} @functools.wraps(func) def wrapper(*args): try: return cache[args] except KeyError: r = cache[args] = func(*args) return r return wrapper </code></pre> <p>Note: without memoization it is an exponential algorithm (<a href="http://www.wolframalpha.com/input/?i=RSolve%5B%7Ba%5Bn%5D+%3D%3D+K+a%5Bn-1%5D+%2B+K%2C+a%5B0%5D+%3D+K%7D%2C+a%5Bn%5D%2C+n%5D" rel="nofollow">wolfram alpha</a>):</p> <pre><code>$ RSolve[{a[n] == K a[n-1] + K, a[0] = K}, a[n], n] a(n) = (K^(n + 1) - 1) K/(K - 1) </code></pre> <p>where <code>K</code> == <code>len(seqs)</code> and <code>n</code> == <code>max(map(len, seqs))</code></p> <h3>Examples</h3> <pre><code>>>> lcs("agcat", "gac") ('g', 'a') >>> lcs("banana", "atana") ('a', 'a', 'n', 'a') >>> lcs("abc", "acb") ('a', 'c') >>> lcs("XMJYAUZ", "MZJAWXU") ('M', 'J', 'A', 'U') >>> lcs("XMJYAUZ") ('X', 'M', 'J', 'Y', 'A', 'U', 'Z') >>> lcs("XMJYAUZ", "MZJAWXU", "AMBCJDEFAGHI") ('M', 'J', 'A') >>> lcs("XMJYAUZ", "MZJAWXU", "AMBCJDEFAGUHI", "ZYXJAQRU") ('J', 'A', 'U') >>> lcs() #doctest: +IGNORE_EXCEPTION_DETAIL Traceback (most recent call last): ... ValueError: >>> lcs(*"abecd acbed".split()) ('a', 'b', 'e', 'd') >>> lcs("acd", lcs("abecd", "acbed")) ('a', 'd') >>> lcs(*"abecd acbed acd".split()) ('a', 'c', 'd') </code></pre>

Querying!

Guidance

An individual column

Larger individual text columns get their own page to allow for proper reading.

SQuiL has stopped working due to an internal error.

If you are curious you may find further information in the browser console, which is accessible through the devtools (F12).

Reload