3

我正在尝试编写一个递归规则collCount/2，它将列表中的相同项目及其各自的出现次数分组到元组中。

例如，与collCount([a,b,a,b,c,b],F)绑定。运行此查询时，Prolog 仅返回.F[(a,2),(b,3),(c,1)]no

以下是我到目前为止所做的事情：

collCount([H|T],[(H,N)|L2]) :-
    countDel(H,[H|T],L,N),
    collCount(L,L2).

countDel(X,T,Rest,N) :-
    occur(X,T,N),
    delAll(X,T,Rest).

occur(_,[],0).
occur(X,[X|T],N) :-
    occur(X,T,NN),
    N is NN + 1.
occur(X,[H|T],N) :-
    occur(X,T,N),
    X \= H.

delAll(_,[],[]).
delAll(X,[X|T],Ans) :-
    delAll(X,T,Ans).
delAll(X,[H|T],[H|Rest]) :-
    delAll(X,T,Rest),
    X \= H.

谓词countDel/4计算并删除列表中特定项目的所有出现。例如，将 L与和countDel(2,[1,2,3,2,2],L,N)绑定。[1,3]N3

谓词occur/3计算列表中特定项目的所有出现次数。例如，与occur(3,[1,2,3,4,3],Num)绑定。Num2

谓词delAll/3删除列表中特定项目的所有出现。例如，与delAll(3,[1,2,3,4,3],L)绑定。L[1,2,4]

任何帮助是极大的赞赏。

4

4 回答 4

3

我想提请您注意您和@CapelliC 解决方案的一小部分。无害的：

发生（_，[]，0）：-假。
发生（X，[X|T]，N）：-
    发生(X,T,NN), false ,
     N 是 NN + 1。
发生（X，[H|T]，N）：-
    发生（X，T，N），假，
     X \ =
 H。

所以我在这里所做的就是在false你的程序中插入一些目标。以这种方式，该程序现在将比没有时进行更少的推理。尽管如此，还是有一些了不起的东西。考虑：

?- 长度(As,M), M>9, maplist(=(a),As), \+ time(occur(a,As,_))。
% 3,072次推理，0.002 秒内 0.002 CPU（100% CPU，1989931 唇）
As = [a, a, a, a, a, a, a, a, a|...],
米 = 10 ;
% 6,144 次推断，0.003 秒内 0.003 CPU（100% CPU，2050613 唇）
As = [a, a, a, a, a, a, a, a, a|...],
M = 11 ;
% 12,288 次推断，0.006 秒内 0.006 CPU（100% CPU，2128433 唇）
As = [a, a, a, a, a, a, a, a, a|...],
M = 12

你看够了吗？当再添加一个元素时，推理的数量会增加一倍。简而言之，有指数级的开销！你需要把不平等的目标放在第一位。更好的是，使用dif(X, H).

请注意，此属性与是否尾递归无关。还有一些地方可以优化，但远不如这个。

有关使用此技术的更多示例，请参见。

于 2014-06-28T22:46:28.613 回答
3

对于逻辑上纯粹的实现，请查看我对相关问题“如何计算 Prolog 列表中元素出现次数”的回答。

在那个答案中，我提出了一个list_counts/2保留的实现。

让我们list_counts/2使用吧！

?- list_counts([a,b,a,b,c,b],F).
F = [a-2, b-3, c-1].

请注意，list_counts/2表示K和V作为对K-V。通常，出于多种原因（可读性、与其他标准库谓词的互操作性、效率），这比基于逗号(K,V)或列表的表示更可取。[K,V]

如果确实需要使用逗号符号，可以定义collCount/2如下：

:- use_module(library(lambda)).

collCount(Xs,Fss) :-
    list_counts(Xs,Css),
    maplist(\ (K-V)^(K,V)^true,Css,Fss).

所以让我们collCount/2开始使用：

?- collCount([a,b,a,b,c,b],F)。
F = [(a,2), (b,3), (c,1)]。%确定性地成功

编辑 2015-05-13

出于好奇，让我们考虑一下@false 在他的回答中提到的性能方面。

以下查询大致对应于@false 在他的答案中使用的查询。在这两种情况下，我们都对通用终止所需的努力感兴趣：

?- 长度(As,M),
   M>9,
   地图列表（=（a），作为），
   时间((list_item_subtracted_count0_count(As,a,_,1,_),false ; true))。
