First of all, this is an NP-hard problem - for example, any algorithm that can solve your problem can solve the longest path of a weighted graph problem as follows:
- Each vertex of the graph is human
- Any edge of the graph can be encoded by creating a new hobby shared only by two vertices / faces of the edge
(Perhaps a simpler problem with an NP-complete problem, but I think it will be done).
Skiena will offer a simulated annealing , start with any arrangement and make a random choice. The trick gradually reduces the likelihood that you will agree to a deteriorating change (thus, at first you allow it a little freedom to avoid local optima, but it gradually “cools” and stabilizes in a certain area and makes small refinements). You can also run it several times and support the best solution.
Perhaps you can put together something less complicated in the same vein. I assume that your instances of problems will be small, so you will surely find good solutions if you try many of them (and try to clarify them randomly).
Of course, if your problems are very small, you can simply list all the permutations and find the best location. (If you have n people, make sure you fix someone’s position and only generate permutations for n - 1 people).