Search code examples
pythonpermutationpython-itertools

Permutation of lists with overlapping values

My brother is a medical student and he came to me with a problem. He and 3 of his classmates have to rotate between two hospitals, say H1 and H2.

  • H1 has a morning shift and a night shift. The morning shift is the most demanding one, so two people have to be there for it. The night shift can be covered by one person, this person would then take the rest of the following day off.

  • H2 only has a morning shift and can be covered by a single person

The problem:

I'm trying to solve this problem by looking it as a permutation of the following events:

  • H1 morning shift (H1_M)
  • H1 night shift (H1_N)
  • H2 shift (H2)
  • Rest day (R)

These events would have the following restrictions:

  • No 24 hour shifts, so H1_N cannot follow H1_M
  • A rest day always follows the night shift, so R always goes after H1_N
  • 1 student is always on his rest day except on the first day, otherwise there is no solution

The problem is how to create 4 schedules, one for each student, which fulfill the two requirements above.

Attempted solution:

I've created sequences of events which follow the rules set above,

import itertools

# Possible sequences from the 4 events
seq1 = ['H1_M', 'H1', 'H1_N', 'R']
seq2 = ['H1_N', 'R', 'H1_M', 'H2']
seq3 = ['H1_N', 'R', 'H2', 'H1_M']
seq4 = ['H2', 'H1_N', 'R', 'H1_M']

# All possible iterations
it = list(itertools.permutations([seq1, seq2, seq3, seq4]))

The problem with this is that I don't know how I can generate 4 lists in which 2 of them overlap during the morning shift H1_M for every day. If anyone can give me any pointers me and my brother would greatly appreciate it, thanks

Solution

  • Let us name the people p1, p2, p3, and p4.

    I am going to number the shifts s1, s2, s3, s4, s5, ...

    The shift numbers are chronological.

    even-numbered shifts are night shifts.

    odd-numbered shifts are day shifts.

    +----+-------+
| s1 | DAY   |
+----+-------+
| s2 | NIGHT |
+----+-------+
| s3 | DAY   |
+----+-------+
| s4 | NIGHT |
+----+-------+
| s5 | DAY   |
+----+-------+
| s6 | NIGHT |
+----+-------+

    It sounds like:

    • For each night shift, we want 1 med student
    • For each day shift there must be 3 med students.
    • People cannot work back-to-back shifts. Mathematically speaking, that means that for any whole number a and any whole number b if it is necessary that person p(a) works shift s(b) then it is necessary that person p(a) not work shift s(b+1) (i.e. not possible for person p(a) to work shift s(b+1)).

    In the beginning, we do not care what hospital each person works at. After we figure out who is going to work each shift, we can then decide which hospital to send each person to.

    Somebody is going to work the first night shift. It does not matter who. Pick person p1 arbitrarily.

    +-------+-------+--------+
| SHIFT | DAY   | PEOPLE |
|       | OR    |        |
|       | NIGHT |        |
+-------+-------+--------+
| s1    | DAY   | ???    |
+-------+-------+--------+
| s2    | NIGHT | p1     |
+-------+-------+--------+
| s3    | DAY   |        |
+-------+-------+--------+
| s4    | NIGHT |        |
+-------+-------+--------+
| s5    | DAY   |        |
+-------+-------+--------+
| s6    | NIGHT |        |
+-------+-------+--------+

    Presumably, you do not want the med students to work back-to-back shifts. So, p1 necessarily must not work shift s1.

    We need 3 people for the day shift s1. There are only 3 people to choose from for day-shift s1

    +-------+-------+------------+
| SHIFT | DAY   | PEOPLE     |
|       | OR    |            |
|       | NIGHT |            |
+-------+-------+------------+
| s1    | DAY   | p2, p3, p4 |
+-------+-------+------------+
| s2    | NIGHT | p1         |
+-------+-------+------------+
| s3    | DAY   |            |
+-------+-------+------------+
| s4    | NIGHT |            |
+-------+-------+------------+
| s5    | DAY   |            |
+-------+-------+------------+
| s6    | NIGHT |            |
+-------+-------+------------+

    The rule was that if p1 worked shift s2, then p1 would not work shift s3

    +-------+-------+------------+
| SHIFT | DAY   | PEOPLE     |
|       | OR    |            |
|       | NIGHT |            |
+-------+-------+------------+
| s1    | DAY   | p2, p3, p4 |
+-------+-------+------------+
| s2    | NIGHT | p1         |
+-------+-------+------------+
| s3    | DAY   | not(p1)    |
+-------+-------+------------+
| s4    | NIGHT |            |
+-------+-------+------------+

    That is a problem. If p1 cannot work shift s3, then we only have one choice:

    +-------+-------+----------+------------+
