Prolog搜索列表

Question

我将尝试比较这些列表。给定函数(List1, List2)，其中List1的长度为N，List2的长度为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]).

应该为假。

谢谢。

- forreal

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.

- mat

Answer 2

这是另一种 DCG 解决方案。

perm(Xs,Ys) ：- phrase(perm(Xs),[],Ys)。

perm([])-->[]。
perm([X|Xs])-->perm(Xs),ins(X)。
ins(X),[X]-->[]。
ins(X),[Y]-->[Y],ins(X)。

归属：Prolog 时刻，展品 0

- false

Answer 3

使用permutation/2和prefix/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),
    !.

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

就我个人而言，我会选择最后一个。

- m09

---

我希望我有足够的积分来投票支持您，但非常感谢您！ - forreal

请看@mat的解决方案！高效且无需切割！ - false

@Mog。它们不一样。has_prefix_perm([a,b],[X,Y]).只能找到一个解决方案。 - false

@Mog: 当输入has_prefix_perm([a,b,c],[X,a,c])时，它应该成功并返回X = b，但实际上却失败了。 - false

@Mog：我的观点是要向您展示这些！和once/1只会破坏语义。 - false