python - 根据人员列表和他们必须会面的人创建时间表

Question

我有一个人员 ID 列表以及他们应该会见的人，如下所示:

people = [
    [1, [2,3,4]], 
    [2, [1,3,4]], 
    [3, [1,2,4]],
    [4, [1,2,3]]
]
#    ^ person_id
#        ^ list of person to meet

我想安排列表以便每个人在不同的时间段见面，即我想要的输出是

people = [
    [1, [2,3,4]], 
    [2, [1,4,3]], 
    [3, [4,1,2]],
    [4, [3,2,1]]
]
#        ^ ^ ^  timeslot 1,2,3

这意味着 1 必须在第一个时隙中满足 2 并且 3 必须满足 4。 ...

对于人数少的人，我可以手工完成。我想知道当我有一个更大的列表时是否有办法解决这个问题。我将 CSV 文件附在更大的人 ID 和他们必须见的人 here .

注意 不确定这是否适合 Stack Overflow，我可以在其他地方询问。欢迎提出建议。

Answer 1

已更新，以防万一有人从 Google 偶然发现这里时更加清晰。内容几乎相同。

根据您的数据设置方式，每次 session 在某种意义上都“属于”个人。以第 1 个人为例，他们需要与第 2、第 3 和第 4 个人会面。即使第 2-4 个人没有在他们的 session 列表中反射(reflect)这些 session ，这也会强制这些人会面。换句话说，存在一个对称性，因此如果人 1 和人 2 之间有会面，那么人 2 和人 1 之间也会有会面。任何时候一个问题自然都有感兴趣的对象(人)和他们( session )之间的对称关系，图可能会成为解决问题的有效工具。在您的情况下，您有下图。

根据此图表重申您的问题，您需要一种方法将这些 session 分成小组，以便在任何小组中，同一个人不会同时参加两个 session 。这通常称为图形的边着色，您在其中用所谓的“颜色”标记每个组，并尝试为每条边着色，以便没有顶点具有两条相邻的边相同的颜色。在您的问题中，您给出的解决方案将表示如下。

相关信息包括称为 Vizing 定理的东西。如果一个人的最大 session 次数是 N，那么你要么需要 N 要么 N+1 个不同的颜色(不同的时间段)来解决你的问题。当然，额外的时间段可能会很好，但通常您需要一个最小的解决方案。在您的问题中，您提供的解决方案显然是最小的。一般来说，您可能会有一些空闲的时间段供某些人使用。

在实践中，实现边界是 NP 完全的。有各种启发式算法通常做得很好并且接近。 networkx 库(顺便说一句，我很喜欢)实际上不支持我不相信的边缘着色，但等效的构造是图形的折线图的顶点着色。折线图是当您将所有边变成顶点时得到的，并且如果它们以前是由顶点连接的边，则说两个这样的顶点由边连接。您的问题的折线图并不太复杂。

当查看折线图而不是原始图时，您反而想找到一个顶点着色，因为现在顶点是 session (您仍想分配)，而边代表由一个不能同时参加两个 session 的人联系。对于您的问题，您给出的解决方案是折线图的以下顶点着色。

在图论中完成这个练习的全部意义在于图算法得到了很好的研究和理解。以下代码将您的数据结构转换为图形，使用 networkx 库找到折线图的顶点着色，并将数据重新格式化为您请求的结构。

import networkx as nx

def build_line_graph(people):
    G = nx.Graph()
    G.add_edges_from(((p, q) for p, L in people for q in L))
    return nx.line_graph(G)

def color_graph(G):
    return nx.greedy_color(G)

def format_answer(coloring):
    res = {}
    N = max(coloring.values()) + 1
    for meeting in coloring:
        time_slot = coloring[meeting]
        for meeting_member in (0, 1):
            if meeting[meeting_member] not in res:
                res[meeting[meeting_member]] = [None] * N
            res[meeting[meeting_member]][time_slot] = meeting[1-meeting_member]
    return res

def nest_answer(people, formatted):
    return [[p, formatted[p]] for p, v in people]

>>> format_answer(color_graph(build_line_graph(people)))
{1: [2, 3, 4], 2: [1, 4, 3], 3: [4, 1, 2], 4: [3, 2, 1]}

>>> nest_answer(people, format_answer(color_graph(build_line_graph(people))))
[[1, [2, 3, 4]], [2, [1, 4, 3]], [3, [4, 1, 2]], [4, [3, 2, 1]]]

出于某些原因，我更喜欢字典的答案，但我们可以重新格式化它，以便以最小的努力提供您要求的准确答案。

我应该提到的一点是，您的问题没有唯一的正确答案。来自有效答案的时隙的任何排列也是有效答案，并且通常有许多其他种类的着色可以满足您的必要属性。此外，贪心算法不能保证产生最佳解决方案(实际上有病态的反例)，但在这种情况下，它实际上会产生与您想出的相同的解决方案。通常解决方案会很好。