Prolog挑战赛

Question

我有以下子列表算法的实现。 问题：给定两个列表，确定其中一个是否是另一个的子列表。 我真的需要另一种独特的Prolog解决方案。

第一种解决方案：

sublist([H1|T1], L, [H2|T2]):-
  H1 = H2,
  sublist(T1, L, T2).
sublist([], _, _)
sublist([H1|T1],L,[H2|T2]):-
  sublist(L,L,T2).

解决方案二：

sublist([H|T], [H|L]):- check(T,L),
sublist(S, [H|T]):- sublist(S,T).
check([H|T], [H|R]):-
   check(T,R).
check([],_).

解决方案三：

sublist(S,L):-
  append(_,R,L),
  append(S,_,R).

"方案三："

sublist(S,L):-
  append3(_,S,_,L).

- Ravul

---

你所说的列表是另一个列表的子列表，具体是什么意思？因为有几种解释。例如，这些查询中哪些应该成功 sublist([a,b,c], [a, c])、sublist([a, b, c], [c, a])、sublist([a, b, c], [a, b])？ - salva

正确的例子是：?-sublist([a b c], [d e b a b c f]) True \n ?-sublist([a b c], [a e b f c]) 失败 - Ravul

Answer 1

?- phrase((...,seq(Sublist),...),List).

使用：

... --> [] | [_], ... .

seq([]) --> [].
seq([E|Es]) --> [E], seq(Es).

（警告：为了能够解释这个解决方案，您需要先了解DCGs！）

- false

---

这是一个很好的解决方案，谢谢！ - Ravul

Answer 2

sublist([], _).
sublist([H|T], List) :-
    select(H, List, R),!,
    sublist(T, R).

如果列表一开始就是有序的，那么它可能会更有效率。

根据你所使用的 Prolog 方言，`select/3` 的名称可能不同。

注意：根据 false 的评论，这实际上是“子集”而不是“子列表”。

- twinterer

---

对于 ?- sublist([a,c],[a,b,c]).，您的解决方案成功了，这可能不是您想要的结果。 - false

嗯，这取决于列表是用来表示集合还是列表。由于我通常将列表用作集合，这可能会影响我的思考。如果列表表示一个序列，并且子列表意味着部分序列，那么你是正确的。 - twinterer

关于序列和集合存在一些歧义。尽管如此：sublist([a,c],[A,B,c]). 应该会产生一个合适的答案。 - false

子列表是初始列表的部分序列。例如：sublist([a b], [x a b c]) 返回 true，而 sublist([a,c], [a b c]) 失败。 - Ravul