There are $m$ Reception (R) classes in a school, each contains $n$ students, $m|n$. In September all $mn$ students will be in Primary 1 (P1).
In P1 there will still be $m$ classes each with $n$ students. However, to let students get to know more friends, the classes will be reorganized following rules:
students will be re-orged so that each P1 class has $n/m$ students from each R class
Each student could name $k$ R classmates (I.e. from his/her R class) that he/she would like to sit with in the P1 class. The re-org will try to fulfill as many as possible wishes, while fulfillment rate is named $F$.
e.g. There are $m=5$ R classes, each contains $n=15$ students, altogether there are 75 students. After re-org each P1 class has 3 "old friends" from each R class. Each student names $k=2$ "buddies", so there are $150$ wishes. If the re-org fulfilled 120 wishes, then fulfillment rate $F = 80\%$.
Question:
- In which cases all wishes could be fulfilled?
- Is there a good algorithm to re-org?
- if the wishes are cast randomly, what is the expectation of $F$?
Answer to Question $1$ only.
As @saulspatz pointed out, the various classes don't interfere with one another. So we just need to consider a single class of $n$ students. Represent them as an $n$-node directed graph $G$, where directed edge $(u,v)$ means student $u$ wishes to be in the same future class as student $v$. Thus each node (student) $u$ has out-degree $k$.
Now consider the undirected graph $G'$ where edge $\{u,v\} \in G'$ iff $(u,v) \in G$ or $(v,u) \in G$. Consider a connected component $C$. Clearly, every wish of everyone in $C$ is respected iff every node (student) $c \in C$ is placed in the same future class.
Now consider all the connected components $C_1, C_2, ..., C_k$ and their sizes (no. of nodes/students) $|C_1|, |C_2|, ..., |C_k|$. Every wish of everyone can be respected iff there is a way to partition these $k$ components into $m$ subsets $S_1, ..., S_m$ s.t. for every subset the sum of the component sizes $= n/m$, i.e.,
$$\forall i \in \{1, 2, ..., m\}: \sum_{C_j \in S_i} |C_j| = n/m$$
Remarks for Question $2$: we are trying to color the $n$ nodes of $G$ with $m$ colors, $n/m$ nodes per color, so as to minimize the number of directed edges with different colored endpoints. The direction of the edge doesn't really matter[*] and we can equivalently consider the undirected graph as long as we allow $2$ edges between $u,v$ if each wishes for the other (or use edge weight $2$ and consider a weighted minimization). Sadly, I have not much idea how to solve this.
[*] A curious design choice since a 5-6-year-old kid who, for the greater good, ends up with none of his/her preferences will probably cry. :)