python - 将数组拆分为子数组 5 次，同时在所有子数组中保留唯一的对

Question

背景:我是一名 session 经理，在 session 期间，我需要将参与者分成几组。我虽然使用python，但我很挣扎。

我需要将 70 人分成 10 组，每组 7 人。
另外，我需要将它们拆分 5 次(5 轮)。
在每一轮中，我需要在每个团队中，在此之前的所有轮中都不会有一对在同一团队中在一起。

假设人们是一个数组 [0,1,...,69]并拆分为组实际上是创建大小为 7 的子数组。

一个好的输出将是(例如 2 个完全独特的回合和缺少 3 个回合):

Round 1:
[[0, 1, 2, 3, 4, 5, 6], [7, 8, 9, 10, 11, 12, 13], [14, 15, 16, 17, 18, 19, 20], [21, 22, 23, 24, 25, 26, 27], [28, 29, 30, 31, 32, 33, 34], [35, 36, 37, 38, 39, 40, 41], [42, 43, 44, 45, 46, 47, 48], [49, 50, 51, 52, 53, 54, 55], [56, 57, 58, 59, 60, 61, 62], [63, 64, 65, 66, 67, 68, 69]]

Round 2:
[[0, 9, 18, 27, 35, 44, 53, 62], [1, 10, 19, 36, 45, 54], [2, 11, 20, 28, 37, 46, 55, 63], [3, 12, 29, 38, 47, 64], [4, 13, 21, 30, 39, 48, 56, 65], [5, 22, 31, 40, 57, 66], [6, 14, 23, 32, 41, 49, 58, 67], [15, 24, 33, 50, 59, 68], [7, 16, 25, 34, 42, 51, 60, 69], [8, 17, 26, 43, 52, 61]]

Round 3:
...

Round 4:
...

Round 5:
...

请问有什么帮助吗？
我虽然这在 python 中将是一项简单的任务，但我现在几个小时都无法正确完成。我会很感激 python 代码，但我可以轻松编译和运行它的任何其他语言也很棒。

非常感谢。

Answer 1

同样的方法在 Rust 中运行得更快——完整的项目文件和二进制文件可用 here .
顺便说一下，这个问题有很多不同的名字，一个是“社交高尔夫问题”。最初的问题发表在 1850 年的一些深奥期刊上，称为“柯克兰的女学生问题”。组合数学是一个有趣的问题领域。
我已经解决了这个有趣问题的更多问题，然后回来更新这篇文章。下面的代码是进行分组的主要代码段。
每个参与者对象都维护一个他们的“熟人”列表，这有助于确定他们是否可以加入一个组，等等。该程序可以在任何地方解决问题，从立即到一两分钟不等。平均而言，它不到 5 秒(我有一个旧系统)。在 Pypy3 上运行它要快得多。
这段代码为一轮创建分组。每次 session 尝试都会调用 5 次(或任何参数指定的任何参数)。

def run_round(round_id, participants, groups):
    RAND_CANDIDATE_BIAS  = 4
    num_regroup_attempts = len(participants) * 2
    num_rand_candidates  = groups[0].size

    for participant in participants:
        found = False
        random.shuffle(groups)

        # First attempt to find a group.
        for group in groups:
            if try_join(participant, group):
                found = True
                break

        # If not successful, see if getting other participants (regroup 
        # candidates) to change groups will create an opening for the 
        # participant.
        if not found:
            for _ in range(num_regroup_attempts):
                if not random.randint(0, RAND_CANDIDATE_BIAS):
                    # Grouped acquaintances will try to regroup.
                    acqs       = participant.acquaintances
                    candidates = [a for a in acqs if a.group]
                else:
                    # Randomly selected participants will try to regroup.
                    candidates = random.choices(participants,
                                                k=num_rand_candidates)
                    candidates = [cand for cand in candidates if cand.group]

                random.shuffle(candidates)

                for regroup_candidate in candidates:
                    if change_group(regroup_candidate, groups):

                        # Candidate regrouped, see if there's an opening now.
                        if try_join_any(participant, groups):
                            found = True
                            break
                if found:
                    break

    return mixer.Round(round_id, groups)

