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