We know the problem of "maximal pair matching" (or "maximal matching in bipartite graph) — one of solutions for it is via "maximum flow" algorithms.

But how to solve certain extension of the problem?

Statement

There is a set of 3*N persons, gender-agnostic. We want to split them into N groups of 3.

For every two of them we know the value of mutual happiness of being together in the same group (e.g. we have a diagonally symmetric table 3N by 3N of happiness).

Now, how to maximize happiness? Assuming happiness of a group is sum of 3 pair's happiness in it — and total happiness is the sum over group's happiness.

Any ideas? Iterative random swaps may help in improving happiness but is there precise solution (without brute-force iterating over all possible group arrangements as their number increases pretty fast).

Thanks in advance!