Re: atmost and atleast

From: Joachim Schimpf <js10_at_icparc.ic.ac.uk>
Date: Mon 29 Mar 1999 04:34:12 PM GMT
Message-ID: <36FFAB84.6201DD56@icparc.ic.ac.uk>
```Tallys Hoover Yunes wrote:
>
> Hello,
>
>    I'd like to use a modified version of the constraint
> atmost, where, instead of having "at most k elements of
> a list equal to a certain number", I would have "at most
> k elements of a list greater than a certain number".
>
>    Has anyone seen/implemented such a constraint ?
>    Perhaps, starting with the code of the atmost constraint
> it would be easy to implement this new constraint.
>
>    By the way, is there an easy way to implement an
> "atleast" constraint ?
>
> Best regards,
> Tallys Yunes

Here is the code for the occurrences/3 constraint (from the
fd_global library). It should not be too difficult to modify
it for your purposes.

%
%       occurrences(++Value, +List, ?N)
%               The value Value occurs in List N times.
%               Operationally: N gets updated to reflect the number of
%               possible occurrences in the List. List elements may get
%               instantiated to Value, or Value may be removed from
their
%               domain if required by N.
%

:- lib(fd).

occurrences(Value, List, N) :-
var(Value),
suspend(occurrences(Value, List, N), 3, Value->inst).
occurrences(Value, List, N) :-
nonvar(Value),
occurrences(Value, List, N, 0).

occurrences(Value, List, N, Occ) :-
count_vars(Value, List, Occ, Lower, Occ, Upper, VarsWithValue),
% use call_priority to make updates and re-suspend atomic
call_priority(occurrences1(Value, VarsWithValue, N, Lower,
Upper), 2).

occurrences1(Value, VarsWithValue, N, Lower, Upper) :-
Lower #<= N, N #<= Upper,
( N == Lower ->
( foreach(X, VarsWithValue), param(Value) do
dvar_remove_element(X, Value)
)
; N == Upper ->
( foreach(X, VarsWithValue), param(Value) do
X = Value
)
;
suspend(occurrences(Value, VarsWithValue, N, Lower), 4,
[VarsWithValue->any, N->min, N->max])
).

% count_vars(+Value,+Vars,-Lower,-Upper,-VarsWithValue)
% Given an integer value and a list of finite domain variables
% Returns a lower and an upper bound of the times this value
% appear in the variable list as well as the variables which
% may or may not hold this value in the future.
% The lower bound refers to the number of times a variable was
% instantiated to the value.
% The upper bound refers to the number of uninstantiated variables
% which can still take this value.
% The VarsWithValue are the uninstantiated variables...

count_vars(_,[],Lower,Lower,Upper,Upper,[]).
count_vars(Value,[H|T],Lower1,Lower,Upper1,Upper,VarsWithValue) :-
dvar_domain(H,DH),
( dom_check_in(Value,DH) ->
Upper2 is Upper1 + 1,               % Value in domain
( H == Value ->
Lower2 is Lower1 + 1,           % H is instantiated to
Value!
VarsWithValue = MoreWithValue
;
Lower2 = Lower1,
VarsWithValue = [H|MoreWithValue]
),
count_vars(Value,T,Lower2,Lower,Upper2,Upper,MoreWithValue)
;
count_vars(Value,T,Lower1,Lower,Upper1,Upper,VarsWithValue)
).

------------------------------------------------------------------------
Joachim Schimpf                /               phone: +44 171 594 8187
IC-Parc, Imperial College     /              mailto:J.Schimpf@ic.ac.uk
London SW7 2AZ, UK           /      http://www.icparc.ic.ac.uk/eclipse
```
Received on Tue Mar 30 10:52:03 1999

This archive was generated by hypermail 2.1.8 : Wed 16 Nov 2005 06:07:04 PM GMT GMT