4

CLP(FD) ライブラリのSICStusマニュアルには次のように書かれています。

nvalue(?N, +Variables)ここVariablesで、 は有限境界または整数を持つドメイン変数のリストでありN、整数またはドメイン変数です。Nが によって取得された個別の値の数である 場合は真ですVariables。

これは、ソリューション内の個別の値の数を最小限に抑えたい場合に特に役立ちます。たとえば、さまざまなサイズのバッグに物を分配しようとしていて、バッグの数を最小限に抑えたい場合。

SWI Prologで同じことを達成するための同等の述語(または方法)はありますか?

4

1 に答える 1

4

@jschimpf のコメントの後、アルゴリズムを再考しました。

nvalue(1, [_]).
nvalue(C, [V|Vs]) :-
    count_equals(V, Vs, E),
    E #= 0 #/\ C #= R+1 #\/ E #> 0 #/\ C #= R,
    nvalue(R, Vs).

count_equals(_, [], 0).
count_equals(V, [U|Vs], E) :-
    V #= U #/\ E #= E1+1 #\/ V #\= U #/\ E #= E1,
    count_equals(V, Vs, E1).

さらなるクリーンアップ

繰り返しますが、@jschimpf のメモの後、コードを微調整しました。ライブラリの apply と yall のおかげで、コードは非常にコンパクトになりました。

nvalue(1, [_]).
nvalue(C, [V|Vs]) :-
    maplist({V}/[U,Eq]>>(Eq#<==>V#=U), Vs, Es),
    sum(Es, #=, E),
    E #= 0 #/\ C #= R+1 #\/ E #> 0 #/\ C #= R,
    nvalue(R, Vs).

古い答え、バグ

具体化に基づく私の素朴な試み:

% nvalue(?N, +Variables)
nvalue(N, Vs) :-
    nvalues(Vs, [], VRs),
    sum(VRs, #=, N).

nvalues([], Acc, Acc).
nvalues([V|Vs], Acc, VRs) :-
    nvalues_(V, Vs, Acc, Upd),
    nvalues(Vs, Upd, VRs).

nvalues_(_V, [], Acc, Acc).
nvalues_(V, [U|Vs], Acc, Upd) :-
    V #\= U #<==> D,
    nvalues_(V, Vs, [D|Acc], Upd).

サンプルクエリの実行:

?- length(Vs, 3), Vs ins 1..3, nvalue(2, Vs), label(Vs).
Vs = [1, 1, 2] ;
Vs = [1, 1, 3] ;
Vs = [1, 2, 1] ;
Vs = [1, 2, 2] ;
Vs = [1, 3, 1] ;
Vs = [1, 3, 3] ;
Vs = [2, 1, 1] ;
Vs = [2, 1, 2] ;
Vs = [2, 2, 1] ;
Vs = [2, 2, 3] ;
Vs = [2, 3, 2] ;
Vs = [2, 3, 3] ;
Vs = [3, 1, 1] ;
Vs = [3, 1, 3] ;
Vs = [3, 2, 2] ;
Vs = [3, 2, 3] ;
Vs = [3, 3, 1] ;
Vs = [3, 3, 2].

編集

私のコードは少し衒学的でしたが、もちろんもっとコンパクトにすることができます（そして明確ですか？）：

nvalue(N, Vs) :-
    bagof(D, X^H^T^V^(append(X, [H|T], Vs), member(V, T), V #\= H #<==> D), VRs),
    sum(VRs, #=, N).

具体化された変数 D のコピーはポストされた制約を失うため、findall/3 は機能しないことに注意してください。

于 2017-01-06T14:22:09.967 に答える