| SHIFT | DAY   | QUANTITY | PEOPLE     |
|       | OR    | OF       |            |
|       | NIGHT | PEOPLE   |            |
+-------+-------+----------+------------+
| s1    | DAY   | 3        | p2, p3, p4 |
+-------+-------+----------+------------+
| s2    | NIGHT | 1        | p1         |
+-------+-------+----------+------------+
| s3    | DAY   | 3        | p2, p3, p4 |
+-------+-------+----------+------------+
| s4    | NIGHT | 1        | p1         |
+-------+-------+----------+------------+

    I think that the med students are supposed to change what hospital they work at. Person p1 is not supposed to do the night shift at hospital #1 every night.

    How often do they have to switch off?

    Suppose each med student writes down how many shifts they have worked at each hospital. Is it the case that they cannot have their second shift at one hospital untill they have completed at least one shift at all of the other hospitals?

    If the med students are not allowed to stay at the same hospital the whole time, then pulling a double-shift is unavoidable.

    I worked out a schedule that seems okay.

    Anytime you are on two consecutive shifts, you get the next 2 consecutive shifts off to recover.

    +-------+-------+----------+--------+--------+--------+--------+
| SHIFT | DAY   | QUANTITY | p1     | p2     | p3     | p4     |
|       | OR    | OF       |        |        |        |        |
|       | NIGHT | PEOPLE   |        |        |        |        |
+-------+-------+----------+--------+--------+--------+--------+
| s1    | DAY   | 3        | work   |        |        | snooze |
+-------+-------+----------+--------+--------+--------+--------+
| s2    | NIGHT | 1        | work   |        |        | snooze |
+-------+-------+----------+--------+--------+--------+--------+
| s3    | DAY   | 3        | snooze | work   |        |        |
+-------+-------+----------+--------+--------+--------+--------+
| s4    | NIGHT | 1        | snooze | work   |        |        |
+-------+-------+----------+--------+--------+--------+--------+
| s5    | DAY   | 3        |        | snooze | work   |        |
+-------+-------+----------+--------+--------+--------+--------+
| s6    | NIGHT | 1        |        | snooze | work   |        |
+-------+-------+----------+--------+--------+--------+--------+
| s7    | DAY   | 3        |        |        | snooze | work   |
+-------+-------+----------+--------+--------+--------+--------+
| S8    | NIGHT | 1        |        |        | snooze | work   |
+-------+-------+----------+--------+--------+--------+--------+

    The blank spots in the table are actually easy to fill in.

    A double-shift cannot be followed or proceeded by work or else it would be a triple-shift.

    +--------------+------------------------------+
| single-shift |      snooze-work-snooze      |
+--------------+------------------------------+
| double-shift | snooze-work-work-snooze      |
+--------------+------------------------------+
| triple-shift | snooze-work-work-work-snooze |
+--------------+------------------------------+

    Everywhere you see work-work in the table, insert a snooze before it and a snooze after it.

    The following is the fully-populated table:

    ╔═══════╦═══════╦══════════╦════════╦════════╦════════╦════════╗
║ SHIFT ║ DAY   ║ QUANTITY ║ p1     ║ p2     ║ p3     ║ p4     ║
║       ║ OR    ║ OF       ║        ║        ║        ║        ║
║       ║ NIGHT ║ PEOPLE   ║        ║        ║        ║        ║
╠═══════╬═══════╬══════════╬════════╬════════╬════════╬════════╣
║ s1    ║ DAY   ║ 3        ║ work   ║ work   ║ work   ║ snooze ║
╠═══════╬═══════╬══════════╬════════╬════════╬════════╬════════╣
║ s2    ║ NIGHT ║ 1        ║ work   ║ snooze ║ snooze ║ snooze ║
╠═══════╬═══════╬══════════╬════════╬════════╬════════╬════════╣
║ s3    ║ DAY   ║ 3        ║ snooze ║ work   ║ work   ║ work   ║
╠═══════╬═══════╬══════════╬════════╬════════╬════════╬════════╣
║ s4    ║ NIGHT ║ 1        ║ snooze ║ work   ║ snooze ║ snooze ║
╠═══════╬═══════╬══════════╬════════╬════════╬════════╬════════╣
║ s5    ║ DAY   ║ 3        ║ work   ║ snooze ║ work   ║ work   ║
╠═══════╬═══════╬══════════╬════════╬════════╬════════╬════════╣
║ s6    ║ NIGHT ║ 1        ║ snooze ║ snooze ║ work   ║ snooze ║
╠═══════╬═══════╬══════════╬════════╬════════╬════════╬════════╣
║ s7    ║ DAY   ║ 3        ║ work   ║ work   ║ snooze ║ work   ║
╠═══════╬═══════╬══════════╬════════╬════════╬════════╬════════╣
║ S8    ║ NIGHT ║ 1        ║ snooze ║ snooze ║ snooze ║ work   ║
╚═══════╩═══════╩══════════╩════════╩════════╩════════╩════════╝

    You can rotate who has the night-shift:

    ╔═══════╦═══════╦═════════╦══════╦══════╦══════╦══════╗
