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]).

但是它给我一个“未定义过程”错误。

是否有可能查看内置函数的代码？如何操作？

- user893182

---

请尽量一次只提出一个问题。为什么在第一个问题中我们应该尽量避免使用任何内置谓词？ - svick

@svick 我不想为自己的问题浪费几篇帖子。 - user893182

@用户，请做到这一点。 这不是一个论坛，每个问题都应该只是一个问题。 例如，不同的人很可能想回答您当前问题的不同部分。 如果他们不知道所有答案，他们可能不会费心回答。 - svick

@svick 好的，如果那是首选方式。我将在未来的帖子中按照你说的做。谢谢。 - user893182

也许这是一份作业？这可以解释为什么我们不应该使用内置函数，以及为什么查看内置函数的源代码对于提问者有帮助。 - undefined

Answer 1

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

- ДМИТРИЙ МАЛИКОВ

---

根据这个定义，sublist([1,2,3], [0,1,0,2,0,3,0]) 是真的。 - starblue

有没有关于如何实现@starblue所说的内容的提示？例如，我只想识别[1,2,3]。 - Vaggelis Manousakis

这不是“sublist”的定义，而是“subset”的定义。例如，使用您的定义sublist(X，[a，b，c])返回X = []，[a]，[a，b]，[a，b，c]，[a，c]，[b]，[b，c]，[c]。 [a，c]不是[a，b，c]的子列表，而是子集。 - Géry Ogam

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)传递，回溯(backtracking)将为您提供列表(List)的所有可能子列表的综合集，但这通常包括多个空列表的重复项(因为空列表可以与在附加操作中位于它们前面和后面的所有其他子列表组合)。

- Kaitain

Answer 3

由于这似乎是一份作业，我只会给你一些提示：

• 看起来你漏掉了一个空列表是另一个列表的子列表的情况。

• 你把“子列表从这里开始”和“子列表从后面开始”两种情况混在了一起。

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

没有内置的sublist/2，只有一个sublist/3，它执行不同的操作（使用谓词过滤列表）。

- starblue

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

- guilieen

---

这是不正确的：sublist(X, [a, b, c]) 返回 [], [a], [a, a], [a, a, a], [a, a, a, a], …。 - Géry Ogam

Answer 5

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

- Klajdi Isteri

Answer 6

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

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

- Parsa

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过程并检查是否这是剩余列表的前缀。如果是，则解决方案以成功结束。

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

- Karthik_D

Answer 8

% prefix: Is the first list the prefix of the second?
% 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 first list is the empty list.
prefix([], _).

% sublist: Is the first list a sublist of the second 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 first list is a sublist of the tail of the second.
sublist(L, [_|R]) :- sublist(L, R).
% True if the first list is the empty list.
sublist([], _).

- Mihai Danila