Mutual exclusivity in CLP(FD)
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.
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.
下一篇: CLP（FD）的相互排斥