list - 有极限的序列

Question

这是我的问题:

Write a procedure distance(List, Nemptylist, SubList)/3 that checks if Sublist is a sublist of List with a distance of not more than N between items constraint (N is implemented as Nemptylist – a list of N anonymous variables). Assume that List is fully instantiated. Duplicate answers are allowed, as long as their number is finite.

For example, for 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) .

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

我调试了几个小时，我真的很累。请帮我完成这个可怕的任务。

Answer 1

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

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

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

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

这个解决方案太专业了，因为它只描述了 substrings但不是subsequences .一个子序列是:

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).

因此只需知道第一个参数即可使谓词终止。

编辑:您的问题陈述含糊不清 w.r.t.其中距离 N 适用于:

... with a distance of not more than N between items constraint ...

这可能意味着总编辑距离不超过 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).