Longest Increasing Sequence (Dynamic Programming)
/* lis(As, Xs) is true if Xs is a longest strictly increasing sequence of */
/* elements occurring in As. */
/* e.g. lis([59,43,49,37,51,25,8,51,28,21,7,75,5,54,87,13,34,92,97,2], Xs). */
/* gives Xs=[43,49,51,54,87,92,97] */
lis(As, Xs):-
lis_1(As, As, [], Ls),
max(Ls, Maximum),
reverse(As, As1),
reverse(Ls, Ls1),
lis_3(Maximum, Ls1, As1, [], Xs).
% Find length of longest increasing sequence ending at each element of As...
lis_1([], _, Ls, Ls).
lis_1([Aj|As], AllAs, Ls0, Ls):-
lis_2(Ls0, AllAs, Aj, 1, Lj),
append(Ls0, [Lj], Ls1),
lis_1(As, AllAs, Ls1, Ls).
% Find the length of the longest increasing sequence ending at A[j]...
lis_2([], _, _, Lj, Lj).
lis_2([Li|Ls], [Ai|As], Aj, Lj0, Lj):-
Aj > Ai, % Strictly increasing
Li + 1 > Lj0, !,
Lj1 is Li + 1,
lis_2(Ls, As, Aj, Lj1, Lj).
lis_2([_|Ls], [_|As], Aj, Lj0, Lj):-
lis_2(Ls, As, Aj, Lj0, Lj).
% Extract the sequence from the list of lengths in Ls...
lis_3(0, _, _, Xs, Xs):-!.
lis_3(I, [I|Ls], [A|As], Xs0, Xs):-!,
I1 is I - 1,
lis_3(I1, Ls, As, [A|Xs0], Xs).
lis_3(I, [_|Ls], [_|As], Xs0, Xs):-
lis_3(I, Ls, As, Xs0, Xs).
/* max(List, Max) is true if Max is the largest element in List. */
max([X|Xs], Y):-max_1(Xs, X, Y).
max_1([], X, X):-!.
max_1([Y|Ys], X, Z):-Y >= X, !, max_1(Ys, Y, Z).
max_1([_|Ys], X, Z):-max_1(Ys, X, Z).
/* append(Xs, Ys, Zs) is true if Zs is the result of appending the list Xs */
/* to the list Ys. */
%append([], Ys, Ys).
%append([X|Xs], Ys, [X|Zs]):-append(Xs, Ys, Zs).
/* 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