3

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

?- 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).
4

3 回答 3

4

使用！

:- 使用模块（库（clpfd））。

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

频率（Es，M）：-
    list_counts（Es，Xss），
    maplist（arg（2），Xss，Zs），
   地图列表（#>=（M），Zs）。

示例查询：

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

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

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

?- 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).
于 2016-02-25T14:27:17.270 回答
3

您可以首先尝试考虑可以解决此类问题的最“便宜”（就写作而言）的方式。我通常会尝试弄清楚如何使用标准命令行工具来做到这一点。例如，要查找名为 的文本文件中所有行foo的出现，可以编写（在 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

现在，一种询问“是否有任何行的计数超过 3”的方法？是这样使用awk的：

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

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

使用上述文件，您将获得：

$ sort foo | uniq --count | awk '{ if ($1 > 3) exit(1) }'
$ echo $?
1
$ sort foo | uniq --count | awk '{ if ($1 > 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. 例如，您可以按如下方式使用它（与同一库中的其他谓词一起，您可以在同一链接中查看代码）：

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

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

maplist(=<(3), Counts)

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

编辑

当然没有必要使用group_pairs_by_key/2; 但是，了解它非常有用，这就是我链接实现的原因。对于这个问题，做一个稳定的排序就足够了，然后是一个简单地计算相同元素连续出现次数的谓词，并且只有在所有此类运行不超过限制时才会成功。执行此操作的谓词的基本结构与group_pairs_by_key/2.

于 2016-02-21T21:04:21.693 回答
1

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

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).
于 2016-02-22T12:21:02.603 回答