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 上，以及他们必须在这里会见的人。

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

标签： python

Answer 1

更新以更清晰，以防有人从谷歌这里绊倒。内容几乎相同。

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

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

相关信息包括称为 Vizing 定理的东西。如果一个人最多开会 N 次，那么你需要 N 或 N+1 种不同的颜色（不同的时间段）来解决你的问题。当然，额外的时间段可以正常工作，但通常你需要一个最小的解决方案。在您的问题中，您给出的解决方案显然是最小的。一般来说，您可能会有一些人没有占用的时间段。

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

当查看折线图而不是原始图时，您希望找到一个顶点着色，因为现在顶点是会议（您仍要分配），而边代表无法连接的单个人一次参加两次会议。对于您的问题，您给出的解决方案是折线图的以下顶点着色。

在图论中完成这个练习的重点是图算法得到了很好的研究和理解。以下代码将您的数据结构转换为图形，使用该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]]]

出于几个原因，我更喜欢字典的答案，但我们可以重新格式化它，以最小的努力给出您要求的确切答案。

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