Перестановка списков с перекрывающимися значениями
Мой брат студент-медик, и он пришел ко мне с проблемой. Он и трое его одноклассников должны чередоваться между двумя больницами, скажем H1 и H2.
H1есть утренняя смена и ночная смена. Утренняя смена самая трудоемкая, поэтому на ней должны работать два человека. Ночную смену может выполнять один человек, тогда этот человек будет отдыхать до конца следующего дня.H2работает только в утреннюю смену и может быть прикрыт одним человеком
Проблема:
Я пытаюсь решить эту проблему, рассматривая ее как перестановку следующих событий:
- Утренняя смена H1 (
H1_M) - H1 ночная смена (
H1_N) - Сдвиг H2 (
H2) - День отдыха (
R)
Эти события будут иметь следующие ограничения:
- Никаких 24-часовых смен, поэтому
H1_Nне может следоватьH1_M - День отдыха всегда следует за ночной сменой, поэтому
Rвсегда идет послеH1_N - 1 ученик всегда в выходной, кроме первого дня, иначе решения нет
Проблема заключается в том, как создать 4 расписания, по одному для каждого учащегося, которые удовлетворяют двум вышеуказанным требованиям.
Попытка решения:
Я создал последовательности событий, которые следуют правилам, установленным выше,
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]))
Проблема в том, что я не знаю, как мне сгенерировать 4 списка, в которых 2 из них перекрываются во время утренней смены H1_M на каждый день. Если кто-нибудь может дать мне какие-либо указатели, я и мой брат были бы очень признательны, спасибо
Я думал то же самое, но мне было любопытно, смогу ли я найти решение проблемы на питоне. Я также спрошу это в математическом стеке
Я понимаю ограничения, но какова цель? Ограничение — это правило, такое как «Если у человека p ночная смена днем x, то p выходной день x+1». Однако что вы пытаетесь оптимизировать? Вы хотите, чтобы больницы всегда были укомплектованы персоналом? Вы хотите свести к минимуму количество дней, пока каждый студент-медик не поработает в обеих больницах? Свести к минимуму количество ночных смен / увеличить количество сна? Вы хотите максимизировать справедливость (никто не имеет больше ночных смен, чем кто-либо другой) Какова именно цель?
Может ли студент-медик работать в две смены в один день? То есть может ли «Сара» (вымышленное имя) работать и в дневную, и в ночную смену в один и тот же день?
Разрешено ли студенту-медику работать в одной больнице все время, или ему действительно нужно чередоваться? Имеет ли значение, сколько они вращаются / как часто? например Джо работает в больнице №1 20% времени, а в больнице №2 80% времени? Должно быть 50 на 50?
В ограничении, например, для каждой больницы H должен существовать день в следующие 3 месяца, когда Джо работает в больнице H? Или ограничение состоит в том, что Джо должен проводить одинаковое количество времени в каждой больнице (настолько равное, насколько это возможно)?
Кажется разумным, что вы можете позволить студентам-медикам работать в ночную смену каждый день вместо выходных, если никто не работает в последовательные (спина к спине) смены. Например, вы можете работать в дневную смену, дневную смену, дневную смену, дневную смену каждый день, но не в дневную смену, а затем в следующую ночную смену или в ночную смену, а затем в следующую дневную смену. ночная смена каждую ночь может быть прекрасной, если вы никогда не работаете в дневную смену
Ответы 1
Назовем людей p1, p2, p3 и p4.
Я буду нумеровать смены s1, s2, s3, s4, s5, ...
Номера смен указаны в хронологическом порядке.
четные смены - ночные смены.
нечетные смены - дневные смены.
+----+-------+
| s1 | DAY |
+----+-------+
| s2 | NIGHT |
+----+-------+
| s3 | DAY |
+----+-------+
| s4 | NIGHT |
+----+-------+
| s5 | DAY |
+----+-------+
| s6 | NIGHT |
+----+-------+
Это звучит как:
- В каждую ночную смену нам нужен 1 студент-медик.
- В каждой дневной смене должно быть 3 студента-медика.
- Люди не могут работать посменно. Математически говоря, это означает, что для любого целого числа
aи любого целого числаbесли необходимо, чтобы человекp(a)работал в сменуs(b), то необходимо, чтобы человекp(a)не работал в сменуs(b+1)(т.е. человекp(a)не может работать в сменуs(b+1)).
Вначале нам все равно, в какой больнице работает каждый человек. После того, как мы выясним, кто будет работать в каждую смену, мы сможем решить, в какую больницу отправить каждого человека.
Кто-то собирается работать в первую ночную смену. Неважно, кто. Выберите человека p1 произвольно.
+-------+-------+--------+
| SHIFT | DAY | PEOPLE |
| | OR | |
| | NIGHT | |
+-------+-------+--------+
| s1 | DAY | ??? |
+-------+-------+--------+
| s2 | NIGHT | p1 |
+-------+-------+--------+
| s3 | DAY | |
+-------+-------+--------+
| s4 | NIGHT | |
+-------+-------+--------+
| s5 | DAY | |
+-------+-------+--------+
| s6 | NIGHT | |
+-------+-------+--------+
Предположительно, вы не хотите, чтобы студенты-медики работали посменно. Итак, p1 обязательно не должна работать смена s1.
В дневную смену требуется 3 человека s1. В дневную смену всего 3 человека на выбор s1
+-------+-------+------------+
| SHIFT | DAY | PEOPLE |
| | OR | |
| | NIGHT | |
+-------+-------+------------+
| s1 | DAY | p2, p3, p4 |
+-------+-------+------------+
| s2 | NIGHT | p1 |
+-------+-------+------------+
| s3 | DAY | |
+-------+-------+------------+
| s4 | NIGHT | |
+-------+-------+------------+
| s5 | DAY | |
+-------+-------+------------+
| s6 | NIGHT | |
+-------+-------+------------+
Правило состояло в том, что если p1 работал в смену s2, то p1 не работал в смену s3.
+-------+-------+------------+
| SHIFT | DAY | PEOPLE |
| | OR | |
| | NIGHT | |
+-------+-------+------------+
| s1 | DAY | p2, p3, p4 |
+-------+-------+------------+
| s2 | NIGHT | p1 |
+-------+-------+------------+
| s3 | DAY | not(p1) |
+-------+-------+------------+
| s4 | NIGHT | |
+-------+-------+------------+
Это проблема. Если p1 не может работать в смену s3, то у нас есть только один выход:
+-------+-------+----------+------------+
| 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 |
+-------+-------+----------+------------+
Я думаю, что студенты-медики должны сменить больницу, в которой они работают. Человек p1 не должен работать в ночную смену в больнице №1 каждую ночь.
Как часто их приходится выключать?
Предположим, каждый студент-медик записывает, сколько смен он отработал в каждой больнице. Неужели они не могут работать во вторую смену в одной больнице, пока не отработают хотя бы одну смену во всех других больницах?
Если студентам-медикам не разрешается оставаться в одной и той же больнице все время, то работа в две смены неизбежна.
Я разработал график, который кажется приемлемым.
Каждый раз, когда вы работаете две смены подряд, вы получаете следующие две смены подряд для восстановления.
+-------+-------+----------+--------+--------+--------+--------+
| 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 |
+-------+-------+----------+--------+--------+--------+--------+
Пустые места в таблице на самом деле легко заполнить.
За двойной сменой нельзя следовать или продолжать work, иначе это будет тройная смена.
+--------------+------------------------------+
| single-shift | snooze-work-snooze |
+--------------+------------------------------+
| double-shift | snooze-work-work-snooze |
+--------------+------------------------------+
| triple-shift | snooze-work-work-work-snooze |
+--------------+------------------------------+
Везде, где вы видите work-work в таблице, вставьте snooze перед ним и snooze после него.
Ниже приведена полностью заполненная таблица:
╔═══════╦═══════╦══════════╦════════╦════════╦════════╦════════╗
║ 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 ║
╚═══════╩═══════╩══════════╩════════╩════════╩════════╩════════╝
Вы можете чередовать тех, у кого ночная смена:
╔═══════╦═══════╦═════════╦══════╦══════╦══════╦══════╗
║ 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 ║ ║ ║ ║ ║
╚═══════╩═══════╩═════════╩══════╩══════╩══════╩══════╝
Предположим, что никто не должен работать в дневную смену сразу после работы в ночную смену. Затем мы можем заполнить остальную часть таблицы:
╔═══════╦═══════╦═════════╦════════╦════════╦════════╦════════╗
║ 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 ║
╚═══════╩═══════╩═════════╩════════╩════════╩════════╩════════╝
К сожалению, если 1 или 4 человека откладывают смену после ночной смены, вам нужно 3 человека для дневной смены, и только 3 доступны. Выбора, кто будет работать в дневную смену в этот день, не так много.
╔═══════╦═══════╦═════════╦════════╦════════╦════════╦════════╗
║ 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 ║
╚═══════╩═══════╩═════════╩════════╩════════╩════════╩════════╝
ПОЛНОСТЬЮ ЗАПОЛНЕННАЯ ТАБЛИЦА:
╔═══════╦═══════╦═════════╦════════╦════════╦════════╦════════╗
║ 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 ║
╚═══════╩═══════╩═════════╩════════╩════════╩════════╩════════╝
Спасибо, это потрясающий ответ, и ваша конструкция гораздо более прямолинейна. Спасибо!
Это скорее математическая задача, чем программная, но, конечно же, вы можете просто перебрать все возможные комбинации, чтобы проверить, удовлетворяет ли это вашим требованиям.