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.
:- 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] ;
...
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.
If you love us? You can donate to us via Paypal or buy me a coffee so we can maintain and grow! Thank you!
Donate Us With