/* 

  Set packing problem in Picat.

  Steven Skiena, The Stony Brook Algorithm Repository
  http://www.cs.sunysb.edu/~algorith/files/set-packing.shtml
  """
  Input Description: A set of subsets S = S_1, ..., S_m of the universal set 
  U = {1,...,n}.
 
  Problem: What is the largest number of mutually disjoint subsets from S?
  """


  This Picat model was created by Hakan Kjellerstrand, hakank@gmail.com
  See also my Picat page: http://www.hakank.org/picat/

*/


import cp.


main => go.


go =>
  data(Data),

  NumSets = Data.length,
  NumElements = Data[1].length,

  
  X = new_list(NumSets),
  X :: 0..1,

  NumNeeded #= sum(X),

  foreach(J in 1..NumElements)
     sum([Data[I,J]*X[I] : I in 1..NumSets]) #= 1
  end,

  % solve($[max(NumNeeded)],X),
  solve(X),

  println(numNeeded=NumNeeded),
  println(x=X),
  SelectedSets= [I : I in 1..NumSets, X[I] = 1],
  println(selectedSets=SelectedSets),

  % show the set assignments for each element
  foreach(I in 1..NumElements)
    printf("%2d in Set %d\n", I, [S : S in SelectedSets, Data[S,I] = 1].first())
  end,

  nl.


%
% data
%

% Note: this happens to have a unique solution with 4 sets needed ,
% namely the sets [1,3,5,7].
data(Data) => 
 Data = 
[
   %  1 2 3 4 5 6 7 8 9 0 1 2  elements
     [1,1,0,0,0,0,0,0,0,0,0,0],      % Set 1
     [0,1,0,0,0,0,0,1,0,0,0,0],      %     2
     [0,0,0,0,1,1,0,0,0,0,0,0],      %     3
     [0,0,0,0,0,1,1,0,0,1,1,0],      %     4
     [0,0,0,0,0,0,0,0,1,1,0,0],      %     5
     [1,1,1,0,1,0,0,0,1,1,1,0],      %     6
     [0,0,1,1,0,0,1,1,0,0,1,1]       %     7
].