时间戳

首页 > 解决方案 > 给定重复次数的另一个列表的重复列表

prolog - 给定重复次数的另一个列表的重复列表

问题描述

我试图建立一个谓词itrepeats(all,part,num0,num)

“all”是“part”列表重复的完整列表。"num"是"all"中"part"的重复次数，" num0"增加"num"

例如：

itrepeats(['a','b','c','a','b','c','a','b','c'],['a','b','c'],0,R)

输出应该是：

R=3

另一个例子：

itrepeats(['a','b','c','c','a','b','a','b','b'],['a','b','c'],0,R)

输出应该是：

no

“all”为空的另一个示例：

itrepeats([],['a','b','c'],0,R)

输出应该是：

R=0

我试过这个，但它不起作用，即使只是两个元素的列表：

itrepeats([],[_],0,0).
itrepeats([A,B|R],[A,B|R2],0,N):-
    N is N-1,
    itrepeats(R,[A,B|R2],0,N).

我很确定应该是这样，在没有实际迭代的先前元素的情况下执行下一次迭代，直到“all”为空，但我不知道如何做好。请帮忙，谢谢。

标签： prolog

解决方案

这可能会帮助你。

一个常见的 Prolog 习惯用法是使用带有附加状态作为额外参数的辅助谓词。在这里，我们需要一个累加器来计算匹配的子列表，我们用 0 作为其初始值：

number_of_sublists( [H|T] , SL , N ) :- number_of_sublists( [H|T], SL, 0, N ).

查找匹配子列表的过程非常简单：

  • 如果所需的子列表是当前列表的前缀，则将计数打上 1。
  • 剥离列表的头部并在尾部向下递归。
  • 当列表为空时，累加器的值是匹配子列表的最终计数。

查找一个列表是否是另一个列表的前缀非常容易。只需匹配列表项，直到一个列表为空。（请注意，空列表将作为每个列表的前缀找到。）

is_prefix_of( []     , _      ).   % once the prefix list is empty, we're done: the prefix list is the prefix of the other list.
is_prefix_of( [X|Xs] , [X|Ys] ) :- % Otherwise, if the two lists share a common head,
    is_prefix_of(Xs, Ys).          % - then recurse down on the tails.

把它们放在一起，你会得到：

number_of_sublists( []    , _  , N , N ) .  % once the list is exhausted, we're done. The accumulator is the final tally.
number_of_sublists( [H|T] , SL , X , N ) :- % otherwise...
    ( is_prefix_of(SL, [H|T])               % - if the sublist is a prefix of the list
      -> X1 is X+1                          %   - then increment the accumulator by 1
      ;  X1 is X                            %   - else don't increment 
    ),                                      %
    number_of_sublists( T, SL, X1, N ).     % remove the head of the list and recurse down on its tail.

有人可能会注意到，使用findall/3and可以更轻松地完成此操作append/3，例如：

number_of_sublists( L, SL, N ) :- findall( SL , prefix_of(SL,L), Sls), length(SLs,N).

prefix_of( SL, L ) :-
  append( _  , Sfx , L   ) ,
  append( SL , _   , Sfx ).

推荐阅读