Skip to main content
deleted 269 characters in body
Source Link
aardvark2012
  • 5.4k
  • 1
  • 11
  • 22

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]

enter image description hereenter image description here

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]

This is a fun problem. I suspect there's 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[
      DistanceMatrix[listoflists, 
        DistanceFunction -> (Length@Intersection[#1, #2] &)]
    ]
  ];
  list[[#]] & /@ MaximalBy[
      FindClique[g, Length@listoflists, All], 
    Length@Flatten@listoflists[[#]] &]
  ]

To start with, we can use DistanceMatrix, with DistanceFunction -> (Length@Intersection[#1, #2] &), to get a matrix where element [[i, j]] denotes the length of the intersection between the i^th and j^th subsets. Since we're only actually interested in pairs of subsets that have empty intersections, we can use 1 - Unitize on the distance matrix to get a 1 where a pair has an empty intersection and zero elsewhere.

Row[MatrixForm /@ {
   dm = DistanceMatrix[list, DistanceFunction -> (Length@Intersection[#1, #2] &)],
   1 - Unitize[dm]
   }]

enter image description here

Now we can define our graph, using 1 - Unitize[dm] as the adjacency matrix:

g = AdjacencyGraph[1 - Unitize[dm], VertexLabels -> Automatic]

This is a fun problem. I suspect there 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[
    Partition[
     Boole[Intersection[#1, #2] == {} & @@@ Tuples[listoflists, 2]], 
     Length@listoflists]];
  listoflists[[#]] & /@ 
   MaximalBy[FindClique[g, Length@listoflists, All], 
    Length@Flatten@listoflists[[#]] &]
  ]

The first step is to create an incidence matrix for the relation of having an empty intersection. That is, where element [[i, j]] is 1 if intersection between the i^th and j^th subsets is empty, and a 0 otherwise.

im = Partition[Boole[
  Intersection[#1, #2] == {} & @@@ Tuples[lst, 2]], 
  Length@lst]

enter image description here

Now we can define our graph, using the incidence matrix as the adjacency matrix:

g = AdjacencyGraph[im, VertexLabels -> Automatic]
added 234 characters in body
Source Link
aardvark2012
  • 5.4k
  • 1
  • 11
  • 22

To start with, we can use DistanceMatrix, with DistanceFunction -> (Length@Intersection[#1, #2] &), to get a matrix where element [[i, j]] denoteddenotes the length of the intersection between the i^th and j^th subsets. Since we're only actually interested in subset pairs of subsets that have empty intersections, we can use 1 - Unitize on the distance matrix to get those pairsa 1 where a pair has an empty intersection and zero elsewhere.

Now we can define our graph, using 1 - Unitize[dm] as the adjacency matrix:

In the above graphsgraph, connectedthe nodes correspond to the subsets of list and connected nodes correspond to subset pairs with empty intersection. Therefore, a clique corresponds to a set of subsets such that all intersections are empty.

So now we grab those cliques, pick the ones that havecover the largest unionrange of values (that is, have the longest Flattened length, since there's no doubling up), and then figure out whatget the corresponding subsets actually arefrom list:

To start with, we can use DistanceMatrix, with DistanceFunction -> (Length@Intersection[#1, #2] &), to get a matrix where element [[i, j]] denoted the length of the intersection between the i^th and j^th subsets. Since we're only actually interested in subset pairs that have empty intersections, we can use 1 - Unitize on the distance matrix to get those pairs.

Now we can define our graph:

In the above graphs, connected nodes correspond to subsets with empty intersection. Therefore, a clique corresponds to a set of subsets such that all intersections are empty.

So now we grab those cliques, pick the ones that have the largest union, and then figure out what the corresponding subsets actually are:

To start with, we can use DistanceMatrix, with DistanceFunction -> (Length@Intersection[#1, #2] &), to get a matrix where element [[i, j]] denotes the length of the intersection between the i^th and j^th subsets. Since we're only actually interested in pairs of subsets that have empty intersections, we can use 1 - Unitize on the distance matrix to get a 1 where a pair has an empty intersection and zero elsewhere.

Now we can define our graph, using 1 - Unitize[dm] as the adjacency matrix:

In the above graph, the nodes correspond to the subsets of list and connected nodes correspond to subset pairs with empty intersection. Therefore, a clique corresponds to a set of subsets such that all intersections are empty.

So now we grab those cliques, pick the ones that cover the largest range of values (that is, have the longest Flattened length, since there's no doubling up), and then get the corresponding subsets from list:

Source Link
aardvark2012
  • 5.4k
  • 1
  • 11
  • 22

This is a fun problem. I suspect there's 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.

TL;DR: The Function

maxcover[listoflists_] := Block[{g},
  g = AdjacencyGraph[
    1 - Unitize[
      DistanceMatrix[listoflists, 
        DistanceFunction -> (Length@Intersection[#1, #2] &)]
    ]
  ];
  list[[#]] & /@ MaximalBy[
      FindClique[g, Length@listoflists, All], 
    Length@Flatten@listoflists[[#]] &]
  ]

Then with

list = {{2, 3, 4}, {3, 4, 5}, {3, 4, 5, 6}, {7}, {4, 5, 6, 7}};

we get

maxcover[list]

(* {{{3, 4, 5, 6}, {7}}} *)

as required.

The Explanation

Using a slightly more complex example:

list = DeleteDuplicates@Table[
   Range[#1, #1 + #2] & @@ {s = RandomInteger[{1, 10}], 
     RandomInteger[{0, Min[4, 10 - s]}]},
   8]

(* {{10}, {6, 7, 8, 9, 10}, {4, 5, 6, 7}, {3}, {3, 4}, {3, 4, 5, 6, 7}, {8}} *)

To start with, we can use DistanceMatrix, with DistanceFunction -> (Length@Intersection[#1, #2] &), to get a matrix where element [[i, j]] denoted the length of the intersection between the i^th and j^th subsets. Since we're only actually interested in subset pairs that have empty intersections, we can use 1 - Unitize on the distance matrix to get those pairs.

Row[MatrixForm /@ {
   dm = DistanceMatrix[list, DistanceFunction -> (Length@Intersection[#1, #2] &)],
   1 - Unitize[dm]
   }]

enter image description here

Now we can define our graph:

g = AdjacencyGraph[1 - Unitize[dm], VertexLabels -> Automatic]

enter image description here

In the above graphs, connected nodes correspond to subsets with empty intersection. Therefore, a clique corresponds to a set of subsets such that all intersections are empty.

For example, in that graph there's a four-node clique ({1, 3, 4, 7}) and two three-node cliques ({1, 5, 7} and {1, 6, 7}). And you can easily check that, say,

list[[{1, 5, 7}]]

(* {{10}, {3, 4}, {8}} *)

indeed has no shared elements.

So now we grab those cliques, pick the ones that have the largest union, and then figure out what the corresponding subsets actually are:

cliques = FindClique[g, Length@list, All]
maxcliques = MaximalBy[cliques, Length@Flatten@list[[#]] &]
list[[#]] & /@ maxcliques

(* {{1, 3, 4, 7}, {1, 6, 7}, {1, 5, 7}, {2, 5}, {2, 4}}

   {{1, 3, 4, 7}, {1, 6, 7}, {2, 5}}

   {{{10}, {4, 5, 6, 7}, {3}, {8}}, 
    {{10}, {3, 4, 5, 6, 7}, {8}}, 
    {{6, 7, 8, 9, 10}, {3, 4}}} *)

Which is, of course, the result given by maxcover.

I haven't Sorted the output in any way, or Unionized the returned components. But that's easily done if you need it.