查找一定长度的子串

Question

我是 prolog 的初学者，我在开始时遇到以下问题：

Define the predicate partstr/3, where the first argument is a list, that generates a list A of length L that you find consecutive in the first list.

You should be able to present all answers with backtracking.

例如：

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

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

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

Answer 1

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

所以...

考虑 append/3 可以连接两个列表：append( [a,b,c], [1,2,3], L) returns L as [a,b,c,1,2,3]。但它也可以分解一个列表为前缀和后缀，所以
```
append( Pfx, Sfx, [a,b,c])
```
将在回溯时连续产生：

Pfx Sfx

[] [a,b,c]

[a] [b,c]

[a,b] [c]

[a,b,c] []
...and... length/2 不仅可以告诉您列表的长度，而且可以生成指定长度的列表，其中填充了唯一的，未绑定变量，所以 length(L,3) returns [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 行代码 —

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

Pfx	Sfx
`[]`	`[a,b,c]`
`[a]`	`[b,c]`
`[a,b]`	`[c]`
`[a,b,c]`	`[]`

查找一定长度的子串

Find substrings of certain length

prolog