下面是程序的输出。每行的第一个数字是组号 - 可以忽略。

Oo>>>>>> Sun Mar  8 20:53:12 2020 <<<<<<oO

Iteration 1 best so far: 1 groupless

[[[ Iteration 2 -- SOLVED!! ]]]

Conference(3,
    Round(1, [
        Group( 1, [ 1, 35, 41, 42, 44, 45, 57]),
        Group( 2, [ 2, 10, 37, 40, 43, 47, 55]),
        Group( 3, [ 3, 15, 31, 36, 62, 63, 68]),
        Group( 4, [ 4,  8, 20, 26, 29, 32, 54]),
        Group( 5, [ 5, 46, 64, 65, 66, 67, 69]),
        Group( 6, [ 6, 17, 22, 23, 27, 39, 53]),
        Group( 7, [ 7, 14, 21, 33, 48, 52, 60]),
        Group( 8, [ 9, 12, 25, 38, 49, 50, 70]),
        Group( 9, [11, 18, 19, 24, 34, 51, 59]),
        Group(10, [13, 16, 28, 30, 56, 58, 61]),
    ]),
    Round(2, [
        Group( 1, [ 1,  5, 10, 15, 51, 52, 70]),
        Group( 2, [ 2, 11, 25, 44, 46, 61, 68]),
        Group( 3, [ 3,  8, 12, 27, 34, 43, 67]),
        Group( 4, [ 4, 39, 41, 48, 55, 58, 65]),
        Group( 5, [ 6, 26, 28, 50, 59, 63, 64]),
        Group( 6, [ 7, 23, 36, 38, 45, 56, 66]),
        Group( 7, [ 9, 14, 16, 20, 22, 37, 42]),
        Group( 8, [13, 18, 33, 35, 54, 62, 69]),
        Group( 9, [17, 21, 24, 29, 31, 47, 49]),
        Group(10, [19, 30, 32, 40, 53, 57, 60]),
    ]),
    Round(3, [
        Group( 1, [ 1, 18, 27, 32, 37, 56, 68]),
        Group( 2, [ 2, 30, 45, 48, 50, 51, 67]),
        Group( 3, [ 3,  5,  6, 29, 38, 44, 60]),
        Group( 4, [ 4,  9, 23, 24, 40, 46, 62]),
        Group( 5, [ 7, 13, 22, 49, 55, 57, 63]),
        Group( 6, [ 8, 10, 25, 31, 33, 41, 59]),
        Group( 7, [11, 12, 15, 20, 35, 58, 66]),
        Group( 8, [14, 17, 19, 54, 61, 64, 70]),
        Group( 9, [16, 21, 26, 36, 43, 53, 65]),
        Group(10, [28, 34, 39, 42, 47, 52, 69]),
    ]),
    Round(4, [
        Group( 1, [ 1, 14, 31, 34, 46, 50, 58]),
        Group( 2, [ 2,  4,  6, 18, 21, 57, 66]),
        Group( 3, [ 3, 23, 26, 51, 55, 61, 69]),
        Group( 4, [ 5,  9, 13, 17, 32, 36, 59]),
        Group( 5, [ 7, 15, 37, 41, 53, 54, 67]),
        Group( 6, [ 8, 11, 40, 42, 56, 65, 70]),
        Group( 7, [10, 20, 27, 28, 49, 60, 62]),
        Group( 8, [12, 24, 30, 33, 39, 44, 63]),
        Group( 9, [16, 19, 35, 38, 47, 48, 68]),
        Group(10, [22, 25, 29, 43, 45, 52, 64]),
    ]),
    Round(5, [
        Group( 1, [ 1, 39, 43, 59, 61, 62, 66]),
        Group( 2, [ 2, 24, 38, 42, 53, 58, 64]),
        Group( 3, [ 3, 11, 16, 32, 33, 45, 49]),
        Group( 4, [ 4, 22, 31, 35, 60, 67, 70]),
        Group( 5, [ 5, 18, 20, 23, 41, 47, 63]),
        Group( 6, [ 6, 30, 36, 46, 52, 54, 55]),
        Group( 7, [ 7, 12, 17, 28, 51, 65, 68]),
        Group( 8, [ 8, 19, 21, 37, 44, 50, 69]),
        Group( 9, [ 9, 10, 29, 34, 48, 56, 57]),
        Group(10, [13, 14, 15, 25, 26, 27, 40]),
    ]))

