I am creating an event notification system.
Each event has a user and a subject, such that, 'user did event to the subject'. Now while presenting these the events need to be grouped.
All the events in the same group must either refer to the same user or the same subject and each event must be in exactly one group. Subject to those constraints, a group can contain any number of events, including just one. I want to calculate the grouping that uses the least possible number of groups.
Note that forming one group for each user, or forming one group for each subject does not, in general, give the smallest possible number of groups. Also, the events cannot, in general, all be placed in the same group, as that usually gives a group containing multiple users and multiple subjects, which is forbidden.
If I start from the first event and start putting it in the group with most possible events (acting all greedy), I will end up with a sub-optimal solution.
I could check all possible groupings but that will blow up exponentially ($2^n$ possible groupings for just n events).
How can I go about optimally grouping these events such that most of the events get grouped one way or the other, minimising the total number of groups?
Sample data -
event1 user1 subject1
event2 user2 subject1
event3 user3 subject1
event4 user2 subject2
event5 user3 subject2
event6 user1 subject3
event7 user2 subject4
event8 user2 subject5
event9 user3 subject5
event10 user1 subject5
event11 user4 subject1
event12 user4 subject2