4

我想为许多牧师制定一个时间表。条件是：

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

我不能使用随机数（1 到 12），因为牧师有可能去同一个教堂（他去同一个教堂的几率为 8.3%）。

我想让他去同一个教堂的机会很小（大约 3% 或更少）。

4

2 回答 2

12

您的条件不要求随机选择给定牧师的下一个教堂。你不能只遍历教会列表吗？

也就是说，给每位牧师分配一个数字，0-12。为每个教堂分配一个数字，0-12。第一个月：

第0 个月：
pastor-0 --> Church-0
Pastor-1 --> Church-1
Pastor-2 --> Church-2
...
Pastor-N --> Church-N

下个月，只需增加一个计数器（带环绕）

第 1 个月：
pastor-0 --> Church-1
Pastor-1 --> Church-2
Pastor-2 --> Church-3
...
Pastor-N --> Church-0

然后重复剩余的几个月：

第 3 个月：
pastor-0 --> Church-2 Pastor
-1 --> Church-3 Pastor
-2 --> Church-4
...
Pastor-(n-1) --> Church-0 Pastor
-n- -> 教堂-1

所有这些都有一个非常简单的循环（O（n））。如果它让你感到困惑，我建议在纸上尝试使用 n=3 的循环。

如果需要随机性，请更新您的问题。

由 PAX 编辑

我正在删除我的答案并投票赞成这个答案，因为它是 O(n) 并且我的扩展以满足编辑将至少是 O(n^2)。

您仍然可以通过将 pastor-0 到 Pastor-N 值索引到一个随机排序的牧师数组中来获得随机性，从而使这个解决方案至少和我的一样好。

由 PAX 结束编辑

于 2008-12-01T13:31:34.113 回答
1

鉴于您拥有相同数量的牧师和教堂，这里有一个非常简单的算法：

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

  2. 构造一个数组，其中包含元素 0 到 12。

  3. 对阵列执行 Knuth Shuffle（见下文），生成随机打乱的教堂列表。

  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]

值得注意的是，在每次迭代中，您都将列表中的当前项目与仅从尚未选择的那些中选择的随机元素交换。这确保了可能的 shuffle 的数量与排列的数量完全匹配（因此，它们都具有相等的概率），基于交换随机元素或将当前元素与整个列表中的任何元素交换的天真的 shuffle，不要'没有。

于 2008-12-01T13:49:39.083 回答