时间戳

首页 > 解决方案 > 查找一定长度的子串

prolog - 查找一定长度的子串

问题描述

我是 prolog 的初学者，我在开始解决以下问题时遇到了麻烦：

定义 predicate partstr/3，其中第一个参数是一个列表，它生成一个A长度列表L，您在第一个列表中发现该列表是连续的。

您应该能够通过回溯呈现所有答案。

例如：

?- partstr([1, 2 , 3], L, A).

如果L=2那么A=[1,2]和[2,3]，或者如果L=2那么 F=[1,2] 和 [2,3]。等等...

我觉得你会使用递归来解决它，但我不知道从哪里开始。我真的很感激一些关于如何解决这个问题的提示，因为我觉得我无处可去。

标签： prolog

解决方案

这个问题的核心是你需要一种方法来N从一个列表中拉出所有长度的子列表，对吗？

所以...

  • 考虑append/3可以连接两个列表：append( [a,b,c], [1,2,3], L)返回L为[a,b,c,1,2,3]. 但它也可以将一个列表分解为前缀和后缀，所以

    append( Pfx, Sfx, [a,b,c])

    将在回溯时连续产生：

    特效 音效
    [] [a,b,c]
    [a] [b,c]
    [a,b] [c]
    [a,b,c] []

  • ...and...length/2不仅可以告诉您列表的长度，还可以生成指定长度的列表，其中填充了唯一的、未绑定的变量，因此length(L,3)返回[V1,V2,V3].

您可以将它们组合起来以获得您想要的行为：

partstr( Xs, N, SL ) :- % To get all the contiguous sublists of length N from Xs...
  append(_,Sfx,Xs) ,    % - repeatedly get all possible suffixes of Xs, and...
  length(SL,N) ,        % - construct an empty, unbound list of the desired length (N), and...
  append(SL,_,Sfx)      % - pull that prefix off the suffix
  .                     % Easy!

这是一种方法。我想这是课程作业，您的讲师可能希望您从头开始推出自己的解决方案。

为此，我们首先需要一个将产生源列表的谓词，并在回溯时删除列表的头部。就像是：

suffix( Xs     , Xs  ) .
suffix( [_|Xs] , Sfx ) :- suffix(Xs,Sfx).

然后我们需要一种从列表中获取第一个n元素的方法，如下所示：

take( _      , 0 , []      ) :- ! .
take( [X|Xs] , N , [X|Sfx] ) :- N1 is N-1 , take(Xs,N1,Sfx) .

鉴于这两个...

partstr( Xs, N , SL ) :-
  suffix(Xs,Sfx),
  take(Sfx,N, SL )
  .

您甚至可以省去suffix/2谓词，从而将其功能融入partstr/3自身：

partstr(    Xs  , N , SL ) :- take(Xs,N,SL).
partstr( [_|Xs] , N , SL ) :- partstr(Xs,N,SL).

我认为，这就是最佳点：很难击败 4 行代码——</p> 

partstr(    Xs  , N , SL ) :- take(Xs,N,SL) .
partstr( [_|Xs] , N , SL ) :- partstr(Xs,N,SL) .

take( _      , 0 , []      ) :- ! .
take( [X|Xs] , N , [X|Sfx] ) :- N > 0 , N1 is N-1 , take(Xs,N1,Sfx) .\

推荐阅读