Happy Triplets
Back to General discussions forum
Interesting problem! I am not sure whether there is an efficient algorithm to find the optimum for larger instances, more thinking required. A purely greedy algorithm is not guaranteed to find a solution:
6 22
5
5 5
4 4 4
4 4 4 1
4 4 4 1 1
I agree. A purely greedy algorithm is very unlikely to find the optimum solution but it is more than sufficient to get a high enough score to satisfy the threshhold for this problem. The greedy algorithm would make a good starting point for a solution using iterative improvements. This is what I had planned but the greedy algorithm on its own was sufficient. I suspect that this problem is similar to the travelling salesman in that you can get very close to an optimum solution but haven't the computing time needed to be certain of having the optimum solution.
Hi Friends! By "greedy" you mean approach of creating groups one by one, picking most mutually-amiable persons each time?
If so, am I right this shouldn't work even in the "dancing pairs" problem?
Yes, greedy means that you always choose the highest scoring triplet among the people that have not been matched yet. If the happiness threshold is chosen too low, then this can produce a valid answer. However, this greedy approach does not guarantee to always find an answer; see my example (the threshold value to exceed should actually be 21 there, not 22).
The dancing pairs problem is essentially maximum bipartite matching, and there are algorithms for that. Greedy generally won't work. A fun approach is to model this as a max flow problem (see problem 193).
My greedy solution works for the Test Data, but not for the example. For the example it finds
8 4 1 5 2 0 7 6 3 with triplet values of 213 203 153 (total 569)
Grae, thanks for this interesting observation. Perhaps we may want to make sure test data never work with greedy approach :)
Some kind person explained the non-existence of "good algorithm" to me on reddit:
If mutual happiness is in {0, 1}, then mutual happiness describes edges of a graph between the N people.
Maximal happiness N is reached when each group of 3 forms a triangle in this graph.
But partitioning a graph into triangles is known to be NP complete.
Therefore your generalised problem too is NP complete.