On 7/8/13, hubert depesz lubaczewski <depesz@xxxxxxxxxx> wrote: > On Mon, Jul 08, 2013 at 09:09:26AM -0400, Robert James wrote: >> I have two relations, where each relation has two fields, one >> indicating a name and one indicating a position. That is, each >> relation defines a sequence. >> >> I need to determine their longest common subsequence. Yes, I can do >> this by fetching all the data into Java (or any other language) and >> computing it using the standard LCS dynamic programming language. But >> I'd like to stay within Postgres. Is there any way to do this? > > I'm not entirely sure I understand. Can you show us some sample data and > expected output? Sure. Borrowing a good example from http://wordaligned.org/articles/longest-common-subsequence : Table A (val varchar primary key, pos integer): 1, "C" 2, "H" 3, "I" 4, "M" 5, "P" 6, "A" 7, "N" 8, "Z" 9, "E" 10, "E" Table B (val varchar primary key, pos integer): 1, "H" 2, "U" 3, "M" 4, "A" 5, "N" SELECT LongestCommonSubsequence(A,B): 1, "H" 2, "M" 3, "A" 4, "N" (Common chars are in upper case: cHiMpANzee HuMAN ) The std dynamic programming algorithm is described at http://en.wikipedia.org/wiki/Longest_common_subsequence_problem -- Sent via pgsql-general mailing list (pgsql-general@xxxxxxxxxxxxxx) To make changes to your subscription: http://www.postgresql.org/mailpref/pgsql-general
