logo标签列表

Prolog中计算一个列表中元素出现次数的方法

prolog
4

我需要编写一个方法，可以统计给定列表中另一个列表出现的次数。例如：

?-reps([a,b,c,a,b,c],[a,b,c],0,R). 
R = 2 ? ;
no

我试图编写它：

incr(X, X1) :-
   X1 is X+1.

reps([],[],C,D):-
   incr(C,D).
reps(_,[],C,D):-
   incr(C,D),
   !.
reps([X|A],[X|B],C,D):-
   reps(A,B,C,D),
   reps(A,B,C,D).

我的主要问题是，我可以进行首次比较，但第二次我的“比较列表”现在为空，我无法比较列表的其余部分。 有没有办法创建一个全局变量来存储“比较列表”，以便稍后调用它？

4
承诺：将为一个适用于广义查询的纯净版本支付500美元的赏金。 - false
@false 有许多问题需要解决。是否应该允许空列表：list_n_reps([], 3, [])？0次重复怎么样：list_n_reps(_, 0, [])？如果所有参数都是变量，枚举的顺序如何:list_n_reps(L, N, R)？然后你的解决方案可能是：L = R, R = [], N = 0 ; L = R, R = [], N = 1 ; ...。这可以接受吗？ - TA_intern
空列表将意味着无限次重复，即使在空列表中也是如此。因此循环似乎也是一个合理的答案。对于相同列表的不同重复次数对我来说并没有太多意义。 - false
6个回答
2
根据我的另一个答案中@false在评论中提出的建议，希望能够提供一个可以接受一般查询的pure solution。下面的解决方案还允许查找特定长度的所有重复模式或其他更一般的模式：findPatterns收集要在输入列表中搜索的所有可能的模式。reps/5与之前一样，在输入字符串中找到模式的匹配次数。然而，这个版本也可以处理任何不属于模式的内容。reps/3最后检查P是否是要在L中找到的模式之一，如果是，则检索它的计数。
findPatterns([],[]).
findPatterns([H|T],L) :- findall(P, (P=[_|_],append(P,_,[H|T])),Patterns), 
                         findPatterns(T,L1), 
                         append(Patterns, L1,L).

startNoMatch(_,[]):- false.
startNoMatch([X1|T1],[X2|T2]) :- dif(X1,X2); startNoMatch(T1,T2).

reps(L,P,C,C) :- length(L,L1), length(P,L2), L1 < L2.
reps(L,P,C,D):- append(P,R,L),C1 is C+1, reps(R,P,C1,D).
reps([H|T],P,C,D):- startNoMatch([H|T],P),reps(T,P,C,D).

reps(L,P,C) :- findPatterns(L,Patterns), 
               list_to_set(Patterns,PSet), 
               (member(P,PSet), reps(L,P,0,C); \+ member(P,PSet), C=0).

查询：
?- reps([a,b,c,a,b,c],[a,b,c],R).
R = 2 ; false.

?- reps([a,b,c,a,b,c],X,2).
X = [a] ;
X = [a, b] ;
...

?- reps([a,B],[B],2).
B = a ; false.

?- reps([a,B],[B],1).
dif(B, a) ; false.

正如最后一个查询中所看到的，dif/2 会延迟目标，因此对于与 a 不同的 B，查询的进一步部分可能会成功。
C=d, reps([a,b,C],[b,c],0). 失败。但是，reps([a,b,C],[b,c],0), C=d. 成功。Décidez-vous. - false
更新：修复了reps-Count=0的支持。 - jf_
1
reps([a,a,c],[a,c],1). 错误地失败了。 - false
@false 你又一次是正确的。使用 dif/2 进行不匹配检查应该覆盖整个模式长度。我进行了另一个更新。 - jf_
小改进（虽然我仍然持怀疑态度，毕竟有这个 findall/3）：在使用 append/3 之前，不要再使用 length(P,Len),Len>0，而是使用 P=[_|_]。 - false
显示剩余2条评论
2

我的解决方案假设空模板意味着无限多次重复：

reps(L, [], inf):-
  is_proper_list(L).
reps(L, Template, N):-
  dif(Template, []),
  reps(L, Template, 0, N).
  
reps([], _, N, N).
reps(L, Template, N, N2):-
  starts_with(Template, L, L1),
  dif(N, N2),
  succ(N, N1),
  reps(L1, Template, N1, N2).
reps([A|L], Template, N, N1):-
  split_l(Template, [A|L], H, C),
  reps1(C, L, Template, H, N, N1).

reps1(y, L, Template, H, N, N1):-
  dif(Template, H),
  reps(L, Template, N, N1).
reps1(n, _, _, _, N, N).

starts_with([], L, L).
starts_with([A|T], [A|L], L1):-
  starts_with(T, L, L1).
  
