python - 创建一个时间表，让一群人互相交谈 - 有限制

Question

问题陈述

我想实现以下目标：（例如可以用来为学生组织某种快速约会活动）

创建一个时间表，以便人们一对一地相互交谈，并与小组的每个成员交谈。但有限制。

• 输入：人员列表。（例如 30 人）
• 限制：有些人不应该互相交谈（例如，他们彼此认识）
• 输出：配对列表（分成会话）只需一个解决方案即可，无需知道所有可能的结果

例子

例如。4人组

1. 约翰
2. 史蒂夫
3. 标记
4. 梅丽莎

限制：约翰 - 梅丽莎 -> 否

结果

第一节

• 约翰-史蒂夫
• 马克-梅丽莎

第二节

• 约翰-马克
• 史蒂夫-梅丽莎

第三节

• 史蒂夫-马克

约翰和梅丽莎不会加入第三节，因为这是限制。

问题

有没有办法使用 Python 甚至 excel 来解决这个问题？

我特别在寻找一些指示如何调用这个问题，因为我认为这是一些我应该寻找一些求解器吗？动态规划等？

标签： pythonalgorithmdynamic-programming

Answer 1

你给的信息挺大方的，你有一组所有的学生，还有一组no-go pair（因为你自己说了，解释起来也容易，就说这是一组学生知道对方）。所以我们可以遍历我们的学生列表创建随机配对，只要它们不存在于我们的 no-go 集中，然后用它们扩展我们的 no-go 集，并递归剩余的学生，直到我们无法创建任何配对在禁止组中不存在（我们有配对，因此每个学生都遇到了所有学生）。