Как мне составить расписание посещения n-пасторами n-церквей?

Question

Я хочу составить расписание для многих пасторов. Условия:

1. Каждый месяц каждый пастор должен ходить в другую церковь,
2. Пастор не должен ходить в ту же церковь, куда он пришел
3. Через 1 год он должен пойти в 12 разных церквей
4. Существует 13 церквей и 13 пасторов, и каждая церковь принимает только 1 пастора каждый месяц

Я не могу использовать случайные (от 1 до 12), потому что есть шанс, что пастор может пойти в ту же церковь (8,3% вероятности, что он пойдет в ту же церковь).

Я хочу сделать небольшой шанс (около 3% или меньше), что он пойдет в ту же церковь.

Answer 1

Ваши условия не требуют, чтобы следующая церковь для данного пастора была выбрана случайным образом. Не могли бы вы просто пройтись по списку церквей?

То есть назначьте каждому пастору номер 0-12. Присвойте каждой церкви номер 0-12. Первый месяц:

Месяц 0:
пастор-0 -> церковь-0
пастор-1 -> церковь-1
пастор-2 -> церковь-2
...
пастор-н -> церковь-н

В следующем месяце просто увеличьте один из счетчиков (с циклическим изменением)

Месяц 1:
пастор-0 -> церковь-1
пастор-1 -> церковь-2
пастор-2 -> церковь-3
...
пастор-н -> церковь-0

Затем повторите для оставшихся месяцев:

Месяц 3:
пастор-0 -> церковь-2
пастор-1 -> церковь-3
пастор-2 -> церковь-4
...
пастор- (n-1) -> церковь-0
пастор-н -> церковь-1

Есть очень простой цикл для всего этого (O (n)). Если вас это смущает, я предлагаю попробовать цикл на бумаге, скажем, n = 3.

Если случайность является обязательным требованием, обновите ваш вопрос.

РЕДАКТИРОВАТЬ ПО ПАКСУ

Я удаляю свой ответ и голосую с перевесом, так как это O (n), а расширение моего, чтобы обслужить изменения, было бы по крайней мере O (n ^ 2).

Вы все еще можете иметь случайность, превратив индексы значений pastor-0 через pastor-N в массив пасторов, которые были отсортированы случайным образом, так что это решение по крайней мере так же хорошо, как и мое.

КОНЕЦ РЕДАКТИРОВАНИЯ ПАКСОМ

Answer 2

Учитывая, что у вас одинаковое количество пасторов и церквей, вот очень простой алгоритм:

1. Число каждой церкви от 0 до 12

2. Построить массив с элементами от 0 до 12.

3. Выполните перемешивание Кнута (см. Ниже) для массива, создав случайный список перемешанных церквей.

4. Каждый пастор начинает в своей церкви (если у пасторов нет назначенных церквей, просто произвольно нумеруйте пасторов от 0 до 12 и сопоставляйте их с церковью с одинаковым номером). Каждый месяц каждый пастор переходит к следующей церкви в списке. Если они в последней церкви в списке, они идут в первую.

Это дает преимущество в простоте объяснения: просто предоставьте каждому пастору перемешанный список и скажите, с чего начать.

Перестановка Кнута (примерно) такова:

def knuth_shuffle(l):
    for i in range(len(l)):
        j = random.randint(i, len(l))
        l[i], l[j] = l[j], l[i]

Очень важно отметить, что на каждой итерации вы меняете текущий элемент в списке на случайный элемент, выбранный только из тех, у которых не уже выбран. Это гарантирует, что количество возможных перемешиваний точно соответствует количеству перестановок (и, следовательно, что они все имеют одинаковую вероятность), что-то наивное перемешивание основывается на обмене случайными элементами или замене текущего элемента любым элементом из всего списка, не есть.