split_l([], _, [], y).
split_l([_|_], [], [], n).
split_l([_|T], [A|L], [A|L1], C):-
  split_l(T, L, L1, C).
  
is_proper_list(L):-
  freeze(L, is_proper_list1(L)).

is_proper_list1([]).
is_proper_list1([_|L]):- acyclic_term(L), is_proper_list(L).

通过一些示例运行：

?- reps([a,b,c,a,b,c],[a,b,c],N). 
N = 2 ;
false.

?- reps([a,b,c,a,b,c],X,2).
X = [a] ;
X = [a, b] ;
X = [a, b, c] ;
X = [b] ;
X = [c] ;
X = [b, c] ;
false.

?- reps([a,B],[B],N).
B = a,
N = 2 ;
N = 1,
dif(B, a) ;
;
false.

?- reps([A,B,C],[D,E],N).
A = D,
B = E,
N = 1 ;
B = D,
C = E,
N = 1,
dif(f(D, E), f(A, D)) ;
;
N = 0,
dif(f(D, E), f(A, B)),
dif(f(D, C), f(B, E)) ;
;
false.


?- reps(L,T,N).
T = [],
N = inf,
freeze(L, is_proper_list1(L)) ;
;
L = [],
N = 0,
dif(T, []) ;
;
L = T, T = [_1740],
N = 1 ;
L = [_1740, _1740],
T = [_1740],
N = 2 ;
L = [_1740, _1740, _1740],
T = [_1740],
N = 3 .
 ...

一些更多的样例：

?- reps([], [], N).
N = inf ;
false.

?- reps(L, [], N).
N = inf,
freeze(L, is_proper_list1(L)) ;
;
false.

?- reps(L, [], N), L=[].
L = [],
N = inf ;
false.
明显不纯：reps([],[],N) 成功；然而，它的泛化 reps(L,[],N) 失败。 - false
@false: 我正在使用SWI Prolog 8.0.2，其中查询都不会失败。第二个查询：reps(L, [], N) 返回 N = inf, freeze(L, proper_list1(L))。将这些示例运行添加到答案中。 - gusbro
1
我的原始程序 proper_list 当查询 proper_list(L) 时将会答复 freeze(L, proper_list1(L)). - gusbro
啊，我在使用 SWI 的默认定义。 - false
1
将\+cyclic_term(L)更改为acyclic_term(L)，我更喜欢在可能的情况下使用ISO谓词。 - gusbro
显示剩余5条评论
2
正如在我另一篇纯解决方案的评论中指出的那样，使用findall/3会对纯度产生疑问。这个答案没有使用findall/3。它假设要查找的模式是一个非空列表，否则结果为inf。 reps/3检查L中是否存在P模式，如果存在，则使用reps/4计算其出现次数。特殊情况是模式计数为0。为了避免否定pattern，谓词nopattern检查模式是否恰好包含在一个列表中，并将其附加到该列表的第一项。
pattern([A],[A]).
pattern([H|T],P) :- append(P,_,[H|T]);pattern(T,P).

noPattern(L,P) :- append(P,L,PL),reps(PL,P,0,1).

startNoMatch([],[_]):- true.
startNoMatch(_,[]):- false.
startNoMatch([X1|T1],[X2|T2]) :- dif(X1,X2); startNoMatch(T1,T2).

reps(L,P,C,C) :- length(L,L1), length(P,L2), L1 < L2.
reps(L,P,C,D):- append(P,R,L),C1 is C+1, reps(R,P,C1,D).
reps([H|T],P,C,D):- startNoMatch([H|T],P),reps(T,P,C,D).

reps(_,[],inf).
reps(L,P,0) :- P=[_|_],noPattern(L,P).
reps(L,P,C) :- P=[_|_],pattern(L,P),reps(L,P,0,C),C>0.
1
这个 inf（无穷大）并不是一个好主意（与其他部分无关）。 - false
1
您不能在谓词中真正设置全局变量。相反，您可以将常量值作为额外参数传递，以便在工作列表被消耗完毕后重置它。假设输入列表仅由模式列表的倍数组成，如您的示例所示，您可以按以下方式执行（完整模式参数为第三个）：
reps([],[],_,C,D):-
   incr(C,D).
reps([H|T],[],P, C,D):-
   incr(C,C1),reps([H|T], P, P, C1,D).
reps([X|A],[X|B],P,C,D):- reps(A,B,P,C,D).

使用以下命令：

?- reps([a,b,c,a,b,c],[a,b,c],[a,b,c],0,R).
R = 2 ;

如果在中间或不完整的模式之间存在其他字符，我将使用另一个谓词来检查列表的开头是否在每个位置匹配该模式。如果是，则增加计数器。
incr(X, X1) :-
X1 is X+1.

