prolog - prolog 搜索列表

Question

我正在尝试比较这些列表。给定函数（List1，List2），List1 的长度为 N，List 2 的长度为 M 且 N>M。

我想检查 List2 的任何排列是否恰好是 List1 的前 M 个字符。

例如，

predicate([a,c,b,d,e],[a,b,c,d]).

应该是真实的

predicate([a,c,b,e,d],[a,b,c,d]).

应该是假的。

谢谢你。

Answer 1

通常在描述列表之间的关系时，DCG 在这种情况下很方便：

perm_prefix(Ls1, Ls2) :- phrase(perm(Ls2), Ls1, _).

perm([])  --> [].
perm(Ls0) --> [L], { select(L, Ls0, Ls1) }, perm(Ls1).

示例案例：

?- perm_prefix([a,c,b,d,e],[a,b,c,d]).
true

?- perm_prefix([a,c,b,e,d],[a,b,c,d]).
false.

Answer 2

使用permutation/2andprefix/2谓词，您可以编写如下内容：

has_prefix_perm(List1, List2) :-
    permutation(List2, Permutation),
    prefix(Permutation, List1),
    !.

作为旁注并引用swi-prolog 手册：

请注意，长度为 N 的列表有 N! 排列和无界排列生成变得非常昂贵，即使对于相当短的列表（10！= 3,628,800）也是如此。

所以我会注意不要has_prefix_perm/2用太长的第二个列表来调用，特别是如果它碰巧不是前缀模排列，因为所有的情况都会被测试。

另一种方法是测试 List1 项目是否是 List2 的成员，直到 List2 为空，这样您就知道存在排列：

has_prefix_perm(_, []) :- !.
has_prefix_perm([Head1|List1], List2) :-
    once(select(Head1, List2, Rest)),
    has_prefix_perm(List1, Rest).

那样写，我不会在非地面名单上使用它，但看到你的 OP 我没有进一步搜索......

另一种方法是检查 List1 减少到 List2 的长度是否是 List2 的排列：

has_prefix_perm(List1, List2) :-
    length(List2, L),
    length(LittleL1, L),
    append(LittleL1, _, List1),
    permutation(LittleL1, List2),
    !.

另一种方法是......我想有很多方法可以做到这一点，只需选择一个不那么复杂且适合您的风格的方法！:)

我会亲自去最后一个。

Answer 3

这是另一个 DCG 解决方案。

perm(Xs,Ys) :- 短语(perm(Xs),[],Ys)。

烫发（[]）-->[]。
烫发（[X|Xs]）-->烫发（Xs），ins（X）。

ins(X),[X]-->[]。
ins(X),[Y]-->[Y],ins(X)。

归因：序言的时刻，展览 0