如何检查列表是否是 Prolog 中另一个列表的非空子列表

Question

我正在尝试创建一个included_list(X,Y)术语来检查 X 是否是 Y 的非空子列表。

我已经用它来检查元素是否存在于 Y 列表中

check_x(X,[X|Tail]).
check_x(X,[Head|Tail]):- check_x(X,Tail).

和附加条款

append([], L, L).
append([X | L1], L2, [X | L3]) :- append(L1, L2, L3).

创建一个列表，以便程序完成

included_list([HeadX|TailX],[HeadX|TailX]).

但是我在处理我试图通过“追加”创建的新空列表时遇到问题（我想创建一个空列表来添加确认存在于两个列表中的元素。）

我找到了这个

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

但它在 sublist([],[1,2,3,4)

Answer 1

由于您正在寻找非连续子列表或有序子集，并且不想包含空列表，因此：

sub_list([X], [X|_]).
sub_list([X], [Y|T]) :-
    X \== Y,
    sub_list([X], T).
sub_list([X,Y|T1], [X|T2]) :-
    sub_list([Y|T1], T2).
sub_list([X,Y|T1], [Z|T2]) :-
    X \== Z,
    sub_list([X,Y|T1], T2).

一些结果：

| ?- sub_list([1,4], [1,2,3,4]).

true ? a

no
| ?- sub_list(X, [1,2,3]).

X = [1] ? a

X = [2]

X = [3]

X = [1,2]

X = [1,3]

X = [1,2,3]

X = [2,3]

(2 ms) no
| ?- sub_list([1,X], [1,2,3,4]).

X = 2 ? a

X = 3

X = 4

(2 ms) no

请注意，它不仅会告诉您一个列表是否是另一个列表的子列表，而且还回答了更一般的问题，例如，的子列表是L什么？当在谓词中使用切割时，它可以删除这种情况下可能的有效解决方案。因此，该解决方案因此避免了使用 cut 。

解释：

这个想法是生成一组规则来定义子列表是什么，并尝试在没有程序性或命令性的情况下这样做。上述条款可以解释为：

1. [X] 是列表的子列表 [X|_]
2. [X]是列表的子表[Y|T]，如果X和Y是不同的，[X]是列表中的子列表T。X和Y不同的条件可防止此规则与规则 #1 重叠，并通过避免不必要的递归大大减少执行查询所需的推理次数。
3. [X,Y|T1]是[X|T2]if[Y|T1]的子列表 是 的子列表T2。该表单[X,Y|T1]确保列表至少有两个元素，以免与规则 #1 重叠（这可能导致任何单个解决方案重复多次）。
4. [X,Y|T1]是[Z|T2]ifX和Zare different[X,Y|T1]的子列表并且是 的子列表T2。该表单[X,Y|T1]确保列表至少有两个元素，以免与规则#2 重叠，X并且Z不同的条件可以防止此规则与规则#3 重叠（这可能导致任何单个解决方案重复多次）通过避免不必要的递归，大大减少了执行查询所需的推理次数。