% 73 次推理，0.000 CPU 在 0.000 秒内（95% CPU，1528316 唇）
As = [a, a, a, a, a, a, a, a, a|...],
米 = 10 ;
% 80次推理，0.000 CPU 在 0.000 秒内（96% CPU，1261133 唇）
As = [a, a, a, a, a, a, a, a, a|...],
M = 11 ;
% 87次推理，0.000 CPU 在 0.000 秒内（96% CPU，1315034 唇）
As = [a, a, a, a, a, a, a, a, a|...],
M = 12 ...
于 2015-05-13T07:37:09.483 回答
0

您的代码大部分是正确的。我已经在我修改它的地方发表了评论。

collCount([],[]).  % miss base case
collCount([H|T],[(H,N)|L2]) :-
    countDel(H,[H|T],L,N),
    collCount(L,L2).

countDel(X,T,Rest,N) :-
    occur(X,T,N),
    delAll(X,T,Rest).

occur(_,[],0).
occur(X,[X|T],N) :-
    occur(X,T,NN),
    N is NN + 1.
occur(X,[H|T],N) :-
    occur(X,T,N),
    X \= H.

delAll(_,[],[]).
delAll(X,[X|T],Ans) :-
    delAll(X,T,Ans).
delAll(X,[H|T],[H|Rest]) :-
    X \= H,  % moved before recursive call
    delAll(X,T,Rest).

这产生

?- collCount([a,b,a,b,c,b],F).
F = [ (a, 2), (b, 3), (c, 1)] ;
false.
于 2014-06-27T20:21:23.517 回答
0

单程：

frequencies_of( []     , []     ) .  % empty list? success!
frequencies_of( [X|Xs] , [F|Fs] ) :- % non-empty list?
  count( Xs , X:1 , F , X1 ) ,       % count the occurrences of the head, returning the source list with all X removed
  frequencies_of( X1 , Fs )          % continue
  .                                  %

count( [] , F , F , [] ) .           % empty list? success: we've got a final count.
count( [H|T] , X:N , F , Fs ) :-     % otherwise...
  H = X ,                            % - if the head is what we're counting, 
  N1 is N+1 ,                        % - increment the count
  count( T , X:N1 , F , Fs )         % - recurse down
  .                                  %
count( [H|T] , X:N , F , [H|Fs] ) :- % otherwise...
  H \= X ,                           % - if the head is NOT what we're counting
  count( T , X:N , F , Fs )          % - recurse down, placing the head in the remainder list
  .                                  %

另一种看待它的方式：

frequencies_of( Xs , Fs ) :-     % compile a frequency table
  frequencies_of( Xs , [] , Fs ) % by invoking a worker predicate with its accumulator seeded with the empty list
  .

frequencies_of( []     , Fs , Fs ) .  % the worker predicate ends when the source list is exhausted
frequencies_of( [X|Xs] , Ts , Fs ) :- % otherwise...
  count( X , Ts , T1 ) ,              % - count X in the accumulator
  frequencies_of( Xs , T1 , Fs )      % - and recursively continue
  .                                   %

count( X , []       , [X:1]     ) .   % if we get to the end, we have a new X: count it
count( X , [X:N|Ts] , [X:N1|Ts] ) :-  % otherwise, if we found X,
  N1 is N+1                           % - increment the count
  .                                   % - and end.
count( X , [T:N|Ts] , [T:N|Fs]  ) :-  % otherwise
  X \= T ,                            % - assuming we didn't find X
  increment( X , Ts , Fs )            % - just continue looking
  .                                   % Easy!

第三种方法是首先对列表进行排序，而不删除重复项。一旦列表被排序，一个简单的 1-pass，有序列表的运行长度编码就会为您提供频率表，如下所示：

frequencies_of( Xs , Fs ) :- % to compute the frequencies of list elements
  msort( Xs , Ts ) ,         % - sort the list (without removing duplicates)
  rle( Ts , Fs )             % - then run-length encode the sorted list
  .                          % Easy!

rle( []    , [] ) .    % the run length encoding of an empty list is the empty list.
rle( [H|T] , Rs ) :-   % the run length encoding is of a non-empty list is found by
  rle( T , H:1 , Rs )  % invoking the worker on the tail with the accumulator seeded with the head
  .                    %

rle( []    , X:N , [X:N] ) .     % the end of the source list ends the current run (and the encoding).
rle( [H|T] , X:N , Rs    ) :-    % otherwise...
  H = X     ,                    % - if we have a continuation of the run,
  N1 is N+1 ,                    % - increment the count
  rle( T , X:N1 , Rs )           % - and recursively continue
  .                              %
rle( [H|T] , X:N , [X:N|Rs] ) :- % otherwise...
  H \= X ,                       % - if the run is at an end,
  rle( T , H:1 , Rs)             % - recursively continue, starting a new run and placing the current encoding in the result list.
  .                              %
于 2014-06-27T23:33:55.833 回答