奇数列表中所有可能的配对组合+1个三元组？

Question

从一张单数学生名单开始，假设总共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人。他们每天都会换搭档。例如，在第1天和第2天，各组的外观如下：

[(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

如何用Python编写函数来打印类对的所有可能配置？我想看看每天的所有清单，知道每个人至少要花多长时间才能一起工作一次

我研究了round robin scheduling algorithms和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)

Answer 1

循环算法在这方面做得相当好。对于一个奇数的参与者，你必须考虑他们中的一个每天都坐在外面。p>

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对，每组3对）。即使你能神奇地避免在前17天重新配对学生，你也会在最后一天有一个奇怪的日子，你需要组成6对，把9个学生排除在外，这可能对他们不公平。每天静坐一次的方法更容易管理（也更公平）

Answer 2

这是一个边缘要求一个程序的实施，但我会回答无论如何。只需假设列表中的最后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

当然，这可以进行大量优化，但这是一个直观的实现

Answer 3

首先，让我们讨论这个问题的理论最小值。你有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其他学生一起工作

至于算法，这里是您探索的起点：对奇数个团队（其中BYE是稳定元素）使用标准RR（循环）调度，然后将空闲团队（学生）添加到相邻的配对中，以形成三元组。例如，对于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个循环）

---

我会让你从这里拿走的。：-）