CODEWITHSUNDEEP
graphclassificationpartitiondisjoint-sets
Vertero
Vertero

Reputation: 3

Minimal count of the disjoint set partitioning

I am looking for an efficient algorithm (if there is one) to solve the following problem: Given a set S, whose elements are sets with only two elements. For simplicity, let' s say "two elements" are integers from 1 on. As an example, S can be decribed like: S = {{1, 2}, {2, 3}}. We define R as a radix, which means the integers in the set can not be greater than or equal to R, a bit different from integer 10 in the decimalism. We now define a group G which is merged by the disjoint sets in S with the total count of integers in G less than or equal to R. For example, S = {{1, 2}, {1, 3}, {1, 4}, {2, 3}, {2, 4}, {3, 4}}, R = 4, and then G1 = {{1, 2}, {3, 4}}, G2 = {{1, 3}, {2, 4}}, G3 = {{1, 4}, {2, 3}}. Therefore, in this example, the minimal count of groups is 3.

I want to know if there is any algorithms can efficiently solve this problem with minimal groups. Before posting this problem, I was thinking to transform it into a graph clustering problems, however I find it hard to do with it. I hope I can get some help here, thank you!

Upvotes: 0

Views: 126

Answers (1)

ravenspoint
ravenspoint

Reputation: 20596

I think I must have misunderstood this question, it seems so trivial.

Let

  • N be the number of sets in S
  • M be the minimal number of groups in G1, G2, ... GM

then

M = ( 2 * N ) / R, rounded UP to the nearest whole integer

The rounding up is needed because if 2 * N is not divisible by R, then there will one G group with less than R elements.

e.g for your example: M = 2 * 6 / 4 = 3

Upvotes: 0

Related Questions