I have been trying to come up with a better algorithm that detects conflicts in the scenarios below.
Let's say we have 4 dancers. We pair them up and find out which ones can dance together. So, we have the dancer # combination and whether they can dance together or not.
(1,2) True
(1,3) True
(1,4) False
(2,3) True
(2,4) False
(3,4) False
At the end of the day, I want to know which group of dancers I can group together.
A group can only be formed when all of the dancers within the group can dance with each other AND no dancer outside the group can dance with any dancer in the group.
For example, group A can be formed with dancers {1,2,3} because they call can dance with each other (i.e. (1,2), (2,3), and (1,3) are True) AND no dancer outside the group can dance with them (i.e. 4 is outside the group and (1,4),(2,4),(3,4) are all false).
Now, if we change:
(2,4) -> True
grouping changes quite a bit. I can no longer group 1,2 and 3 together because even though (1,2), (1,3) and (2,3) are all True, there is a dancer (#4) that can dance with 2 (i.e. (2,4) is True).
Now, can we group 1 and 3? No. Even though (1,3) is True, there would be one dancer outside the group that CAN dance with either 1 or 3 (i.e. (2,3) and (1,2) are True).
I came up with an algorithm that simply uses some non-sophisticated logic, but I was wondering if one can frame this problem in terms of a CS or Math problem, and whether something similar has been formally solved already.
If it helps you visualize this, you can draw rectangles or circles where they overlap if they can dance together.