安排人们参加应成对进行的事件的算法

Question

每天有一个任务需要两个人执行，并且有一个团队可用。

我们的想法是将每个可能的组合至少分配一次的方式分配给两个不同的人。

此外，理想情况下，任何特定人员的分配时间应尽可能远离前一天分配的时间。

示例:

给定团队:A、B、C、D、E、F

任务的时间表可以是:

Day 1  = A, D
Day 2  = B, E
Day 3  = C, F
Day 4  = A, E
Day 5  = B, F
Day 6  = C, D
Day 7  = A, F
Day 8  = B, D
Day 9  = C, E
Day 10 = E, D
Day 11 = B, E
Day 12 = C, A
...

请注意，同一个字母与上一次的分配有一定的距离。例如，A 被分配到第 1、4、7、12 天，D 被分配到第 1、6、8、10 天。另请注意，所有可能的组合都存在。

目前，我可以为小型团队(6 到 8 人)“手动”组合和排序配对，但对于更大的团队，我无法想出一种算法。

是否有算法可以帮助我？

奖励积分:

在任何时候，一个人都可能变得“不活跃”，因此应该按照规则由其他人代替。

非常感谢!

Answer 1

在Wikipedia 上描述了以下循环调度算法解决了您问题的非奖金部分。这个想法是像这样配对

0 1 2 3 4
5 6 7 8 9

获取对 05 16 27 38 49，然后顺时针旋转除 0 之外的所有内容

0 5 1 2 3
6 7 8 9 4

得到对06 57 18 29 34，然后重复

0 6 5 1 2
7 8 9 4 3

等尽管该算法是为并行循环赛设计的，但它恰好具有这样的特性:由于顺时针旋转不会将任何元素水平移动太远，因此每个特定数字出现之间的间隔相当一致。

为了回答您的附加问题，我建议您尝试使用本地搜索——随机中断不可能让任何提前组合解决方案正常工作。