如何检查一个列表是否是 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]).

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

我找到了这个

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

但它在子列表 ([],[1,2,3,4)

上变为 true

Answer 1

如果顺序很重要。示例 [1,2,3] 是 [1,2,3,4] 的子列表，但 [1,3,2] 不是。

你可以这样做。

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

Answer 2

这是你要做的：

mysublist(L,L1):- sublist(L,L1), notnull(L).

notnull(X):-X\=[].

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

以此为参考： Prolog - first list is sublist of second list? 我只是添加了条件以预先检查它是否为空。

希望对您有所帮助。

Answer 3

由于您正在寻找一个非连续子列表或有序子集，并且不想包含空列表，那么:

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] 是列表 [=20] 的子列表=]. X 和 Y 的不同条件可防止此规则与规则 #1 重叠，并通过避免不必要的递归大大减少执行查询所需的推理次数。
[X,Y|T1] 是 [X|T2] 的子列表，如果 [Y|T1] 是 T2 的子列表。 [X,Y|T1] 形式确保列表至少有两个元素，以免与规则 #1 重叠（这可能导致任何单个解决方案重复多次）。

X

Z

[X,Y|T1]

T2

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

Answer 4

我会使用追加：

sublist(X, []) :-
    is_list(X).


sublist(L, [X | Rest]) :-
    append(_, [X|T], L),
    sublist(T, Rest).

Answer 5

基本上，如果 M 存在于 L 中，我们可以检查 M 是否是 L 的子列表，方法是在其背面 and/or 其前面附加一些内容。

append([], Y, Y).
append([X|XS],YS,[X|Res]) :- append(XS, YS, Res).

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

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

How to check if a list is a non-empty sublist of another list in Prolog

prolog

sublist