Prolog - 第一个列表是第二个列表的子列表？

Question

例如：

isin([1,2,3], [1,0,1,2,3,0])

将产生 true，因为

123

在

101230

的内部

我写了以下代码：

isin([AH|AT],[AH|AT]).

isin([AH|AT],[BH|BT]):- AH = BH, isin(AT,BT),isin([AH|AT],BT).

似乎不起作用。尽量不要使用任何内置函数，顺便说一句，Prolog 有一个内置的

sublist(L1,L2)

函数。

如何使用 SWI-Prolog 编写针对内置函数的查询？我尝试直接写

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

但它给了我

underfined procedure

错误。

是否可以看到内置函数是如何编码的？怎么办？

Answer 1

sublist( [], _ ).
sublist( [X|XS], [X|XSS] ) :- sublist( XS, XSS ).
sublist( [X|XS], [_|XSS] ) :- sublist( [X|XS], XSS ).

Answer 2

如果你愿意

my_sublist( [2,3,4], [1,2,3,4,5] ) 

...成功，但是

my_sublist( [1,3,5], [1,2,3,4,5] ) 

...要失败，您可能需要考虑

my_sublist( Sublist, List ) :-
    append( [_, Sublist, _], List ).

请注意，如果您将变量作为 Sublist 传递，回溯将为您提供 List 的所有可能子列表的完整集合，但这通常会包括空列表的多次重复（因为空列表可以与所有其他子列表组合）在追加操作中位于它们的前面和后面）。

Answer 3

因为这看起来像是家庭作业，所以我只会给你一些提示：

• 您似乎错过了空列表是另一个列表的子列表的情况。

• 您将“子列表从这里开始”和“子列表稍后开始”这两种情况混合到一个子句中。

• 看来子列表的元素在大列表中应该是连续的。为此，您需要两个谓词。本质上，您必须记住，当您拆开列表时，子列表已经开始。

没有内置的

sublist/2

，只有

sublist/3

可以做不同的事情（带有谓词的过滤列表）。

Answer 4

使用成员的另一个实现是：

sublist([],_).
sublist([X|Xs],Y) :- member(X,Y) , sublist(Xs,Y).

member/2 如果找到列表中的元素则返回 true

member(X,[X|_]).
member(X,[_|Ys]):-member(X,Ys).

Answer 5

sublist(S, L) :-length(S, N),
                length(L, N1),
                N2 is N1 - N,
                length(P, N2),
                append( _ , S, P), 
                append(P, _ , L).

为了避免失败情况下的堆栈溢出，我们必须确定列表的大小

P

。

Answer 6

sublist([],[],_):-!.
sublist(_,[],_):-!.

sublist([H1|T1],[H2|T2],LV):-
H1 = H2,!,
sublist(T1,T2,LV).

sublist([H1|T1],[H2|_],LV):-
not(H1 = H2),
sublist(T1,LV,LV).

如果您尝试这些查询：

?-sublist([1,2,3,4,5],[1,2,3],[1,2,3]).
TRUE

?-sublist([1,2,3,4,5],[1,2,4],[1,2,4]).
FALSE

Answer 7

对 ДМИТРИЙ МАЛИКОВ 的答案进行一些修改，这是有效的，

preList([], L).
preList([H_s|T_s], [H_s|Tail]):-
    preList(T_s, Tail).

subList([H_s|T_s], [H_s|Tail]):-
    preList(T_s, Tail).

subList([H_s|T_s], [H_s|Tail]):-
    subList([H_s|T_s], Tail).
    
subList(Sub, [_|Tail]):-
    subList(Sub, Tail).

本质上，使用

subList

过程查找子列表和主列表的第一个元素之间的匹配。当发生匹配时，转到

preList

过程并检查这是否是列表其余部分的前缀。如果是这样，决议就成功了。

如果没有，请返回并继续比较列表的其余部分以查找第一个元素匹配。

Answer 8

% prefix: Is the left list the prefix of the left?
% True if the two have the same head and the tail of the first
% is the prefix of the tail of the second.
prefix([X|T], [X|R]) :- prefix(T, R).
% True if the left list is the empty list.
prefix([], _).

% sublist: Is the left list a sublist of the right list?
% True if the two lists start with the same element and
% the tail of the first is a prefix of the tail of the second.
sublist([X|T], [X|R]) :- prefix(T, R), !.
% True if the left list is a sublist of the tail of the second.
sublist(L, [_|R]) :- sublist(L, R).
% True if the left list is the empty list.
sublist([], _).