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 ...