list - Prolog中的最长子序列

Question

我想实现一个谓词P(Xs,Ys,Zs)，其中Xs, Ys,Zs是列表​​。

我是 Prolog 的新手，我无法找到一种方法来获得Xs(example. Xs = ['b','b','A','A','A','A','b','b']) 中最长的序列，该序列包含在Ys(example Ys = ['A','A','A','A','c','A','A','A','A']) 中，而不会跨越偶数次。也许有人已经写了这段代码，或者有人可以告诉我我该如何开始。感谢您的帮助。

老师的解释。

longest_subsequence(List, Part, Subsequence):-
    longest_subsequence_(List, Part, [], Subsequence).

longest_subsequence_(Xs, Ys, CurrentSubsequence, LongestSubsequence):-
    append(CurrentSubsequence, Ys, NextSubsequence),
    divide_list(Xs, [_LeftYs, NextSubsequence, _RightYs]), !,
    longest_subsequence_(Xs, Ys, NextSubsequence, LongestSubsequence).
longest_subsequence_(_Xs, _Ys, LongestSubsequence, LongestSubsequence).

Answer 1

好吧，我做到了。

 main_task(Xs, Ys, Zs) :-         
      atom_chars(Xs, Xl),
      atom_chars(Ys, Yl),
      retractall(record(_, _)),
      assert(record(0, [])),
      process(Xl, Yl, Zl),
      atom_chars(Zs, Zl).

 process(Xl, Yl, _) :-     
      get_sublist(Xl, Zl),     
      length(Zl, L),
      record(MaxL, _),
      L > MaxL,
      get_index(Yl, Zl, Il),
      test_even(Il),
      test_intersect(Il, L),
      retractall(record(_, _)),
      assert(record(L, Zl)),
      fail.
    process(_, _, Zl) :-
      record(_, Zl).

    get_sublist(L1, L2) :-
      get_tail(L1, L3),
      get_head(L3, L2).

    get_tail(L, L).
    get_tail([_|T], L) :-
        get_tail(T, L).

    get_head([H|T1], [H|T2]) :-
        get_head(T1, T2).
    get_head(_, []).

    get_index(Yl, Zl, Il) :-
      get_index(Yl, Zl, Il, 0).

    get_index([], _, [], _).
    get_index([Yh|Yt], Zl, [I|It], I) :-
      get_head([Yh|Yt], Zl),
      !,
      I1 is I + 1,
      get_index(Yt, Zl, It, I1).
    get_index([_|Yt], Zl, Il, I) :-
      I1 is I + 1,
      get_index(Yt, Zl, Il, I1).

    test_even(Il) :-
      length(Il, L),
      L > 0,
      L mod 2 =:= 0.

    test_intersect([_], _).
    test_intersect([X,Y|T], L) :-
      Y - X >= L,
      test_intersect([Y|T], L).

1. 列表中关于使用列表的符号处的所有行
2. 初始化动态数据库——将存储在其中，以及它的最大行长
3. 枚举来自 X 的所有子字符串（子列表）。 Bust 进行双重“修剪” - 首先在前面切断的列表中，然后从后面。
4. 检查结果字符串的长度，如果我们已经有很长的，请立即离开以继续破坏
5. 我们考虑一个 Y 出现的索引列表，然后列表的每个元素 - Y 中的一个位置，它包括 Z。
6. 检查奇偶校验 - 只需考虑索引列表的长度，chёtnaya 长度 - 偶数个条目。我们需要检查它是否大于零。
7. 检查交点 - 你需要检查索引列表中两个相邻元素之间的差异，差异应该始终大于长度 Z。
8. 如果进行了所有检查，则存在动态数据库更新 - 当前列表 Z 存储为最大值
9. 最后它是一个强制失败，它被回滚到第 3 段中的 fork 并继续搜索。注意：如果不进行任何检查，则本次测试失败立即回滚到第 3) 段中的分叉并继续搜索。
10. 当萧条结束时，执行第二个规则谓词过程，它只是选择基数中的最后一个 spicok Z。
11. 在列表的末尾 Z 被转换回字符串

Answer 2

一种天真的方法如下：

longest_subsequence(Xs,Ys,Zs) :-
    longest_subsequence(Xs,Ys,Ys,0,[],Zs).

longest_subsequence([X|Xs],Y0,[Y|Ys],N0,Z0,Z) :-
    try_seq([X|Xs],[Y|Ys],Nc,Zc),
    (Nc > N0
    -> longest_subsequence([X|Xs],Y0,Ys,Nc,Zc,Z)
    ;  longest_subsequence([X|Xs],Y0,Ys,N0,Z0,Z)
    ).
longest_subsequence([_|Xs],Y0,[],N0,Z0,Z) :-
    longest_subsequence(Xs,Y0,Y0,N0,Z0,Z).
longest_subsequence([],_,_,_,Z,Z).

try_seq([H|TA],[H|TB],N,[H|TC]) :-
    !,
    try_seq(TA,TB,N1,TC),
    N is N1+1.
try_seq(_,_,0,[]).

这里谓词旨在从列表的开头开始try_seq/3尽可能多地匹配（生成最长的公共子序列）。

问题是这是一种计算量大的方法：它将具有时间复杂度O(mnp)，其中n是第一个列表的长度，m是第二个列表的长度，p是两个列表的最小长度。

用你的例子调用它会给出：

?- longest_subsequence([b,b,a,a,a],[a,a,a,c,a,a,a],Zs).
Zs = [a, a, a] ;
false.

您可以使用反向引用使算法更高效，这或多或少基于Knuth-Morris-Pratt-algorithm。

Answer 3

解决问题时，首先尝试：分而治之。

当我们有一个list_subsequence(+List, ?Subsequence)谓词

list_subsequence([H|T], S) :-
  list_subsequence(H, T, S, _).
list_subsequence([H|T], S) :-
  list_subsequence(H, T, _, R),
  list_subsequence(R, S).

list_subsequence(H, [H|T], [H|S], R) :- !, list_subsequence(H, T, S, R).
list_subsequence(H, R, [H], R).

我们可以请求库（聚合）帮助：

longest_subsequence(Seq, Rep, Longest) :-
  aggregate(max(L, Sub), N^(
    list_subsequence(Seq, Sub),
    aggregate(count, list_subsequence(Rep, Sub), N),
    N mod 2 =:= 0,
    length(Sub, L)
  ), max(_, Longest)).

编辑：提供更多库支持

最近添加的库有助于：

longest_subsequence_(Seq, Rep, Longest) :-
    order_by([desc(L)], filter_subsequence(Seq, Rep, Longest, L)), !.

其中 filter_subsequence/4 只是外部聚合的目标：

filter_subsequence(Seq, Rep, Sub, L) :-
    list_subsequence(Seq, Sub),
    aggregate(count, list_subsequence(Rep, Sub), N),
    N mod 2 =:= 0,
    length(Sub, L).