如何为n个牧师访问n个教堂创建日程安排？

Question

我想为许多牧师制定一个时间表，条件如下：

1. 每个月，每位牧师必须去另一间教堂，
2. 牧师不能去他来过的同一间教堂，
3. 在1年内，他必须去12个不同的教堂，
4. 共有13个教堂和13位牧师，每个教堂每个月只接受1位牧师。

我不能使用随机数(1-12)，因为牧师有可能会去同一间教堂 (8.3% 的概率去同一间教堂)。

我希望将他去同一间教堂的几率降低到很小 (大约 3% 或更少)。

- ferdinand

---

这是作业吗？如果是，请使用作业标签。 - Martin v. Löwis

不是作业，有人让我做这个。 - ferdinand

那个人是计算机科学讲师吗？ - Dónal

什么？？没有牧师轮换的Java库吗 ;) - oz10

Answer 1

您的要求并不要求对于给定牧师的下一个教堂是随机选择的。您可以通过遍历教堂列表来实现。也就是说，为每个牧师分配一个0-12的编号，为每个教堂分配一个0-12的编号。第一个月：

月份0：
牧师0 --> 教堂0
牧师1 --> 教堂1
牧师2 --> 教堂2
...
牧师n --> 教堂n

然后在下一个月，只需递增一个计数器（循环进行）：

月份1：
牧师0 --> 教堂1
牧师1 --> 教堂2
牧师2 --> 教堂3
...
牧师n --> 教堂0

然后重复剩余的几个月：

月份3：
牧师0 --> 教堂2
牧师1 --> 教堂3
牧师2 --> 教堂4
...
牧师（n-1）--> 教堂0
牧师n --> 教堂1

这个过程有一个非常简单的循环（O(n)）。如果您感到困惑，建议使用n=3在纸上进行循环尝试。如果随机性是必要的，请更新您的问题。编辑 BY PAX您仍然可以通过将牧师0到牧师N值作为已经随机排序的牧师数组的索引来实现随机性，因此使这个解决方案至少与我的相同。END EDIT BY PAX

- Michael Haren

---

不错，Pax。你可以通过将牧师随机分配到牧师-0到牧师-12来获得随机性。虽然所有12个月都由一个初始洗牌确定，但它并不感觉随机。这是随机的——类似于纸牌游戏的工作方式。通常在抽牌之间不会洗牌。 - Michael Haren

Answer 2

假设你有相同数量的牧师和教堂，这里是一个非常简单的算法：

1. 给每个教堂编号，从 0 到 12

2. 构建一个包含元素从 0 到 12 的数组。

3. 执行一次 Knuth 洗牌（见下文），生成一个随机洗牌的教堂列表。

4. 每位牧师最初待在自己的教堂里（如果没有分配教堂，只需任意给牧师编号从 0 到 12，并将其与具有相同编号的教堂匹配）。每个月，每位牧师移动到列表中的下一个教堂。如果他们在列表上的最后一个教堂，他们就转到第一个教堂。

这样做的好处是非常容易解释：只需向每位牧师展示打乱的列表，并告诉他们要从哪里开始。

Knuth 洗牌大致如下:

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

非常重要的是要注意，在每次迭代中，您都会将列表中的当前项与仅从尚未选择的元素中选择的随机元素进行交换。这确保了可能的洗牌数量正好匹配排列数量（因此，它们都具有相等的概率），而基于随机交换元素或将当前元素与整个列表中的任何元素交换的简单洗牌则不具备这种性质。

- Arachnid