Group tuples to satisfy constraints
I suggest expressing this as an instance of integer linear programming (ILP).  Express boolean logic operations in zero-one integer linear programming (ILP) might be useful to you in figuring out how to do that.

In particular, introduce zero-or-one variables $x_{n,j}$, which is one if person $n$ is placed into group $j$, or zero otherwise.  You can now express each of your requirements as a linear inequality,  and then use an ILP solver to test for feasibility. Now do binary search (or simple iterative search) over the number of groups, to find the maximum number of groups for which you can find a feasible solution.