044: Steiner triple systems

/*

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