Oo>>>>>> Sun Mar  8 20:53:13 2020 <<<<<<oO

有更多方法可以改进这种方法。例如，它可以及时返回到较早的轮次并进行参与者组交换以影响未分组成员的 future /当前开放。另外，一个更好的算法来选择重组候选者以及他们应该交换到哪些组会很好。现在它只是随机的；主要基于预感。
应用于柯克曼女学生问题。

Oo>>>>>>>>>>>>> Mon Mar  9 02:13:33 2020 <<<<<<<<<<<<<oO

Iteration 1 best so far: 7 groupless
Iteration 12 best so far: 6 groupless
Iteration 96 best so far: 5 groupless
Iteration 420 best so far: 4 groupless

[[[ Iteration 824 -- SOLVED!! ]]]

Conference(825,
    Round(1, [
        Group( 1, [ 1,  5, 15]),
        Group( 2, [ 2, 10, 14]),
        Group( 3, [ 3,  4,  8]),
        Group( 4, [ 6,  9, 13]),
        Group( 5, [ 7, 11, 12]),
    ]),
    Round(2, [
        Group( 1, [ 1, 11, 14]),
        Group( 2, [ 2,  4, 15]),
        Group( 3, [ 3, 12, 13]),
        Group( 4, [ 5,  6, 10]),
        Group( 5, [ 7,  8,  9]),
    ]),
    Round(3, [
        Group( 1, [ 1,  8, 13]),
        Group( 2, [ 2,  3, 11]),
        Group( 3, [ 4,  9, 10]),
        Group( 4, [ 5, 12, 14]),
        Group( 5, [ 6,  7, 15]),
    ]),
    Round(4, [
        Group( 1, [ 1,  7, 10]),
        Group( 2, [ 2,  6, 12]),
        Group( 3, [ 3,  9, 14]),
        Group( 4, [ 4,  5, 13]),
        Group( 5, [ 8, 11, 15]),
    ]),
    Round(5, [
        Group( 1, [ 1,  2,  9]),
        Group( 2, [ 3,  5,  7]),
        Group( 3, [ 4,  6, 11]),
        Group( 4, [ 8, 10, 12]),
        Group( 5, [13, 14, 15]),
    ]),
    Round(6, [
        Group( 1, [ 1,  4, 12]),
        Group( 2, [ 2,  7, 13]),
        Group( 3, [ 3, 10, 15]),
        Group( 4, [ 5,  9, 11]),
        Group( 5, [ 6,  8, 14]),
    ]),
    Round(7, [
        Group( 1, [ 1,  3,  6]),
        Group( 2, [ 2,  5,  8]),
        Group( 3, [ 4,  7, 14]),
        Group( 4, [ 9, 12, 15]),
        Group( 5, [10, 11, 13]),
    ]))

Oo>>>>>>>>>>>>> Mon Mar  9 02:13:38 2020 <<<<<<<<<<<<<oO

Fifteen young ladies in a school walk out three abreast for seven days in succession: it is required to arrange them daily so that no two shall walk twice abreast.

^^ 是 1850 年的原始组合问题。
我觉得有趣的是，1850 年该问题的解决方案侧重于与几何的相关性以找到可能的组。
回到以前的分组并调整它们以使当前分组更容易的想法是我确实探索过的。结果证明它比我措辞时对该功能的原始描述更简单。在前几轮中移动参与者使用与在当前轮中放置参与者完全相同的功能；它没有任何“时间”方面。这些回合统称为一个更大的网格的一部分。