This is a fun problem. I suspect there'sthere are many, very different ways of going about it. Here's a way using graphs. I'll give you the packaged version, and then I'll explain it in a bit more detail. I should note that I haven't tried to optimize this in any way, and don't know how it'll fare with large lists.
maxcover[listoflists_] :=
Block[{g},
g = AdjacencyGraph[
1 - Unitize[Partition[
DistanceMatrix[listoflistsBoole[Intersection[#1,
#2] == {} DistanceFunction& ->@@@ (Length@Intersection[#1Tuples[listoflists, #2]2]], &)]
]
];Length@listoflists]];
list[[#]]listoflists[[#]] & /@ MaximalBy[
FindClique[gMaximalBy[FindClique[g, Length@listoflists, All],
Length@Flatten@listoflists[[#]] &]
]
To start with, we can use DistanceMatrix
, with DistanceFunction -> (Length@Intersection[#1, #2] &)
,The first step is to get acreate an incidence matrix for the relation of having an empty intersection. That is, where element [[i, j]]
denotes the length of theis 1 if intersection between the i^th
and j^th
subsets. Since we're only actually interested in pairs of subsets that haveis empty intersections, we can use 1 - Unitize
on the distance matrix to get a 1
where a pair has an empty intersection and zero elsewherea 0 otherwise.
Row[MatrixFormim /@= {Partition[Boole[
dm = DistanceMatrix[listIntersection[#1, DistanceFunction ->#2] (Length@Intersection[#1,== #2]{} &)],
@@@ 1Tuples[lst, -2]], Unitize[dm]
}]Length@lst]
Now we can define our graph, using 1 - Unitize[dm]
the incidence matrix as the adjacency matrix:
g = AdjacencyGraph[1 - Unitize[dm]AdjacencyGraph[im, VertexLabels -> Automatic]