0
$\begingroup$

I'm trying to figure out an algorithm for this specific problem.

The problem: I have N people (say 60 but could be far more) that I want to organize into groups of 4 on a monthly cadence.

The constraints:

  1. Each month, groups should contain people that haven't been grouped before (until they've been in a group with everyone)
  2. Since these people all work for the same company, people in a group should never be on the same team (as in, reporting to the same manager).
$\endgroup$

1 Answer 1

2
$\begingroup$

Here's one potential approach. First, partition all people who work at the company according to their team. This way, you get sets $T_1, \ldots, T_k$. Now, for every 4-tuple $(a,b,c,d)$, with $1 \leq a < b < c < d \leq k$, you can enumerate the groups $g_1, \ldots, g_m$ where the first person belongs to $T_a$, the second one to $T_b$, third to $T_c$ and last to $T_d$. Initialize an empty graph $G$ over $n$ nodes, each representing a person, where edges will represent who has been grouped with whom. For each group $g_i$, check if you can actually create it by verifying it's not a $4$-clique in $G$. If you can create it, then print it and add edges between every pair of people in $g_i$.

There might be better approaches, but that will depend on how large you expect $n$ to be, what the team-structure is like, and what properties are you trying to optimize in your algorithm; e.g., minimizing enumeration delay, memory, etc.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.