prolog - 如何检查列表是否是 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 。

解释:

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

[X]是列表的子列表 [X|_]

[X]是列表的子列表 [Y|T]如果 X和 Y和[X]不同是列表的子列表 T . X的条件和 Y different 防止此规则与规则 #1 重叠，并通过避免不必要的递归大大减少执行查询所需的推理次数。

[X,Y|T1]是 [X|T2] 的子列表如果 [Y|T1]是 T2 的子列表.表格 [X,Y|T1]确保列表至少有两个元素，以免与规则 #1 重叠(这可能导致任何单个解决方案重复多次)。

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