Re: atmost and atleast

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