/*

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

*/

% 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].