Social golfer problem with additional requirement

Question

I need to write a program that sorts people into groups.

To give a little context: The aim of the program is to create an equitable distribution of tasks and people for a school trip. Every day the groups are reshuffled and each group is assigned a task (cleaning, cooking, ...). So far, we have put the groups together randomly by drawing items from a bag. But every year the students complain if they are never in the same group as their friends or if they always have the task "cleaning". So I had the idea to develop a small program that solves this problem by dividing the students into groups where the people and tasks are evenly distributed.

The following specifications are requested:

1. We have a total of x people.
2. The people will be divided into y groups.
3. There are z days. On each day, the groups are mixed so that ideally, after all days, each person has been in a group with every other person at least once. The distribution should be even, i.e. everyone shares a group with every other person about the same number of times.
4. There are as many tasks as there are groups. For each day, each group is assigned one of these tasks. After all days, each person should have had each task about the same number of times.

Now about the algorithm. I think a solution to the "Social golfer problem" (www.mdpi.com/2073-8994/13/1/13) might be a way to sort people into groups. But since there is the additional requirement of Tasks (people equally distributed among all groups), I really don't know how to approach this problem. After a bit of googling "Kirkman's Schoolgirl Problem" and "The Running Dinner Problem" were some other keywords that popped up. Maybe that can be helpful?

If someone has a hint or even a full algorithm I would be very happy! Thank you!

Answer 1

Some thoughts:

• If each student is to do each task at least once, then $z>y$
• For even distribution of tasks, each student should be performing any particular task roughly $\frac{z}{y}$ times
• Due to symmetry, there is likely to be roughly $\frac{x}{y}$ in each group; i.e. performing a specific task on a specific day
• For even distribution of sharing groups, each pair of students should share roughly $\frac{\left(\frac{x}{y}-1\right) z}{x-1}$ groups
• Groups can be formed by grouping together students who have the same task in the same day. So we can just allocate a task to each student each day for the problem.

Though I don't have a solution, here's some (nearly) equivalent problem statements, in case the alternative perspectives are useful. If you can solve any of these, then that solution can be translated into a solution for your original problem.

1. String Matching

Generate $x$ strings of length $z$ from a pool of $y$ characters (allowing repetition) such that:

1. There should be an 'even' number distribution of characters from the pool in each string; i.e. each character occurs either $\left\lfloor \frac{z}{y} \right\rfloor$ or $\left\lceil \frac{z}{y} \right\rceil$ times.
2. Every two strings should have at least one overlap: a matching characters in the same position 2.1 The number of overlaps between any two strings should be roughly the same [Putting this as a sub-condition because if both conditions cannot be satisfied simultaneously, then give preference to the at least one overlap condition]

Each string represents the sequence of tasks that a particular student does through the trip (with position corresponding to day). One solution direction would be to generate all distinct strings where every character occurs either $\left\lfloor \frac{z}{y} \right\rfloor$ or $\left\lceil \frac{z}{y} \right\rceil$ times, then look for an $x$-sized subset that minimizes the gap between the most and least number of overlaps between any two strings, while ensuring least overlap is always non-zero.

2. Arithmetic Modulus

Create a $z \times y$ table. Distribute $x$ students evenly in the first row; i.e. each cell having either $\left\lfloor \frac{x}{y} \right\rfloor$ or $\left\lceil \frac{x}{y} \right\rceil$ students. Number the cells from top to bottom and left to right, so that cell $(i,j)$ is assigned $(i-1)*y + j$, with $(1,1)$ being top-left. Each day, increment each student's position by some value (which can vary depending on the student and the day) such that

1. The student ends up in the next row each day
2. Over the $z$-day trajectory, each student visits every column an even number of times. If $p$ is a student's position, then $(p \mod y) + 1$ gives the column
3. For every pair of students, there is at least one cell where they both visit simultaneously. The number of cells where any pair of students is simultaneously present is roughly even.

If a student is present in cell $(i,j)$, then they are assigned task $j$ on day $i$. For example, starting from $(1,1)$ with value $1$, if you increment position by $y+1$ each day, then you will cycle through all the columns over $y$ days. Though the next increment would cause the student to skip row $y+1$, so a simple constant increment probably won't work.

3. Natural Number Sequences

And because I was in the mood, a more mathematical version of the above.

Construct $x$ natural number sequences $\lbrace p_{i,j} \rbrace_{i=1}^{z}$ for $1 \leq j \leq x$, such that$$ p_{i,j} \in [1, zy] \; \forall \; i,j \\ 1 \leq p_{1,j} \leq y \; \forall \; j \\ y - (p_{i-1,j} \; \text{mod} \; y) + 1 \leq \Delta p_{i, j} \leq 2y - (p_{i-1,j} \; \text{mod} \; y) \quad i \geq 2, \forall j, \quad \Delta p_{i, j} \equiv p_{i,j} - p_{i-1,j} \\ \left\lfloor \frac{z}{y} \right\rfloor \leq \left\vert\left\lbrace i | i \in [1,z], (p_{i,j} \; \text{mod} \; y) + 1 = k \right\rbrace\right\vert \leq \left\lceil \frac{z}{y} \right\rceil \qquad k \in [1,y], \forall j \\ \forall j_1, j_2 \in [1,x], \exists \; i \ni \; p_{i,j_1} \; \text{mod} \; y = p_{i,j_2} \; \text{mod} \; y \\ \left\lfloor \frac{\left(\frac{x}{y}-1\right) z}{x-1} \right\rfloor \leq \left\vert\left\lbrace i | i \in [1,z], p_{i,j_1} \; \text{mod} \; y = p_{i,j_2} \; \text{mod} \right\rbrace\right\vert \leq \left\lceil \frac{\left(\frac{x}{y}-1\right) z}{x-1} \right\rceil \qquad \forall j_1, j_2 \in [1,x] $$

And some other perspectives I haven't fleshed out,

4. Distributing Balls: Distribute $xz$ balls, evenly colored by $x$ colors, into a $z \times y$ grid of boxes such that ...

5. Set of Points: Construct $S \subset [1, x] \times [1, y] \times [1, z]$, with $|S| = xz$, such that ...

6. Graph Theory: Construct a graph with $zy$ vertices and $x(z-1)$ edges, with $z-1$ edges of a different color/weight forming $x$ paths by color/weight, such that ...