3

这是我的问题：

编写一个程序distance(List, Nemptylist, SubList)/3，检查是否Sublist 是一个子列表，List其距离不超过N项之间的约束（N 实现为Nemptylist-N匿名变量列表）。假设它List 是完全实例化的。允许重复答案，只要它们的数量是有限的。

例如，对于N= 2 ：

?- distance( [a,t,d,r,a,n,c,b,c] , [_,_], [a,b,c] ).
true

?- distance( [m,a,t,d,r,b,c,t] , [_,_] , [a,b,c] ).
false

?- distance([a, t, d, r, a, n, c, b], [_, _], [a, b, c]).
false

?- distance([c, c, c, a, c, c, c], [_, _], [a]).
true.

我已经坐了几个小时，试图解决这个问题，最终上面的例子奏效了，但后来我运行了一些测试，但它们失败了。

我现在的解决方案如下：

distance( L1 , L2 , [X]   ) :-
  member(X,L1) .
distance( L1 , L2 , [H|T] ) :-
  distance(L1,L2,T) ,
  append(Y,Z,L2) ,
  T=[Hs|Ts] ,
  append([H],Y,W) ,
  append(W,[Hs],R) ,
  sublist(R,L1) .

prefix(X,L) :- append(X, _, L).

suffix(X,L) :- append(_, X, L).

sublist(X,L) :- suffix(S,L) , prefix(X,S) .

当我尝试运行此测试时：

distance( [r,a,n,c,b,c],[],X) .

由于超出运行时间错误而失败。

我调试了几个小时，我真的筋疲力尽了。请帮我完成这个可怕的任务。

4

2 回答 2

3

这是一个从不完整定义开始的逐步解决方案：

distance_tentative(Xs, _Ys, Zs) :-
   phrase(( ..., seq(Zs), ... ), Xs).

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

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

这个解决方案太专业了，因为它只描述子字符串而不描述子序列。一个子序列是：

subseq([]) --> [].
subseq([E|Es]) --> [E], subseq(Es).
subseq(Es) --> [_], subseq(Es).

现在，我们要限制中间不相关元素的数量。也就是说，我们希望将最后一条规则的应用限制在这个列表参数的长度上LN。

subseq_n([], _) --> [].
subseq_n([E|Es], LN) --> [E], subseq_n(Es, LN).
subseq_n(Es, [_|LN]) --> [_], subseq_n(Es, LN).

也许最后一条规则应该改为：

subseq_n(Es, [E|LN]) --> [E], subseq_n(Es, LN).

我怀疑问题陈述的翻译有问题。无论如何，现在我们有：

distance(Xs, Ys, Zs) :-
   phrase(( ..., subseq_n(Zs, Ys), ... ), Xs).

有很多多余的答案，但你说这没关系。

优化

...在 ;的第一个元素和第一个元素的开头之间存在很多冗余，即模棱两可subseq_n//2。同样，在之间subseq_n//2和...最后。此外，如果Zs为空，则一个答案就足够了。简短的

distance(_Xs, _Ys, []).
distance(Xs, Ys, [Z|Zs]) :-
   phrase( ( ..., [Z], rsubseq_n(Zs, Ys), ... ), Xs).

rsubseq_n([], _) --> [].
rsubseq_n([E|Es], Ys) --> [E], rsubseq_n(Es, Ys).
rsubseq_n([E|Es], [_|Ys]) --> [_], rsubseq_n([E|Es], Ys).

请注意，“距离列表”现在仅在子序列中使用。

该程序具有非常有利的终止特性：

distance(A,B,C)terminates_if b(A).

所以只需要知道第一个参数就可以使谓词终止。

编辑：您的问题陈述在距离N适用于：

...项目约束之间的距离不超过 N ...

这可能意味着总编辑距离不超过 N，或每个连续对之间的距离。因此，假设每个连续对之间的距离是指：

distanceII(_Xs, _Ys, []).
distanceII(Xs, Ys, [Z|Zs]) :-
   phrase( ( ..., [Z], rsubseq_d(Zs, Ys), ... ), Xs).

rsubseq_d([], _) --> [].
rsubseq_d([E|Es],Max) -->
   maxseq(Max),
   [E],
   rsubseq_d(Es, Max).

maxseq(_) --> [].
maxseq([_|Es]) --> [_], maxseq(Es).
于 2014-06-14T08:23:03.273 回答
2

我发现您的实施存在两个主要问题：

  1. 您正在将目标中的NEmptyList元素与List目标中的元素统一起来sublist(R, L1)。未来sublist的目标可能会失败，因为NEmptyList不会N与List. 如果你想使用 append （没关系），你应该N每次最多建立一个新的长度列表（见下文）。

  2. 您可以使用来自的相同唯一序列验证来自 的不同序列SubListList。为了证明这一点，请尝试使用您的解决方案：

    ?- distance([a,a],[],[a,a,a,a,a,a]).
true ;
true ;
false.

这是一个解决方案：

distance(_, _, []).
distance(List, NEmpty, Sublist):-
    append(_, Right, List),   % The first element can be anywhere in the list
    distance2(Right, NEmpty, Sublist).

distance2([X|_], _, [X]).
distance2(List, NEmpty, [X|Sublist]):-
    length(NEmpty, N),
    between(0, N, N1),
    length(AtMostNEmpty, N1), % Make a different list each time of length <N
    append([X|AtMostNEmpty], Right, List),
    distance2(Right, NEmpty, Sublist).
于 2014-06-14T08:24:35.003 回答