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

を使用してください。

:- use_module(ライブラリ(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.

のおかげで、非常に一般的な質問をすることができ、論理的に正しい答えも得ることができます!

?- 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 を超える行はありますか?」と尋ねる 1 つの方法があります。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にどう役立つの？さて、次のようなパイプラインをエミュレートする簡単な方法の 1 つ:

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)

その時点で、Sortedinの各要素の出現回数がCountsわかり (確かに よりも少し冗長ですuniq --count)、これらのいずれかが制限を超えていないかどうかを確認する必要があります。awk上記の呼び出しと非常によく似た処理を Prolog で行うには、次のようにします。

maplist(=<(3), Counts)

免責事項: これは、問題に対処する 1 つの方法にすぎません。既に利用可能なツールを知っていれば、多くのコードを自分で書く必要はほとんどないことがわかるので、私はそれを入力することにしました。

編集

もちろん、使用する必要はあり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 に答える