为成对工作的人安排班次

Question

我会安排轮班的方式，人们工作成对。

1. 主要的限制因素是，每个人都不应不时与他在上一班工作过的人一起工作。
2. 换班的时间没有限制，我只需要一天一双。

例如，如果{A，B。F)代表人们

第一天:第一天:第二天:第三天:第四天: A-B <-错误，因为是这样(1.)被违反

我的解决办法是：

定义一个适应度函数T，如果A今天工作，T(A)等于0，如果A在c天前最后一次工作，则T(A)=c。

这些步骤将是：

1. 随机化对(明显尊重斜交)
2. 创建一个新的对(i，j)：取具有最高适配度的元素( person) i和具有T(j)!=T(i)的第二高适配值的元素j。(为了避免每次都有不同的一对)
3. 更新

有更好的方法来解决问题吗？文学中有类似的东西，我可以参考吗？比如类似的问题？护士的问题和这个类似吗？

谢谢。

Answer 1

您的问题没有明确说明，导致了一些琐碎的解决方案。例如，选择任意三个人，{A，B，C}，以及调度AB，AC，BC (重复)。

如果你想要一个更公平的解决方案:坚持每天随机选择一对，直到你找到一个可行的配对。最多有N个不可行对和N(N-1)/2可能对.

有一种方法可以做到：

import random

def schedule(folk):
    excluded = dict((p, None) for p in folk)
    while True:
        while True:
            a, b = random.sample(folk, 2)
            if excluded[a] != b and excluded[b] != a:
                break
        excluded[a], excluded[b] = b, a
        yield a, b

for a, b in schedule('ABCDE'):
    print '%s%s' % (a, b),