Longest Palindromic Sublist (Dynamic Programming)

/* palin(List, Length, Position) is true if the longest palindromic sublist  */
/*   of the List is of length Length and occurs at position Position. In the */
/*   case of ties, the last position is returned.                            */
/* e.g. palin([3,1,4,1,5,9,2,6,5,3,5,8,9,7,9,3,2,3,8,4,6,2,6,4,3,3], 5, 20). */
/*                                                   * * * * *               */
/*      palin([2,7,1,8,2,8,1,8,2,8,4,5,9,0,4,5,2,3,5,3,6,0,2,8,7,4], 7, 4).  */
/*                   * * * * * * *                                           */
palin(List, Length, Position):-
  length(List, L),
  replicate(L, 0, Row0),
  replicate(L, 1, Row1),
  palin_1(List, List, 2, Row0, Row1, Length, 1, Position).

palin_1([_], _, _, _, [Length], Length, Position, Position):-!.
palin_1([_|Bs], As, J, Row0, Row1, Length, Position0, Position):-
  palin_2(Bs, As, Row0, Row1, 1, J, Position0, Position1, RowJ),
%  write([J, RowJ, Position1]), nl, %DEBUG
  J1 is J + 1,
  palin_1(Bs, As, J1, Row1, RowJ, Length, Position1, Position).

% Element I of row J contains the length of the longest palindrome in the
%   J elements of As starting at position I
palin_2([], _, _, _, _, _, I, I, []).
palin_2([A|Bs], [A|As], [_,C|Row0], [_,E|Row1], I, J, _, Posn, [J|RowJ]):-
  C =:= J - 2, !, % A palindrome of length J occurs at position I
  I1 is I + 1,
  palin_2(Bs, As, [C|Row0], [E|Row1], I1, J, I, Posn, RowJ).
palin_2([_|Bs], [_|As], [_|Row0], [D,E|Row1], I, J, Posn0, Posn, [D|RowJ]):-
  D >= E, !,     % Same length as that in J-1 elements starting at position I
  I1 is I + 1,
  palin_2(Bs, As, Row0, [E|Row1], I1, J, Posn0, Posn, RowJ).
palin_2([_|Bs], [_|As], [_|Row0], [D,E|Row1], I, J, Posn0, Posn, [E|RowJ]):-
  D < E,        % Same length as that in J-1 elements starting at position I+1
  I1 is I + 1,
  palin_2(Bs, As, Row0, [E|Row1], I1, J, Posn0, Posn, RowJ).

/* length(Xs, L) is true if L is the number of elements in the list Xs.      */
%length(Xs, L):-length_1(Xs, 0, L).

/* length_1(Xs, L0, L) is true if L is equal to L0 plus the number of        */
/*   elements in the list Xs.                                                */
%length_1([], L, L).
%length_1([_|Xs], L0, L):-L1 is L0 + 1, length_1(Xs, L1, L).

/* 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).

LPA Index     Home Page