Equivalent of nvalue/2 from SICStus in SWIProlog

Question

The SICStus manual for the CLP(FD) library says:

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.

This is particularly useful when one wants to minimize the number of distinct values in the solution. For example, if one is trying to distribute stuff into bags of different sizes, and want to minimize the number of bags.

Is there an equivalent predicate (or way) for achieving the same in SWI Prolog?

I don't think so... fd_size/2 returns the number of elements of a domain. For example, X in 0..10, fd_size(X, 11). I'm looking for something that constrains the number of distinct elements in a list of variables. — Hugo Sereno Ferreira
I would expect length(Vs, 3), Vs ins 1..3, nvalue(2, Vs) to exclude as possible answers things like Vs = [3, 3, 3] or Vs = [1, 2, 3], because we are saying that there must be two distinct values. — Hugo Sereno Ferreira

CapelliC CapelliC · Accepted Answer · 2017-01-06T14:22:09

After @jschimpf comment, I've rethought the algorithm.

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

further cleanup

again, after @jschimpf note, I've tweaked the code: now it's very compact, thanks to libraries apply and 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).

old answer, buggy

my naive attempt, based on 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).

running your example query:

?- 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].

edit

my code was a bit pedantic, of course could be more compact (and clear ?):

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

note that findall/3 will not work, since the copy of reified variable D would lose the posted constraints.

Equivalent of nvalue/2 from SICStus in SWIProlog

1 Answers