prolog - 相当于 SWIProlog 中 SICStus 的 nvalue/2

Question

SICStus CLP(FD) 库的手册说:

nvalue(?N, +Variables) where Variables is a list of domain variables with finite bounds or integers, and N is an integer or a domain variable. True if N is the number of distinct values taken by Variables.

当想要最小化解决方案中不同值的数量时，这特别有用。例如，如果有人试图将元素分配到不同尺寸的袋子中，并希望尽量减少袋子的数量。

在 SWI Prolog 中是否有等效的谓词(或方式)来实现相同的功能？

Answer 1

在@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).

旧答案，马车

我天真的尝试，基于 reification :

% 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).

请注意， findall/3 将不起作用，因为具体化变量 D 的副本将丢失已发布的约束。