Possible key-terms: combinatorial optimization techniques; simulated annealing; genetic algorithms; Kirkman's schoolgirl problem; Steiner triple systems; orthogonal regrouping.
Background: My class has $10$ students and $3$ tables; naturally, the students are distributed with $3, 3,$ and $4$ seated at the individual tables. On the second day of class, students sat in the same seats as on day one; I asked them to reseat themselves so that they could sit with new people.
Since there are $4$ students at one table and only $3$ total tables, we know by the pigeonhole principle that at least one pair of students will still be seated together after the reseating. In fact, such a reseating (only one pair of students still seated together) is attainable: the students quickly achieved as much!
Foreground: What are the natural notions of mixedness that one uses in similar scenarios for subsequent days? Asking with greater generality, suppose that there are $N$ students with their seats distributed among $k$ tables, each of which contains (on all days) $n_1, \ldots, n_k$ students, respectively, where $\sum n_i = N$.
(In the background case: $N = 10; n_1 = 3, n_2 = 3, n_3 = 4$.)
Question: What sort of literature exists on measuring how mixed up a seating arrangement is (as compared to all previous days), and how does one maximize the mixedness moving forward?
If necessary, I am okay with certain assumptions on the $n_i$; surely they should all be positive, and, at least initially, I am okay with them being assumed equal. (Though this will only be possible if $k$ divides $N$, which is not the case in my class!)
References addressing the general problem or solutions for particular cases (e.g., $10$ students at $3$ tables) would all be welcomed.
This definitely sounds like a variation on Kirkman's schoolgirl problem; the original problem had $N = 15$, $n_{1}=\dots=n_{5}=3$, and it was desired that, for seven days in succession, no two girls were "seated at the same table" twice. For general $N = 3k+3$ (all table sizes $=3$, successive $(1/2)(N-1)$ days), solutions are given by Steiner triple systems admitting a parallelism; similar problems have been looked at for table size 4.
If you are just looking at two days, you can think of having a complete graph on $N$ vertices; now color edges red when kids sit at a table together on the first day, you will get complete graphs of size $n_{1}, \ldots, n_{k}$. For the second day, you want to embed these subgraphs again, reusing as few edges as possible. I'm guessing you will always be able to obtain the theoretical minimum using a greedy algorithm.