I have a matrix (pandas dataframe) with different identities where the values denote the distances between two identities:
id1 id2 id3 id4
id1 0 1 3 2
id2 1 0 4 1
id3 3 4 0 2
id4 2 1 2 0
How can I find groups of n samples, where the distances between all identities within the groups are maximized? In other words, for each identity I want to find the group (identity + (n-1) other identities) that have the highest total distance of all pairs in the group.
With n = 3 this would mean I have to check the following groups: (id1, id2, id3), (id1, id2, id4), (id1, id3, id4), (id2, id3, id4). To check a group, all combinations would have to be calculated. For the first group this would mean to check the distances of (id1, id2)=1, (id1, id3)=3 and (id2, id3)=4. The total distance is 8. I need a efficient way to calculate this for all identities since the original dataframe is 9000x9000. Luckily I only have to check for a fraction of the identities but against all possible identities (roughly 400x9000) where n can range from 3 to 8. The brute force attempt with just building the permutations and n=3 would already mean having to check 121,459,503,000 combinations per identity, which is super inefficient.