reps([],_,C,C).
reps([H|T],Pattern,C,D):- (startMatches([H|T],Pattern) -> 
                               incr(C,C1), reps(T,Pattern,C1,D); 
                               reps(T,Pattern,C,D)).

startMatches(_,[]).
startMatches([X|T1],[X|T2]) :- startMatches(T1,T2).
B = b, reps([a,B],[B],0,1). 成功了，但它的泛化 reps([a,B],[B],0,1). 失败了。不清楚你所说的声明式模式是什么意思。 - false
@false 或许“声明式模式”这个术语有些误导，我只是指Prolog是一种声明式语言。我已经更新了文本。不过，我不确定你的例子想要表达什么意思。 - jf_
谢谢，非常有用！但我不明白为什么你要两次调用reps函数，一次使用C1，另一次使用C。 - Alvaro Sánchez
-> 是一种控制表达式，类似于 if/else。在第一种情况下（找到模式），C 增加到 C1，然后传递给 reps。在第二种情况下，在 ; 之后，reps 获取 C，但不会增加。 - jf_
@jf_: 从声明式的角度来看（即考虑解集），广义查询不可能失败。 - false
@false，我在答案中添加了另一种选择。 - jf_
1

考虑到列表是一个任意列表，一种可能的解决方案是：

reps(L, P, N) :-
   star(P, L, 0, N).

star(_, [], A, A).
star([X|P], [Y|L], A, N) :-
   rest([X|P], [Y|L], RP, RL),
   (   RP = [],                % skip pattern
       A1 is A + 1,
       star([X|P], RL, A1, N)
   ;   dif(RP, []),            % skip first item
       star([X|P], L, A, N) ).

% rest(P, L, RP, RL)

rest([], L, [], L) :- dif(L, []).
rest(P, [], P, []).
rest([X|P], [X|L], RP, RL) :- rest(P, L, RP, RL).
rest([X|P], [Y|L], [X|P], [Y|L]) :- dif(X,Y).

例子：

?- reps([a,b,a], [a,b], N).
N = 1 ;
false.

?- reps([a,a,c], [a,c], N).
N = 1 ;
false.

?- reps([x,a,b,c,y,z,a,b,c], [a,b,c], N).
N = 2 ;
false.

?- reps([a,B], [B], N).
B = a,
N = 2 ;
N = 1,
dif(B, a) ;
false.

?- reps([a,B], P, N).
B = a,
P = [a],
N = 2 ;
P = [a],
N = 1,
dif(B, a) ;
P = [a, B],
N = 1 ;
B = a,
P = [a, a|_20298],
N = 0,
dif(_20298, []) ;
P = [a, B|_22326],
N = 0,
dif(B, a),
dif(_22326, []) ;
B = a,
P = [a, _24256|_24258],
N = 0,
dif(_24256, a) ;
P = [a, _26278|_26280],
N = 0,
dif(B, a),
dif(_26278, B) ;
P = [B],
N = 1,
dif(B, a) ;
P = [B|_29880],
N = 0,
dif(B, a),
dif(_29880, []) ;
P = [_412|_414],
N = 0,
dif(_412, B),
dif(_412, a) ;
false.
reps([a,b,a],[a,b],N). 失败。 - false
1
我已经修改了谓词rest/4的基本情况来解决这个问题。 - slago
0
考虑到列表只是一个模式的重复，可能的解决方案是：
reps(List, [P|Ps], N) :-
   star([P|Ps], List, 0, N).

star(_, [], Acc, Acc).
star([X|Xs], L, Acc, N) :-
   append([X|Xs], R, L),
   Acc1 is Acc + 1,
   star([X|Xs], R, Acc1, N).

以下是一些例子：

?- reps([1,2,3,1,2,3], [1,2,3], R).
R = 2 ;
false.

?- reps([a,b,a,b,a,b], [a,b], R).
R = 3 ;
false.

?- reps([a,B], [B], N).
B = a,
N = 2 ;
false.

?- reps([a,B], P, N).
B = a,
P = [a],
N = 2 ;
P = [a, B],
N = 1 ;
false.

?- reps(L, [a,b], N).
L = [],
N = 0 ;
L = [a, b],
N = 1 ;
L = [a, b, a, b],
N = 2 ;
L = [a, b, a, b, a, b],
N = 3.
reps([a,b],[b],N) 失败了，但应该用 N = 1 能够成功。 - false
1
我已经考虑到输入列表只包含模式的多个副本，就像问题中给出的示例一样。 - slago
我已经更新了我的答案，考虑到任意列表。 - slago
请将您的新解决方案放在另一个答案中！ - false
我已经按照你的要求发布了一个新的解决方案！ - slago
网页内容由stack overflow 提供, 点击上面的
可以查看英文原文，
原文链接