Mutual exclusivity in CLP(FD)

Question

I am writing a Prolog program using clp(fd) and am having difficultly implementing one of my desired constraints.

The output is a list of integers (the length is dependent on the input to another part of the program), where there are certain pairs of predefined numbers which are mutually exclusive, and one number from each pair must be in the output.

An example:

The output is a list of integers, each between 1 and 10. The output must contain either a 3 or a 4, but not both.

---

So far I have the below, which constrains it so that 3 and 4 cannot both be in the output, however it does not ensure that one of them is in the output.

mutual2([A], ME1):-
    (A in 3 #==> ME1) #/\ (#\ A in 4 #<== ME1).
mutual2([A, B| Tail], ME1):-
    (A in 3 #==> ME1) #/\ (#\ A in 4 #<== ME1),
    (B in 3 #==> ME1) #/\ (#\ B in 4 #<== ME1),
    mutual2([B|Tail], ME1).

EDIT:
So running:

[A,B] ins 2..6, A #< B, mutual2([1,2,B,A,5],M), label([A,B]).

Gives:

A = 2,
B = 3,
M = 1 ;
A = 2,
B = 4,
M = 0 ;
A = 2,
B = 5,
M in 0..1 ;
A = 3,
B = 5,
M = 1 ;
A = 4,
B = 5,
M = 0 ;

But I do not want A=2, B=5, M in 0..1 to be a valid output, as neither A nor B are 3 or 4.

Disarmament

Are you also intending to constrain the sequence to exactly 5 integers? – Wale

No, the length of the output is based on a variable input. – Disarmament

What about ExprA #<==> #\ ExprB? – Apochromatic

First of all state that A in 3..4 etc – Apochromatic

Yes, this is specifically about the mutual exclusivity and ensuring one value out of a pair is present. The input would be something like: [A,B] ins 2..6, mutual2([1,2,A,B,5],M), label([A,B]). – Disarmament

Answer 1

I would probably use a combination of CLP(FD) and a DCG since we're dealing with sequences.

Here's an implementation which recognizes sequences containing exactly one 3 or one 4:

:- use_module(library(clpfd)).

one_of_3_4 --> no_3_4, [3], no_3_4.
one_of_3_4 --> no_3_4, [4], no_3_4.

no_3_4 --> [].
no_3_4 --> [X], { X in 1..2 \/ 5..9 }.

This yields something like this:

2 ?- phrase(one_of_3_4, L), label(L).
L = [3] ;
L = [3, 1] ;
L = [3, 2] ;
L = [3, 5] ;
L = [3, 6] ;
L = [3, 7] ;
L = [3, 8] ;
L = [3, 9] ;
L = [1, 3] ;
L = [2, 3] ;
L = [5, 3] ;
L = [6, 3] ;
L = [7, 3] ;
L = [8, 3] ;
L = [9, 3] ;
...

This is not a complete solution to the original problem, but should give an idea for how to approach it in a transparent manner.

---

If you don't want to use a DCG, here is another approach which first specifies a list of single digits other than 3 or 4, then inserts a 3 or a 4 anywhere in the list (SWI Prolog):

:- use_module(library(clpfd)).

one_of_3_4(L) :-
    length(L1, _),
    L1 ins 1..2 \/ 5..9,
    ( select(3, L, L1)
    ; select(4, L, L1)
    ).

This can then be called as follows:

2 ?- one_of_34(L), label(L).
L = [3] ;
L = [4] ;
L = [3, 1] ;
L = [3, 2] ;
L = [3, 5] ;
L = [3, 6] ;
L = [3, 7] ;
L = [3, 8] ;
L = [3, 9] ;
L = [1, 3] ;
L = [2, 3] ;
L = [5, 3] ;
L = [6, 3] ;
L = [7, 3] ;
L = [8, 3] ;
L = [9, 3] ;
L = [4, 1] ;
L = [4, 2] ;
L = [4, 5] ;
L = [4, 6] ;
L = [4, 7] ;
L = [4, 8] ;
L = [4, 9] ;
L = [1, 4] ;
L = [2, 4] ;
L = [5, 4] ;
L = [6, 4] ;
L = [7, 4] ;
L = [8, 4] ;
L = [9, 4] ;
...

---

In response to the comments to this answer, you could create a non-member predicate that applies specifically to the CLP(FD) scenario:

not_member(_, []).
not_member(X, [Y|T]) :- X #\= Y, not_member(X, T).

Or in short, you can abbreviate not_member/2 using maplist/2 as:

not_member(X, L) :- maplist(#\=(X), L).

Using not_member/2, this would work as expected:

mutual(Output, A, B):-
    member(A, Output), not_member(B, Output).
mutual(Output, A, B) :-
    member(B, Output), not_member(A, Output).

And the query yields all of the results:

?- [A,B] ins 2..5, A #< B, mutual([A,B,5],3,4), label([A,B]).
A = 3,
B = 5 ;
A = 2,
B = 3 ;
A = 4,
B = 5 ;
A = 2,
B = 4 ;
false.

Wale

I would prefer to solve this just in CLPFD, and unfortunately I have never used DCG. Also my question specified that the output should contain (for example) 3 or 4, but not both. – Disarmament

@Disarmament You could enter the DCG and do a listing and see the resulting code. That could get you there. Or manually translate the concepts to prologs. – Wale

@Disarmament Sorry I got a little confused on the requirement and have updated my answer again. – Wale

Thank you very much. I believe the same could be done (and generalised) with member/3 (as below), however this is not the clpfd way, it attempts to reify and label the variables rather than constrain their domains, breaking any extra constraint logic. Which is not suitable given the much larger context of my problem as a whole. mutual(Output, A, B):- member(A, Output),\+member(B, Output). mutual(Output, A, B):- \+member(A, Output),member(B, Output). – Disarmament

@Disarmament you mean member/2... Why would member/2 be more generalizable and more "clpfd way" than select/3 (or equivalently, writing an insert/3)? – Wale

Apologies, member/2. Neither of these methods are appropriate to use with CLPFD. – Disarmament

@Disarmament I don't think member/2 or select/3 are particularly contrary to CLP(FD). They are very simple with only list syntax handling and recursion. So you could write them yourself and have a solution that looks purely CLP(FD) or you can use the library, which would do the same thing. – Wale

Well both member/2 and select/3 involve the comparison of values. The idea with clpfd is to express everything in terms of domains, place constraints over the variables and their domains, and finally label the variables. Both of those predicates force variables to prematurely take values. If mutual exclusivity was the entirety of the problem then that would be a valid approach. Otherwise it forces labelling to occur before all constraints have been set up. – Disarmament

@Disarmament CLP(FD) specifically pertain to integers and values. It is certainly about constraints and domains, but also about relative values of integers (e.g., using #> or #<, etc). member/2 and select/3 have no idea about relative numeric values. They only check for unification. Where in the implementation: member(X, [X|_]). member(X, [_|T]) :- member(X, T). is a value comparison made? – Wale

Let us continue this discussion in chat. – Disarmament