prolog搜索列表

Question

我想比较一下这些清单.给定函数(List1,List2),List1具有长度N,列表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

使用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),
    !.

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

我个人会选择最后一个。