Equivalent de nvalue/2 de SICStus dans SWIProlog

Question

El SICStus Le manuel de la bibliothèque CLP(FD) dit :

nvalue(?N, +Variables) donde Variables est une liste de variables de domaine avec des limites finies ou des entiers, et N est un nombre entier ou un variable de domaine. Vrai si N est le nombre de valeurs distinctes prises par Variables .

Ceci est particulièrement utile lorsque l'on veut minimiser le nombre de valeurs distinctes dans la solution. Par exemple, si l'on essaie de distribuer des marchandises dans des sacs de différentes tailles et que l'on souhaite minimiser le nombre de sacs.

Existe-t-il un prédicat équivalent (ou un moyen) pour réaliser la même chose en SWI Prolog ?

Answer 1

Après le commentaire de @jschimpf, j'ai repensé l'algorithme.

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

nettoyage supplémentaire

encore une fois, après la note de @jschimpf, j'ai modifié le code : maintenant il est très compact, grâce aux bibliothèques apply et à vous tous.

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

vieille réponse, buggy

ma tentative naïve, basée sur réification :

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

en exécutant votre requête d'exemple :

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

modifier

mon code était un peu pédant, bien sûr il pourrait être plus compact (et clair ?) :

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

notez que findall/3 ne fonctionnera pas, puisque la copie de la variable réifiée D perdrait les contraintes affichées.