Download
/*
Steiner triplets in Picat.
http://www.probp.com/examples/clpset/steiner.pl
"""
The ternary Steiner problem of order n is to find n(n-1)/6 sets of elements
in {1,2,...,n} such that each set contains three elements and any two
sets have at most one element in common.
For example, the following shows a solution for size n=7:
{1,2,3}, {1,4,5}, {1,6,7}, {2,4,6}, {2,5,7}, {3,4,7}, {3,5,6}
Problem taken from:
C. Gervet: Interval Propagation to Reason about Sets: Definition and
Implementation of a PracticalLanguage,
Constraints, An International Journal, vol.1, pp.191-246, 1997.
"""
Note: This model uses arrays of booleans as an representation of sets.
Model created by Hakan Kjellerstrand, hakank@gmail.com
See also my Picat page: http://www.hakank.org/picat/
*/
% Licenced under CC-BY-4.0 : http://creativecommons.org/licenses/by/4.0/
import cp.
main => go.
go =>
N = 9,
steiner(N,Steiner),
writeln(Steiner),nl.
steiner(N,Steiner) =>
% number of sets
Nb = (N * (N-1)) // 6,
Sets = new_array(Nb,N),
SetsList = vars(Sets),
SetsList :: 0..1,
% atmost 1 element in common
foreach({S1,I} in zip(Sets.to_list(),1..Nb))
S1List = S1.to_list(),
3 #= sum(S1List), % cardinality
foreach({S2,J} in zip(Sets.to_list(),1..Nb))
if I > J then
union_card(S1List,S2.to_list(),Common),
Common #=< 1
end
end
end,
solve([constr,down],SetsList),
% convert to set representation
Steiner = [Res : SS in Sets, boolean_to_set(SS,Res)].
%
% number of common elements in two "sets"
%
union_card(S1,S2,CardCommon) =>
CardCommon #= sum([(SS1 + SS2 #= 2) : {SS1,SS2} in zip(S1,S2)]).
%
% convert a list of boolean to a "set"
%
boolean_to_set(List,Set) =>
Set = [I : {C,I} in zip(List.to_list(), 1..List.length), C = 1].