║ SHIFT ║ DAY   ║ NUMBER  ║ p1   ║ p2   ║ p3   ║ p4   ║
║       ║ OR    ║ OF      ║      ║      ║      ║      ║
║       ║ NIGHT ║ PEOPLE  ║      ║      ║      ║      ║
║       ║       ║ WORKING ║      ║      ║      ║      ║
╠═══════╬═══════╬═════════╬══════╬══════╬══════╬══════╣
║ s1    ║ DAY   ║ 3       ║      ║      ║      ║      ║
╠═══════╬═══════╬═════════╬══════╬══════╬══════╬══════╣
║ s2    ║ NIGHT ║ 1       ║ work ║      ║      ║      ║
╠═══════╬═══════╬═════════╬══════╬══════╬══════╬══════╣
║ s3    ║ DAY   ║ 3       ║      ║      ║      ║      ║
╠═══════╬═══════╬═════════╬══════╬══════╬══════╬══════╣
║ s4    ║ NIGHT ║ 1       ║      ║ work ║      ║      ║
╠═══════╬═══════╬═════════╬══════╬══════╬══════╬══════╣
║ s5    ║ DAY   ║ 3       ║      ║      ║      ║      ║
╠═══════╬═══════╬═════════╬══════╬══════╬══════╬══════╣
║ s6    ║ NIGHT ║ 1       ║      ║      ║ work ║      ║
╠═══════╬═══════╬═════════╬══════╬══════╬══════╬══════╣
║ s7    ║ DAY   ║ 3       ║      ║      ║      ║      ║
╠═══════╬═══════╬═════════╬══════╬══════╬══════╬══════╣
║ S8    ║ NIGHT ║ 1       ║      ║      ║      ║ work ║
╠═══════╬═══════╬═════════╬══════╬══════╬══════╬══════╣
║ s9    ║ DAY   ║ 3       ║      ║      ║      ║      ║
╠═══════╬═══════╬═════════╬══════╬══════╬══════╬══════╣
║ s10   ║ NIGHT ║ 1       ║      ║      ║      ║      ║
╚═══════╩═══════╩═════════╩══════╩══════╩══════╩══════╝

    Suppose that nobody has to work a day-shift immediately after working a night-shift. Then, we can fill in the rest of the table:

    ╔═══════╦═══════╦═════════╦════════╦════════╦════════╦════════╗
║ SHIFT ║ DAY   ║ NUMBER  ║ p1     ║ p2     ║ p3     ║ p4     ║
║       ║ OR    ║ OF      ║        ║        ║        ║        ║
║       ║ NIGHT ║ PEOPLE  ║        ║        ║        ║        ║
║       ║       ║ WORKING ║        ║        ║        ║        ║
╠═══════╬═══════╬═════════╬════════╬════════╬════════╬════════╣
║ s1    ║ DAY   ║ 3       ║        ║        ║        ║        ║
╠═══════╬═══════╬═════════╬════════╬════════╬════════╬════════╣
║ s2    ║ NIGHT ║ 1       ║ work   ║        ║        ║        ║
╠═══════╬═══════╬═════════╬════════╬════════╬════════╬════════╣
║ s3    ║ DAY   ║ 3       ║ snooze ║        ║        ║        ║
╠═══════╬═══════╬═════════╬════════╬════════╬════════╬════════╣
║ s4    ║ NIGHT ║ 1       ║        ║ work   ║        ║        ║
╠═══════╬═══════╬═════════╬════════╬════════╬════════╬════════╣
║ s5    ║ DAY   ║ 3       ║        ║ snooze ║        ║        ║
╠═══════╬═══════╬═════════╬════════╬════════╬════════╬════════╣
║ s6    ║ NIGHT ║ 1       ║        ║        ║ work   ║        ║
╠═══════╬═══════╬═════════╬════════╬════════╬════════╬════════╣
║ s7    ║ DAY   ║ 3       ║        ║        ║ snooze ║        ║
╠═══════╬═══════╬═════════╬════════╬════════╬════════╬════════╣
║ S8    ║ NIGHT ║ 1       ║        ║        ║        ║ work   ║
╠═══════╬═══════╬═════════╬════════╬════════╬════════╬════════╣
║ s9    ║ DAY   ║ 3       ║        ║        ║        ║ snooze ║
╚═══════╩═══════╩═════════╩════════╩════════╩════════╩════════╝

    Unfortunately, if 1 or 4 people snoozes the shift following a night shift, you need 3 people for the day shift, and only 3 are available. There is not much choice who works the day shift on that day.

    ╔═══════╦═══════╦═════════╦════════╦════════╦════════╦════════╗
