2

Prolog でリストのモードを見つける方法を教えてください。

私はこれを試しました：

count_elt([], _, 0) :- !. 
count_elt([H|T], H, P) :- 
  count_elt(T, H, P1),
  P is P1 + 1, !. 
count_elt([_|T], E, P) :- count_elt(T, E, P). 

listMode([], 0) :- !. 
listMode([_], 1) :- !. 
listMode([H1|[H2|T]], M) :- 
  count_elt([H1|[H2|T]], H1, C),
  listMode([H2|T], C1),
  C > C1,
  M is C, !. 
listMode([_|[H2|T]], M) :- listMode([H2|T], M).

リスト内の最大出現数のみを返します。しかし、最大の出現 (リスト内の最も頻繁な値) を持つ要素を返す必要があります。

4

3 に答える 3

3

あなたは実際にはかなり近いですcount_elt/3が、もっと非決定論が必要です。count_elt/3要するに、より少ないカットで表現する方法を見つける必要があります。

?- count_elt([a,b,a,a,c,b,d,e,a,f], Y, X).
Y = a,
X = 4.

そして、あなたが取得したいのはこれです：

?- count_elt([a,b,a,a,c,b,d,e,a,f], Y, X).
Y = a,
X = 4 ;
Y = b,
X = 2 ;
Y = c,
X = 1 ;
...
Y = f,
X = 1 ;
false.

そこからsetof/3、論理式またはaggregateライブラリを使用して実行できる最大値を持つソリューションを見つけようとしています。count_elt/3最初に修正して、そこから進みます。

編集：いくつかの一般的な発言：

  • のように書くことができます[H1|[H2|T]]が[H1,H2|T]、これはもう少し明確です。
  • listMode/2おそらく、カウントではなく2番目の位置にアイテムを返す必要があります。listMode/3この手順を実行するにはカウントが必要なので、再帰中に状態を管理するためにorlistMode/5ヘルパーを作成する必要があるでしょう。

編集：ソリューション

@MaDu_LK が解決策を示すことにしたので、これはおそらく宿題ですが、@false の具体化された等式述語を使用して、私のものを共有したいと思いました。

count_of([],         _,  0).
count_of([H|Rest], E, N1) :- 
  equality_reified(H, E, Bool),
  count_of(Rest, E, N0),
  (Bool == true -> N1 is N0 + 1 ; N1 = N0).

frequency(L, I, N) :-
  sort(L, LSorted),
  member(I, LSorted),
  count_of(L, I, N).

mode(L, X) :-
  frequency(L, X, NMax),
  \+ (frequency(L, _, NBigger),
      NMax < NBigger).

これには、いくらか快適なパフォーマンス プロパティがあります。

% MaDu_LK
?- time(get_mode([a,b,c,a,b,c,a,a,b,c,a,d,b], X)).
% 2,811 inferences, 0.000 CPU in 0.000 seconds (100% CPU, 7117429 Lips)
X = a.

% mine
?- time(mode([a,b,c,a,b,c,a,a,b,c,a,d,b], X)).
% 217 inferences, 0.000 CPU in 0.000 seconds (98% CPU, 3144928 Lips)
X = a ;
% 195 inferences, 0.000 CPU in 0.000 seconds (97% CPU, 3305085 Lips)
false.

もう 1 つのソリューションも、リストがマルチモーダルであっても、1 つのモードのみを生成します。

% MaDu_LK
?- get_mode([a,a,b,b,c], X).
X = a.

% mine
?- mode([a,a,b,b,c], X).
X = a ;
X = b ;
false.

思考の糧。

于 2013-02-04T17:26:01.270 に答える
1

コードについて、ダニエルからすでに良いアドバイスを得ています。情報を取得するためのlibrary( aggregate ) 代替方法を示します。

mode_of_list(L, M) :-
    setof(C-E, (member(E, L), aggregate(count, member(E, L), C)), M).

テスト

?- mode_of_list([a,b,a,a,c,b,d,e,a,f],L).
L = [1-c, 1-d, 1-e, 1-f, 2-b, 4-a].
于 2013-02-04T18:03:16.143 に答える
-1

すでに多くの提案があることを願っています。これはあなたのための作業コードです。 

count_elt([],_,0):-!.
count_elt([H|T],H,C):-count_elt(T,H,C1),C is C1+1,!.
count_elt([_|T],E,C):-count_elt(T,E,C).

listMode([],0) :- !.
listMode([_],1) :- !.
listMode([H1|[H2|T]], M) :-count_elt([H1|[H2|T]],H1,C),listMode([H2|T],C1),C > C1,M is C,!.
listMode([_|[H2|T]],M) :- listMode([H2|T],M).

get_mode([H|T],M):-listMode([H|T],K),count_elt([H|T],M,K).
于 2013-02-05T01:34:43.613 に答える