对的所有可能组合+奇数列表中的1个三重组? [英] All possible combination of pairs + 1 triple group from an odd list?

问题描述

从一个奇怪的学生列表开始，比如说总共21个学生:

Starting with an odd list of students, let’s say 21 total:

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人的小组和3个1人的小组>.他们每天都会改变合作伙伴.例如，在第1天和第2天，组将如下所示:

I want use Python to write a function that assign pairs for group projects every day with different pairings. Since we have an odd number of students, I don’t want anyone to be working alone, so we would need to have 9 groups of 2 people and 1 group of 3 people. Every day they would change partners. For example, on day 1 and day 2, the groups would look like this:

[(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)，等等.

And so on. The order of the pairs isn’t important, so (0, 1) = (1, 0) and (0, 1, 2) = (2, 1, 0) = (1, 2, 0), etc.

如何在Python中编写一个函数以打印所有可能的类配对配置?我想查看每天的所有列表，并知道每个人至少要一起工作需要多长时间.

How can I write a function in Python to print all possible configurations for the class pairings? I would like to see all the lists for each day and know how long it will take for everyone to work together at least once.

我研究了轮循调度算法和 itertools.组合，但是还没有找到解决如何解决由奇数组编号创建的最终元组3 的合适方法.我开始编写以下函数以从下面的列表中获取所有可能的两人配对，但是我知道这样做的方向并不正确，但是我不确定如何继续制作组列表(也许他们需要每天都是无序集合吗?)……

I looked into round robin scheduling algorithms and itertools.combinations, but haven't found a graceful solution for how to account for the final tuple of 3 created by the odd group number. I started writing the following function to get all possible two-people pairings from the following list, but I know this isn't quite going in the right direction, but I'm not sure how to proceed with making the list of groups (maybe they need to be unordered sets instead?) for each day…

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)

推荐答案

我对所有有效配置的数量感兴趣，而且我认为不可能全部打印出来.

I am interested in the number of all the valid configurations, and I don't think it is possible to print out all.

让我们为所有配对位置指定相应的标签，例如，

Let us give all the paring positions their corresponding labels, something like,

[(A, B), (C, D), (E, F), (G, H), (I, J), (K, L), (M, N), (O, P), (Q, R), (S, T, U)]

我们总是可以将不同的学生分配给不同的标签.例如，以下配置

We can always assign different students to different labels. For instance, the following configuration

[(0, 1), (2, 3), (4, 5), (6, 7), (8, 9), (10, 11), (12, 13), (14, 15), (16, 17), (18, 19, 20)]

将表示学生0→A ，学生1→B 等.实际上，对学生人数的任何可能的重新排列都会产生一种对学生进行分组的方法.21个学生(即21个数字)总共有51,090,942,171,709,400,000个可能性.(我从此网站中计算出了这个数字)

would mean student 0 → A, student 1 → B, etc. Actually, any possible rearrangement of the student numbers would yield a way to group students. There are totally 51,090,942,171,709,400,000 possibilities for 21 students (i.e. 21 numbers). (I calculated the number from this site)

两个事实:1)顺序在每个组中确实重要；2)组的顺序无关紧要，将消除一些重复的配置.我的大脑很快为这种情况产生了一个方程:P(21，18)/2 ^ 9/P(10，10)= 2,291,551,762.(选择18个人进行安排，而其余3个人的顺序无关紧要.每个安排都有其重复之处，其中9个配对的组可以翻转其顺序.最后，这10个组的顺序无关紧要.)

The 2 facts that 1) order does matter within each group; 2) the order of the groups does not matter, would eliminate some duplicated configurations. My brain quickly produced an equation for this situation: P(21, 18) / 2^9 / P(10, 10) = 2,291,551,762. (Choosing 18 people to get arrangement, while the order of the rest 3 people does not matter. Each arrangement has its duplication, where the 9 paired groups can flip their order. Finally, the order of the 10 groups does not matter.)

他们每天都会更换合作伙伴"这一事实鉴于学生的首次安排，将进一步消除更多配置.我想到的一个快速方程是:

The fact that "Every day they would change partners" would further eliminate more configurations given the first arrangement of the students. A quick equation I came up with is:

{P(21，18)/2 ^ 9-9 * [P(19，16)/2 ^ 8]-P(18，18)/2 ^ 9)}/P(10，10)=2,091,687,097.

{P(21, 18) / 2^9 - 9 * [P(19, 16) / 2^8] - P(18, 18) / 2^9)} / P(10, 10) = 2,091,687,097.

第二项表示九对中的一个保持不变，第三项表示最后一个三元组保持不变.

The second term means one of the nine pairs remains unchanged, and the third term means the last triplet remains unchanged.

总而言之，第一天您将拥有2,291,551,762份期权，而连续两天将拥有2,091,687,097份期权.

In summary, the first day you would have 2,291,551,762 options, with 2,091,687,097 options for the successive days.

很难对这些有效配置进行采样.幼稚的蒙特卡洛算法将导致〜1e-11的接受概率.我期待先进的解决方案.

It is hard to sample these valid configurations. A naïve Monte Carlo algorithm would lead to an accepting probability of ~1e-11. I am looking forward to advanced solutions.

这篇关于对的所有可能组合+奇数列表中的1个三重组?的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！