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