检查任何元素的频率是否超过限制

Question

我想解决一个问题，即我有一个 Prolog 元素列表。如果任何元素频率大于 N，则 false 为 return。我的期望如下。

?- frequency([1,2,2,2,5],3).
true.

?- frequency([1,2,2,2,2,5],3).
false.

我有一个获取特定元素频率的代码。任何关于问题的想法。

count(_, [], 0) :-
   !.
count(X, [X|T], N) :-
   count(X, T, N2),
   N is N2 + 1.
count(X, [Y|T], N) :-
   X \= Y,
   count(X, T, N).

Answer 1

你可以先想想最"cheap"（就写作而言）的方式来解决这样的问题。我通常会尝试弄清楚如何使用标准命令行工具来完成它。例如，要在名为 foo 的文本文件中查找所有行的出现，可以编写 (in Bash):

sort foo | uniq --count

你可以阅读手册，但这里有一个例子运行:

$ cat foo
a
b
b
b
c
d
d
a
b
d
c
$ sort foo | uniq --count
      2 a
      4 b
      2 c
      3 d

现在，询问 "is there any line that has a count above 3?" 的一种方法是像这样使用 awk：

sort foo | uniq --count | awk '{ if ( > 3) exit(1) }'

（我相信还有更聪明的方法。）

有了上面的文件，你得到：

$ sort foo | uniq --count | awk '{ if ( > 3) exit(1) }'
$ echo $?
1
$ sort foo | uniq --count | awk '{ if ( > 4) exit(1) }'
$ echo $?
0

好的，那么这对您使用 Prolog 有何帮助？好吧，一个简单的方法来模拟这样的管道：

foo | bar | baz # etc

就是在Prolog中这样写一个连词：

foo(In, X0), bar(X0, X1), baz(X1, X2) % etc

回到你的问题：你可以使用msort/2（或者在你使用的实现中调用一个稳定的排序谓词）。然后，您需要统计同一元素的运行个。在 SWI-Prolog 中至少有 group_pairs_by_key/2。你可以像下面这样使用它（连同同一个库中的其他谓词，你可以看到相同的代码link）：

pairs_keys_values(Pairs, Sorted, Sorted),
group_pairs_by_key(Pairs, Grouped),
pairs_values(Grouped, Runs),
maplist(length, Runs, Counts)

到那时，你就有了 Sorted 中每个元素在 Counts 中出现的次数（诚然，比 uniq --count 更冗长），你只需要检查其中任何一项是否超出您的限制。在 Prolog 中执行与上述 awk 调用非常相似的操作：

maplist(=<(3), Counts)

免责声明：这只是解决问题的一种方法。我决定把它写出来，因为它表明如果你知道有哪些工具可供你使用，你很少需要自己编写很多代码。

编辑

当然不用group_pairs_by_key/2；但是，了解它非常有用，这就是为什么我 link 编辑了实现。对于这个问题，做一个稳定的排序就足够了，后面跟着一个简单地计算同一元素连续出现次数的谓词，并且只有当所有这样的运行不超过限制时才会成功。执行此操作的谓词的基本结构与 group_pairs_by_key/2.

相同

Answer 2

这段代码是怎么回事...

frequency(L,N):-getall(L,L1), max_member(A,L1),A=<N.

getall([],[]).
getall(L,N):-append([],[X1|T],L),count(X1,L,N1),getall(T,N2),append([N1],N2,N).

Answer 3

使用clpfd!

:- use_module(library(clpfd)).

如果我们建立在辅助谓词 list_counts/2 上，我们可以这样定义 frequency/2：

frequency(Es, M) :-
   list_counts(Es, Xss),
   maplist(arg(2), Xss, Zs),
   maplist(#>=(M), Zs).

示例查询：

?- frequency([1,2,2,2,5], 3).
true.

?- frequency([1,2,2,2,2,5], 3).
false.

多亏了 clpfd，我们可以提出 非常笼统的 查询——并得到合乎逻辑的答案！

?- frequency([A,B,C], 2).
       A=B ,           dif(B,C)
;                A=C , dif(B,C)
;            dif(A,C),     B=C
;  dif(A,B), dif(A,C), dif(B,C).

检查任何元素的频率是否超过限制

Check if any element's frequency is above a limit

list

prolog

prolog-dif

编辑