I had an assignment for the graph theory unit of my data structures course. The problem was given as follows:

Every person in a class has at least one other person that they dislike and will not work with. Form groups so that everyone gets along with their group members. You are not allowed to form more than $k$ groups in total. Given a list of pairs of people who dislike each other, and the number $k$, return a grouping of students if it is possible, otherwise return None.

I have found a way to generalize this problem more succinctly if it helps:

Given a binary relation $R$ on a set $S$, find an equivalence relation $R'$ on the set $S$ such that $R \cap R'=\emptyset$ and the size of the quotient set of $S$ by $R'$ less than $k$.

My attempt was to solve the problem using a DFS on the tree of partitions of $S$. Start with an empty partition then try to insert some person, forming a new "vertex" of the tree. Continue doing this until a leaf is reached, or a state that has already been visited is seen. The problem with this solution is that although it is correct, it is too slow. Cases with 8 groupings can take several minutes to find, and the list of visited states becomes so massive that the program runs out of memory.

def enemyDicc(dislikes):
    result = {}
    for x, y in dislikes:
        if x in result:
            result[x] = {y}

        if y in result:
            result[y] = {x}
    return result

def formGroups(dislikes, max_):
    enemiesOf = enemyDicc(dislikes)
    ppl = list(enemiesOf.keys())
    failed = []

    def findFrom(people, grouping):
        # dont make the same mistakes
        if grouping in failed:
            return None
        if len(grouping) == len(ppl):
            # everyone is in this grouping and we are done
            return grouping
        grp_ids = set(grouping.values())
        # extra param for edge case at start
        num_grps = max(grp_ids, default=0)
        for i, person in enumerate(people):
            # find a group that can take this person
            found = False
            for id_ in grp_ids:
                hater_in_grp = any(enemy in grouping and grouping[enemy] == id_
                                   for enemy in enemiesOf[person])
                if not hater_in_grp:
                    grouping[person] = id_
                    found = True
            # if no one can, try to make a new one
            if num_grps < max_:
                grouping[person] = num_grps + 1
                found = True
            # if not possible move on to next person
            if found:
                # try to build from this grouping
                # without the person
                nxt_grp = findFrom(people[:i]+people[i+1:], grouping)
                # if a valid grouping is found return it
                if nxt_grp:
                    return nxt_grp
                    # otherwise delete the person from the grouping
                    del grouping[person]
                    # move on to the next person
        # if this point is reached there is no valid grouping
        return None

    return findFrom(ppl, {})
  • 1
    $\begingroup$ Sounds like NP-complete to me. $\endgroup$ – John L. Jun 28 '19 at 0:23

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.