2
$\begingroup$

My raw data is composite, but for simplicity sake let's say they consist of three elements. One might consider a sample set thusly.

[A,a,1]
[A,b,1]
[B,b,1]
[B,b,2]
[C,b,3]
[A,c,3]

I need to create a subset that satisfy two key criteria.

  • All combinations of the two last columns is represented (lower case and numeric)
  • All upper case (first column) is represented at least once.

... in as few rows as possible. The data is not evenly distributed, meaning that e.g 80 percent of the rows in the input data may have b,1. If that was the case, it would be wasteful to include A,b,1 row, because I would have to include A,a,1 as well in order to make sure that a,1 combination is represented.

Though large data, the data is in memory. Accessing and iterating is relatively cheap. The data is static and may be processed over multiple passes .

Language is C#.

I'm not too happy about the title of this question, so if there is any key term that better describes this problem, feel free to comment/edit.

Improve this question
$\endgroup$
5
  • 1
    $\begingroup$ What would be a correct answer in your example? Specifically, I don't understand how you can have a subset that represents the aspects you mention. But overall this sounds like a covering problem that could well be hard. Do you insist on an optimal solution? $\endgroup$
    – Juho
    Commented Apr 10, 2019 at 8:23
  • 1
    $\begingroup$ "Language is C#." In what way is this relevant to the question (since you were only asking about a generic "algorithm")? $\endgroup$
    – dkaeae
    Commented Apr 10, 2019 at 8:56
  • $\begingroup$ In my example case, the correct answer would be to exclude the 2nd row A,b,1. $\endgroup$
    – Tormod
    Commented Apr 10, 2019 at 9:05
  • 1
    $\begingroup$ Your question doesn't have much to do with category theory. $\endgroup$
    – Yuval Filmus
    Commented Apr 10, 2019 at 9:17
  • $\begingroup$ It doesn't? I am not a mathematician, but I thought the two different criterias created two topics that individually could be achieved by reduction (filter). The problem is that the reduction (choosing duplicates to exclude) is affected by the other sub set when they overlap. Since it is a definition and sequence of set operations, I thought it was category theory. $\endgroup$
    – Tormod
    Commented Apr 10, 2019 at 9:39

1 Answer 1

Reset to default
2
$\begingroup$

You can solve this by looking for a maximum cardinality matching in a bipartite graph, then covering remaining vertices arbitrarily.

Make a bipartite graph:

  • In the left part of the graph, make a vertex for every capital letter.
  • In the right part of the graph, make a vertex for every combination of lowercase letter and number.
  • For each record, make an edge (which necessarily goes from a vertex on the left to one on the right) corresponding to the two vertices covered by the record.

Now run an algorithm for finding a maximum cardinality matching in a bipartite graph, such as the Hopcroft-Karp maximum flow algorithm. This picks a subset of edges (records) that together cover the most possible distinct combinations of capital letter and (lowercase letter + number). That is, each chosen record hits both a capital letter, and a (lowercase letter + number) pair that are not hit by any other chosen record.

If the matching saturates (touches) every vertex, you have a "perfect" solution! Otherwise, for each remaining vertex, you need to pick a record incident on that vertex -- it doesn't matter which record you pick, because it definitely won't be incident on any untouched vertices on the other side (if it was, then it would have been included in the matching already).

Improve this answer
$\endgroup$
2
  • $\begingroup$ I had to google that. Yes, this seems to be a bipartite graph (which was a new term for me). Your approach does indeed make sense. And I agree that the vertices left without edges after the matching algorithm can be added arbitrarily because the opposing set will be fully covered. $\endgroup$
    – Tormod
    Commented Apr 10, 2019 at 13:29
  • 1
    $\begingroup$ Glad to hear it :) $\endgroup$
    – j_random_hacker
    Commented Apr 10, 2019 at 13:36

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.