I have a problem related (presumably) to set theory and I can't find the name of it. I just want you to name it so I can do some more research.
Given a set $S$of $n$ elements $S= \{s_{1}, s_{2}, s_{3},\dots,s_{n}\}$ where every $s \in S$ has some degree of 'likeness' to each other (I don't know exactly how to express this, see the example).
Find the partition $P$ of size $k$ of $S$ such that every subset in $P$ produces the maximum amount of 'likeness' between every element in $P$.
Here is a worded example:
We are trying to build 2 teams ($k = 2$) of people at the office to work in a project but there are some people who don't get along with their coworkers very well so we asked them to assign a score from 1 to 3 to all of their coworkers being 3 "I'd really like to work with him" and 1 being "I'd rather get fired". We'd like to build the teams such that the 'likeness' in every team is the maximum possible.
Say we have 4 people ($n = 4$) $S = \{Tod,Lydia,Walter,Jesse\}$ and the scores are as following:
\begin{array}{ccc} \space & Tod & Lydia & Walter & Jesse \\ Tod & - & 3 & 2 & 1 \\ Lydia & 3 & - & 3 & 1 \\ Walter& 2 & 3 & - & 3\\ Jesse & 1 & 1 & 3 & -\\ \end{array}
It is clear that the best partition of $S$ is $\{\{Tod,Lydia\},\{Walter,Jesse\}\}$.
It is worth to mention that in the kind of problem I'm trying to model, the matrix representing the relationship between each pair of elements is always symmetric.
Finally, I should mention that I'm trying to find an algorithm to solve this kind of problems (other than finding all the possible subsets, computing the degree and returning the maximum).
Any help would be greatly appreciated.
This is equivalent to a minimum k-cut partitioning problem. When $k=2$, there are several efficient algorithms for solving this, such as Ford-Fulkerson or Karger's algorithm.
To demonstrate why this is equivalent to a graph cut problem, I'll focus on the case $k=2$, but it generalizes to partitions of size $k$. For each pair of employees $i,j \in S$ let $w(i,j)$ be your 'likeness' function. We'll denote the partitions with the sets $A$ and $S\setminus A$. Then the problem is equivalent to maximizing this set function:
$$f(A)= \sum_{i \in A, \ j \in A} w(i,j)+ \sum_{i \in S \setminus A, \ j \in S\setminus A} w(i,j)$$
Now suppose we construct a weighted graph with vertices $S$ and edge weights $w(i,j)$. Then the graph cut function between the set of vertices $A$ and its complement $S\setminus A$ is:
$$ g(A)=\sum_{i \in A, \ j \in S\setminus A} w(i,j)=\sum_{i \in S\setminus A, \ j \in A} w(i,j) $$
However, for any set $A$ the sum of all the $w(i,j)$ can be broken apart like this: $$ \begin{aligned}\sum_{i,j \in S} w(i,j) &= \sum_{i \in A, \ j \in S\setminus A} w(i,j)+\sum_{i \in S\setminus A, \ j \in A} w(i,j) + \sum_{i \in A, \ j \in A} w(i,j) + \sum_{i \in S \setminus A, \ j \in S\setminus A} w(i,j)\\ &=2g(A)+f(A) \end{aligned} $$ In other words, $2g(A)+f(A)$ is constant for all $A$, so maximizing $f$ is the same as minimizing $g$.