║ SHIFT ║ DAY   ║ NUMBER  ║ p1     ║ p2     ║ p3     ║ p4     ║
║       ║ OR    ║ OF      ║        ║        ║        ║        ║
║       ║ NIGHT ║ PEOPLE  ║        ║        ║        ║        ║
║       ║       ║ WORKING ║        ║        ║        ║        ║
╠═══════╬═══════╬═════════╬════════╬════════╬════════╬════════╣
║ s1    ║ DAY   ║ 3       ║        ║        ║        ║        ║
╠═══════╬═══════╬═════════╬════════╬════════╬════════╬════════╣
║ s2    ║ NIGHT ║ 1       ║ work   ║        ║        ║        ║
╠═══════╬═══════╬═════════╬════════╬════════╬════════╬════════╣
║ s3    ║ DAY   ║ 3       ║ snooze ║ work   ║ work   ║ work   ║
╠═══════╬═══════╬═════════╬════════╬════════╬════════╬════════╣
║ s4    ║ NIGHT ║ 1       ║        ║ work   ║        ║        ║
╠═══════╬═══════╬═════════╬════════╬════════╬════════╬════════╣
║ s5    ║ DAY   ║ 3       ║ work   ║ snooze ║ work   ║ work   ║
╠═══════╬═══════╬═════════╬════════╬════════╬════════╬════════╣
║ s6    ║ NIGHT ║ 1       ║        ║        ║ work   ║        ║
╠═══════╬═══════╬═════════╬════════╬════════╬════════╬════════╣
║ s7    ║ DAY   ║ 3       ║ work   ║ work   ║ snooze ║ work   ║
╠═══════╬═══════╬═════════╬════════╬════════╬════════╬════════╣
║ S8    ║ NIGHT ║ 1       ║        ║        ║        ║ work   ║
╠═══════╬═══════╬═════════╬════════╬════════╬════════╬════════╣
║ s9    ║ DAY   ║ 3       ║ work   ║ work   ║ work   ║ snooze ║
╚═══════╩═══════╩═════════╩════════╩════════╩════════╩════════╝

    FULLY POPULATED TABLE:

    ╔═══════╦═══════╦═════════╦════════╦════════╦════════╦════════╗
║ SHIFT ║ DAY   ║ NUMBER  ║ p1     ║ p2     ║ p3     ║ p4     ║
║       ║ OR    ║ OF      ║        ║        ║        ║        ║
║       ║ NIGHT ║ PEOPLE  ║        ║        ║        ║        ║
║       ║       ║ WORKING ║        ║        ║        ║        ║
╠═══════╬═══════╬═════════╬════════╬════════╬════════╬════════╣
║ s1    ║ DAY   ║ 3       ║ work   ║ work   ║ work   ║ snooze ║
╠═══════╬═══════╬═════════╬════════╬════════╬════════╬════════╣
║ s2    ║ NIGHT ║ 1       ║ work   ║ snooze ║ snooze ║ snooze ║
╠═══════╬═══════╬═════════╬════════╬════════╬════════╬════════╣
║ s3    ║ DAY   ║ 3       ║ snooze ║ work   ║ work   ║ work   ║
╠═══════╬═══════╬═════════╬════════╬════════╬════════╬════════╣
║ s4    ║ NIGHT ║ 1       ║ snooze ║ work   ║ snooze ║ snooze ║
╠═══════╬═══════╬═════════╬════════╬════════╬════════╬════════╣
║ s5    ║ DAY   ║ 3       ║ work   ║ snooze ║ work   ║ work   ║
╠═══════╬═══════╬═════════╬════════╬════════╬════════╬════════╣
║ s6    ║ NIGHT ║ 1       ║ snooze ║ snooze ║ work   ║ snooze ║
╠═══════╬═══════╬═════════╬════════╬════════╬════════╬════════╣
║ s7    ║ DAY   ║ 3       ║ work   ║ work   ║ snooze ║ work   ║
╠═══════╬═══════╬═════════╬════════╬════════╬════════╬════════╣
║ S8    ║ NIGHT ║ 1       ║ snooze ║ snooze ║ snooze ║ work   ║
╠═══════╬═══════╬═════════╬════════╬════════╬════════╬════════╣
║ s9    ║ DAY   ║ 3       ║ work   ║ work   ║ work   ║ snooze ║
╠═══════╬═══════╬═════════╬════════╬════════╬════════╬════════╣
║ s10   ║ NIGHT ║ 1       ║ work   ║ snooze ║ snooze ║ snooze ║
╚═══════╩═══════╩═════════╩════════╩════════╩════════╩════════╝