prolog

Question

我实现了获取列表子列表的功能，例如：

sublist([1,2,4], [1,2,3,4,5,1,2,4,6]).
true

sublist([1,2,4], [1,2,3,4,5,1,2,6]). false 看看我的解决方案：

my_equals([], _).
my_equals([H1|T1], [H1|T2]) :- my_equals(T1, T2).

sublist([], _).
sublist(L1, [H2|T2]) :- my_equals(L1, [H2|T2]); sublist(L1, T2).

你能给我另一个解决方案吗？也许存在一些预定义的谓词 my_equals ？

Answer 1

您可以使用 append/3 统一子列表，如下所示：

sublist(SubList, List):-
  append(_, Tail, List),
  append(SubList, _, Tail).

第一次调用 append/3 会将列表分成两部分（即从列表中删除一些 "leading" 项。第二次调用 append/3 将检查 SubList 本身是否是 Tail 的子列表。

正如@false 所建议的那样，至少就地面而言，交换目标会更好，

sublist(SubList, List):-
  append(SubList, _, Tail),
  append(_, Tail, List).

Answer 2

还有一个 DCG 方法来解决这个问题：

substr(Sub) --> seq(_), seq(Sub), seq(_).

seq([]) --> [].
seq([Next|Rest]) --> [Next], seq(Rest).

您将使用的电话：

phrase(substr([1,2,4]), [1,2,3,4,5,1,2,4,6]).

您可以定义：

sublist(Sub, List) :-
    phrase(substr(Sub), List).

所以你可以这样称呼它，sublist([1,2,4], [1,2,3,4,5,1,2,4,6]).。

根据@mat 的建议：

substr(Sub) --> ..., seq(Sub), ... .

... --> [] | [_], ... .

是的，您可以有一个名为 ... 的谓词。 :)

根据@repeat 和@false 的建议，我将名称从 subseq（子序列）更改为 substr（子字符串），因为 "subsequence" 的含义包含非连续序列。

Answer 3

Maybe there is exists some predefined predicate

如果您的 Prolog append/2 来自库（列表）：

sublist(S, L) :- append([_,S,_], L).

另一个相当紧凑的定义，在每个（我猜）Prolog 中都可用：

sublist(S, L) :- append(S, _, L).
sublist(S, [_|L]) :- sublist(S, L).

Answer 4

这是 Lurkers 的替代解决方案，速度稍快，假设 S 的长度比 L 短得多，因此 phrase/3 DCG 翻译时间可以忽略不计：

sublist(S, L) :-
     phrase((..., S), L, _).

如果 S=[X1,..,Xn] 它会将 DCG 转换为匹配项 I=[X1,..,Xn|O] 在执行之前，因此将 my_equals/2 完全委托给 Prolog 统一。这是一个例子运行:

?- phrase((..., [a,b]), [a,c,a,b,a,c,a,b,a,c], X).
X = [a, c, a, b, a, c] ; 
X = [a, c] ; 
false.

再见

P.S.: 也适用于其他模式 S 而不仅仅是终端。

Answer 5

原始问题中的解决方案是有效的，正如已经说过的，请注意 "my_equals" 可以被 "append" 和 "sublist" 循环替换为另一个提供原始片段的追加列表。

然而，prolog 是（或者曾经是）关于人工智能的。任何人都可以立即回答 "no" 这个例子：

sublist([1,1,1,2], [1,1,1,1,1,1,1,1,1,1] ).

因为一个人，通过简单观察列表，推断出它的一些特征，比如没有“2”。

相反，这些提案在这种情况下确实效率低下。举个例子，在DNA分析领域，研究的是只有四个元素的长序列，这种算法是不适用的。

可以做一些简单的改变，objective先看最强的条件。例如：

/* common( X, Y, C, QX, QY ) => X=C+QX, Y=C+QY */ 
common( [H|S2], [H|L2], [H|C2], DS, DL ) :- !,
     common( S2, L2, C2, DS, DL ).
common( S, L, [], S, L ).

sublist( S, L ) :-
  sublist( [], S, L ). 

sublist( P, Q, L ) :- /* S=P+Q */ 
  writeln( Q ),
  length( P, N ),
  length( PD, N ), /* PD is P with all unbound */
  append( PD, T, L ), /* L=PD+T */ 
  common( Q, T, C, Q2, _DL ), /* S=P+C+Q2; L=PD+C+_DL */
  analysis( L, P, PD, C, Q2 ).  

analysis( _L, P, P, _C, [] ) :- !. /* found sublist */

analysis( [_|L2], P, _PD, C, [] ) :- !,
  sublist( P, C, L2 ).

analysis( [_|L2], P, _PD, C, Q2 ) :-
  append( P, C, P2 ),
  sublist( P2, Q2, L2 ).

让我们试试看：

?- sublist([1,1,1,2], [1,1,1,1,1,1,1,1,1,1]).
[1,1,1,2]
[2]
[2]
[2]
[2]
[2]
[2]
[2]
[2]
false.

看看 "analysis" 是如何决定最好寻找“2”的。

显然，这是一个非常简化的解决方案，在实际情况下可以做得更好 "analysis" 并且查找的模式必须更加灵活（建议仅限于原始 S 模式尾部的模式).

prolog - 列表的子列表 - 替代方法

prolog - sublist of list - alternative approach

dcg