I have a spreadsheet in which the leftmost column and topmost row contain 12 names, and the values in the cells inside represent the similarity (on a scale of -1 to 1) between the names in the column and the row.
Image:
My goal is to sort the names into three groups of four such that the average similarity between the names in each group is as high as possible. How can I achieve this?
This is a classic case of similarity clustering, where you must be explicit about what you mean by "similarity." The simplest technique is $k$-means clustering under constraints. A web search will bring up the explicit algorithms.