Question: A teacher friend of mine asked me to cook up a program to help them assign classroom jobs to their students. There are 23 kids and 12 different job types, where some jobs require multiple kids, totaling 23 available positions. Each week they want to randomly assign new jobs to the kids, where no kid does the same job more than once for as long as that is possible.

My thought process was to generate all possible assignments of kids to jobs following this rule, then step through the results one by one. But I am stumped trying to come up with a practical algorithm to generate these assignment combinations.

If anyone has any ideas for solutions, or can let me know I'm chasing an impossible one, I'd appreciate it!  

I've pasted all the jobs and how many kids are needed for each below in case it's helpful.

"Attendance": 1,  

"Table Captain": 4,  

"Teacher's Helper": 2,  

"Board Eraser": 2,  

"Light Switcher": 1,  

"Librarian": 2,  

"Lunch Helper": 1,  

"Equipment Manager": 3,  

"Trash Monitor": 2,  

"Tech Specialist": 1,  

"Paper Passer": 3,  

"Pencil Sharpener": 1

Answer: 
This is a trivial scheduling problem. You have 23 students for 23 slots; your largest equivalence group is 4 (Table Captain). Line them up and assign jobs. Every week, shift the kids over 4 spots. 23 and 4 are relatively prime, so the pattern won't repeat for 23 weeks.

Let's designate the job types with the ten numerals and two special characters; the students can be letters.

```
0 "Attendance": 1,
1 "Table Captain": 4,
2 "Teacher's Helper": 2,
3 "Board Eraser": 2,
4 "Light Switcher": 1,
5 "Librarian": 2,
6 "Lunch Helper": 1,
7 "Equipment Manager": 3,
8 "Trash Monitor": 2,
9 "Tech Specialist": 1,
# "Paper Passer": 3,
$ "Pencil Sharpener": 1

```

Schedule:

```
 job    0 1 1 1 1 2 2 3 3 4 5 5 6 7 7 7 8 8 9 # # # $
week 1  a b c d e f g h i j k l m n o p q r s t u v w
week 2  t u v w a b c d e f g h i j k l m n o p q r s
week 3  p q r s t u v w a b c d e f g h i j k l m n o

```

If you need to mix the students around a bit, so you don't have a pair of students sharing a job from week to week, then shuffle the job rotation. Make sure that no two instances of a job are separated by a multiple of 4. Perhaps:

```
 job    0 # 1 1 1 1 2 5 3 4 7 2 8 5 6 7 3 7 # 8 9 # $
week 1  a b c d e f g h i j k l m n o p q r s t u v w
week 2  t u v w a b c d e f g h i j k l m n o p q r s
week 3  p q r s t u v w a b c d e f g h i j k l m n o

```
Here is a simple greedy algorithm without any guarantees:

Create a [bipartite graph](https://en.wikipedia.org/wiki/Bipartite_graph) where the students are nodes in one set and the task slots are nodes in the other set.

Now we create edges between students and nodes for those assignments that are viable. Initially, those are all. Once we have this graph, we can calculate a random [perfect matching](https://en.wikipedia.org/wiki/Matching_(graph_theory)#Definition). For this, start with a random edge. See if none of the two incident nodes have assignments yet and fix that assignment. If one of the nodes have assignments, go to the next random edge.

This will give you a random assignment. Let's see what happens in the next week:

We need to modify the graph to exclude those edges which would produce a repetition of a task. Once we have removed those edges, we can do the same thing again and calculate a random perfect matching.

Eventually, you will arrive at a configuration where you cannot complete the matching. This can have two reasons: Either you chose the edges in a bad way or the graph does not admit a perfect matching. To remedy the first cause, you can just run the same approach multiple times with different random choices (e.g. ten times). It won't give you certainty, but it reduces the likelihood of bad choices. The second cause is a bit more tricky. This will happen after a couple of weeks when repetitions must occur because we ran out of tasks. To do this, we can add back some of the edges. Which edges to add is very variable and depends on the desired behavior of the system. I would start by adding all edges for tasks that require the most people. Among those, start with the edges for people that had the least amount of repetitions already. Once you added these edges, try to find the perfect matching again. If you are still unsuccessful, add some more edges, try again, and so on.