Longest Common Subsequence (Dynamic Programming)

/* lcs_seq(As, Bs, Sequence) is true if Sequence is the longest common       */
/*   subsequence of the lists As and Bs.                                     */
/* e.g. lcs_seq([2,7,1,8,2,8,1,8,2,8,4,5], [3,1,4,1,5,9,2,6,5,3,5,8], X).    */
/*                   *       *   *     *      *   *     *       *            */
/* gives X=[1,1,2,5]                                                         */
lcs_seq(As, Bs, Sequence):-
  reverse(As, As1),
  reverse(Bs, Bs1),
  length(Bs, Length),
  replicate(Length, 0, LastRow),
  lcs_seq_1(As1, Bs1, [0|LastRow], [[0|LastRow]], Table),
  Table=[FirstRow|Rest],
  lcs_seq_3(Rest, 1, FirstRow, As, Bs, Sequence).

% Build the Table...
lcs_seq_1([], _, _, Table, Table).
lcs_seq_1([A|As], Bs, PreviousRow, Table0, Table):-
  lcs_seq_2(Bs, A, 0, PreviousRow, NextRow0),
  reverse([0|NextRow0], NextRow),
  lcs_seq_1(As, Bs, [0|NextRow0], [NextRow|Table0], Table).

% Build a row of the table...
lcs_seq_2([], _, _, _, []).
lcs_seq_2([A|Bs], A, _, [P1,P2|PreviousRow], [Item|NextRow]):-!, % 1+T[j-1,i-1]
  Item is 1 + P1,
  lcs_seq_2(Bs, A, Item, [P2|PreviousRow], NextRow).
lcs_seq_2([_|Bs], A, N1, [_,P2|PreviousRow], [P2|NextRow]):-     % T[j-1,i]
  P2 >= N1, !,
  lcs_seq_2(Bs, A, P2, [P2|PreviousRow], NextRow).
lcs_seq_2([_|Bs], A, N1, [_,P2|PreviousRow], [N1|NextRow]):-     % T[j,i-1]
  lcs_seq_2(Bs, A, N1, [P2|PreviousRow], NextRow).
 
% Extract the sequence from the table...
lcs_seq_3([], _, _, _, _, []):-!. % No more rows
lcs_seq_3([NextRow|Table], I, _, [A|As], [A|Bs], [A|Sequence]):-!, % A=B
  I1 is I + 1,
  lcs_seq_3(Table, I1, NextRow, As, Bs, Sequence).
lcs_seq_3([NextRow|Table], I, PreviousRow, [_|As], Bs, Sequence):-
  nth_member(NextRow, I, Item2),
  I1 is I + 1,
  nth_member(PreviousRow, I1, Item1),
  Item2 >= Item1, !, % T[j+1,i] >= T[j,i+1]
  lcs_seq_3(Table, I, NextRow, As, Bs, Sequence).
lcs_seq_3(Table, I, PreviousRow, As, [_|Bs], Sequence):-
  I1 is I + 1,
  lcs_seq_3(Table, I1, PreviousRow, As, Bs, Sequence).

/* nth_member(+Xs, ?N, ?X) is true if X is the N-th (base 1) element of the  */
/*   list Xs.                                                                */
nth_member(Xs, N, X):-nth_member_1(Xs, X, 1, N).

nth_member_1([X|_], X, I, I).
nth_member_1([_|Xs], X, I0, I):-
  I1 is I0 + 1,
  nth_member_1(Xs, X, I1, I).
  
/* replicate(N, X, Xs) is true if the list Xs contains N occurrences of the  */
/*   item X.                                                                 */
replicate(0, _, []):-!.  
replicate(I, X, [X|Xs]):-
  I > 0,
  I1 is I - 1,
  replicate(I1, X, Xs).

/* reverse(Xs, Ys) is true if Ys is the result of reversing the order of     */
/*   the elements in the list Xs.                                            */
%reverse(Xs, Ys):-reverse_1(Xs, [], Ys).

%reverse_1([], As, As).
%reverse_1([X|Xs], As, Ys):-reverse_1(Xs, [X|As], Ys).

LPA Index     Home Page