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!
I think I must have misunderstood this question, it seems so trivial.
Let
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