从一个奇怪的学生列表开始，假设总共21个：
cohort = [0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20]
我想用Python编写一个函数，每天用不同的配对为组项目分配配对。由于我们有奇数名学生，我不希望任何人单独工作，所以我们需要9组2人和1组3人 等等。对的顺序并不重要，所以 我如何用Python编写一个函数来打印类配对的所有可能配置？我想看看每天的所有清单，知道每个人至少合作一次需要多长时间。 我研究了循环调度算法和[(0, 1), (2, 3), (4, 5), (6, 7), (8, 9), (10, 11), (12, 13), (14, 15), (16, 17), (18, 19, 20)]
[(1, 2), (3, 4), (5, 6), (7, 8), (9, 10), (11, 12), (13, 14), (15, 16), (17, 18), (19, 20, 0)]
(0, 1) = (1, 0)和(0, 1, 2) = (2, 1, 0) = (1, 2, 0), etc。itertools.combinations，但还没有找到一个优雅的解决方案来解释奇数创建的3的最终元组。我开始编写下面的函数，从下面的列表中获得所有可能的两个人配对，但我知道这不是朝着正确的方向发展，但我不知道如何为每天制作组列表(也许它们需要是无序的集合？)…def all_pairs(cohort):
result = []
for person1 in range(len(cohort)):
for person2 in range(person1+1,len(cohort)):
result.append([cohort[person1],cohort[person2]])
return result
pairings = all_pairs(cohort)
num_pairs = len(pairings)
print(f"{num_pairs} pairings")
for pair in pairings:
print(pair)
我对所有有效配置的数量感兴趣，我认为不可能全部打印出来。
让我们给所有的配对位置相应的标签，比如
[(A, B), (C, D), (E, F), (G, H), (I, J), (K, L), (M, N), (O, P), (Q, R), (S, T, U)]
我们总是可以给不同的学生贴上不同的标签。例如，以下配置
[(0, 1), (2, 3), (4, 5), (6, 7), (8, 9), (10, 11), (12, 13), (14, 15), (16, 17), (18, 19, 20)]
意思是student 0 → A、student 1 → B等。实际上，任何可能的学生编号重排都会产生一种将学生分组的方法。21名学生共有51090942171709400000种可能性(即21个数字)。(我从这个网站计算出了数字)
2个事实表明：1)秩序在每组中都很重要；2) 组的顺序无关紧要，可以消除一些重复的配置。我的大脑很快就为这种情况产生了一个方程：P(21，18)/2^9/P(10，10)=2291551762。(选择18人进行排列，而其余3人的顺序无关紧要。每个排列都有重复，9组可以翻转顺序。最后，10组的顺序也无关紧要。)
事实上；他们每天都会更换合作伙伴；将在给定学生的第一安排的情况下进一步消除更多配置。我快速得出的方程式是：
{p(21，18)/2^9-9*[p(19，16)/2^8]-p(18，18)-2^9)}/p(10，10)=2091687097。
第二项表示九对中的一对保持不变，第三项表示最后一个三元组保持不变。
总之，第一天你将有2291551762个选项，连续几天有2091687097个选项。
很难对这些有效的配置进行采样。一个天真的蒙特卡罗算法将导致约1e-11的可接受概率。我期待着先进的解决方案。
这是要求程序实现的临界点，但我无论如何都会回答。简单地假设名单中的最后3个人将组成3人小组，然后每天轮换学生名单：
def pairings_on_day(students, day):
# Create today's list by copying the original list of students
bag = students.copy()
pairs = []
# Rotate the list
for _ in range(day):
bag.append(bag.pop(0))
# Remove all 2-person groups from the list
while len(bag) > 3:
pairs.append((bag.pop(0), bag.pop(0)))
pairs.append(tuple(bag))
return pairs
def all_pairings(students):
ret = []
for i in range(len(students)):
ret.append(pairings_on_day(students, i))
return ret
当然，这可以优化很多，但这是一个直观的实现。
首先，让我们攻击问题的理论最小值。你有N个学生，你想知道在所有可能的配对中循环需要多长时间。这是"；简单的"；代数
存在N*(N-1) / 2配对；这是一个众所周知的公式。
每天，你有(N-1)/2对，加上三对，即3对：AB、AC、BC。这是每天总共(N-1)/2 + 3对。
因此，您需要的天数是
ceil( (N*(N-1) / 2) / ((N-1)/2 + 3) )
= ceil( N*(N-1) / (N+5) )
一个快速的估计就说明了这一点。大多数时候，学生与另一个人一起工作；三元组"；天，当他们与两个人一起工作。因此，他们与N-1其他学生一起工作的时间应该不到N-1天。
至于算法，这是你探索的起点：对奇数个团队使用标准的RR(循环)调度(其中BYE是稳定元素)，但随后将空闲团队(学生)添加到相邻的配对中，使其成为三人组。例如，对于7名学生，你的轮换如下：
Rotation Pairs
B 1 2 3 16 25 34 - 7
7 6 5 4
B 7 1 2 75 14 23 - 6
6 5 4 3
B 6 7 1 64 73 12 - 5
5 4 3 2
B 5 6 7 53 62 71 - 4
4 3 2 1
现在。。。如何最好地将孤立子元素分配给一对，从而充分利用三元组？应用这个公式，我们得到了的最小值
ceil(7 * 6 / 12) = 4 days
你能通过以上骑行找到实现这一目标的方法吗？
如果没有，你能使用未列出的3个周期中的一个或两个来使其工作吗？(提示：将上面的第2个或第3个循环替换为第6个)。
我让你从这里拿走。：-)
循环算法在这方面做得很好。对于奇数的参与者，你必须考虑到他们中的一个人每天都会缺席。
def roundRobin(students):
count = len(students)
even = 1-(count&1)
poly = students[even:]
for _ in range(count-even):
pairs = [(students[0],poly[0])]*even
pairs += [(poly[i],poly[count-i-even]) for i in range(1,(count+1)//2)]
yield(pairs)
poly = poly[1:]+poly[:1]
输出：
students = list(range(1,21+1))
for day,pairs in enumerate(roundRobin(students),1):
sitout = set(students).difference(*pairs)
print(day,sitout, *pairs,)
day, sit-out, pairs:
1 {1} (2, 21) (3, 20) (4, 19) (5, 18) (6, 17) (7, 16) (8, 15) (9, 14) (10, 13) (11, 12)
2 {2} (3, 1) (4, 21) (5, 20) (6, 19) (7, 18) (8, 17) (9, 16) (10, 15) (11, 14) (12, 13)
3 {3} (4, 2) (5, 1) (6, 21) (7, 20) (8, 19) (9, 18) (10, 17) (11, 16) (12, 15) (13, 14)
4 {4} (5, 3) (6, 2) (7, 1) (8, 21) (9, 20) (10, 19) (11, 18) (12, 17) (13, 16) (14, 15)
5 {5} (6, 4) (7, 3) (8, 2) (9, 1) (10, 21) (11, 20) (12, 19) (13, 18) (14, 17) (15, 16)
6 {6} (7, 5) (8, 4) (9, 3) (10, 2) (11, 1) (12, 21) (13, 20) (14, 19) (15, 18) (16, 17)
7 {7} (8, 6) (9, 5) (10, 4) (11, 3) (12, 2) (13, 1) (14, 21) (15, 20) (16, 19) (17, 18)
8 {8} (9, 7) (10, 6) (11, 5) (12, 4) (13, 3) (14, 2) (15, 1) (16, 21) (17, 20) (18, 19)
9 {9} (10, 8) (11, 7) (12, 6) (13, 5) (14, 4) (15, 3) (16, 2) (17, 1) (18, 21) (19, 20)
10 {10} (11, 9) (12, 8) (13, 7) (14, 6) (15, 5) (16, 4) (17, 3) (18, 2) (19, 1) (20, 21)
11 {11} (12, 10) (13, 9) (14, 8) (15, 7) (16, 6) (17, 5) (18, 4) (19, 3) (20, 2) (21, 1)
12 {12} (13, 11) (14, 10) (15, 9) (16, 8) (17, 7) (18, 6) (19, 5) (20, 4) (21, 3) (1, 2)
13 {13} (14, 12) (15, 11) (16, 10) (17, 9) (18, 8) (19, 7) (20, 6) (21, 5) (1, 4) (2, 3)
14 {14} (15, 13) (16, 12) (17, 11) (18, 10) (19, 9) (20, 8) (21, 7) (1, 6) (2, 5) (3, 4)
15 {15} (16, 14) (17, 13) (18, 12) (19, 11) (20, 10) (21, 9) (1, 8) (2, 7) (3, 6) (4, 5)
16 {16} (17, 15) (18, 14) (19, 13) (20, 12) (21, 11) (1, 10) (2, 9) (3, 8) (4, 7) (5, 6)
17 {17} (18, 16) (19, 15) (20, 14) (21, 13) (1, 12) (2, 11) (3, 10) (4, 9) (5, 8) (6, 7)
18 {18} (19, 17) (20, 16) (21, 15) (1, 14) (2, 13) (3, 12) (4, 11) (5, 10) (6, 9) (7, 8)
19 {19} (20, 18) (21, 17) (1, 16) (2, 15) (3, 14) (4, 13) (5, 12) (6, 11) (7, 10) (8, 9)
20 {20} (21, 19) (1, 18) (2, 17) (3, 16) (4, 15) (5, 14) (6, 13) (7, 12) (8, 11) (9, 10)
21 {21} (1, 20) (2, 19) (3, 18) (4, 17) (5, 16) (6, 15) (7, 14) (8, 13) (9, 12) (10, 11)
在21天的时间里，每个学生都与其他学生配对。每个学生只有一次被罢课。
如果你不是每天有一个学生坐在外面，而是组成一个3人的小组，你每天将进行12对配对(即9对加上3对)。即使你能神奇地避免在前17天重新配对学生，你也会在最后一天留下一个奇怪的日子，你需要组成6对，把9个学生排除在外，这可能对他们不公平。每天一次静坐的方法更易于管理(也更公平)