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

Question

问题陈述

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

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

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

例子

例如。 4人一组

约翰
史蒂夫
马克
梅丽莎

限制：John - Mellisa -> 否

结果

第一节

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

第二节

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

第三节

史蒂夫-马克

John 和 Mellisa 不会参加第三节课，因为它受到限制。

问题

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

我特别想知道这个问题是如何命名的，因为我认为这是一些我应该寻找一些求解器吗？动态规划等？

Answer 1

你给的信息挺大方的，你有一组所有的学生，还有一组不走的对（因为你自己说的，也很容易解释，就说这是一组一对互相认识的学生）。所以我们可以遍历我们的学生列表来创建随机配对，只要他们不存在于我们的禁忌集中，然后用他们扩展我们的禁忌集合，并递归剩余的学生，直到我们不能创建任何配对不存在的集合中不存在（我们有配对，以便每个学生都遇到所有学生）。

Answer 2

这是一个相当天真的实现：

from itertools import combinations
from typing import Set, List, Generator


def generate_sessions(people: Set, excl: List[Set]) -> Generator[List[Set], None, None]:
    # all the pairings you need are all possible pairings, except the exclusions
    needed_pairings = [set(pair) for pair in combinations(people, 2)]
    for pair in excl:
        needed_pairings.remove(pair)

    # while there pairing that haven't happened yet
    while needed_pairings:
        # each session starts empty
        session = []
        # keep track of all people still available for this session
        available = set(people)
        # create an iterator, so we can loop over the needed pairings
        iter_needed_pairings = iter(needed_pairings)
        # as long as there are more than 2 people still waiting and there's a pair left in the needed pairings
        while (len(available) > 1) and (pair := next(iter_needed_pairings, False)):
            # are both people in the pair in the group of available people?
            if available.intersection(pair) == pair:
                # then they can meet in this session
                session.append(pair)
                # and they're no longer available
                available -= pair
        # once we have a session, remove the pairs in it from the pairings still needed
        for pair in session:
            needed_pairings.remove(pair)
        # yield the session
        yield session


print(list(generate_sessions(people={'John', 'Steve', 'Mark', 'Melissa'}, excl=[{'John', 'Melissa'}])))

结果（由于集合的无序性质，可能会有所不同）：

[[{'John', 'Mark'}, {'Melissa', 'Steve'}], [{'John', 'Steve'}, {'Melissa', 'Mark'}], [{'Mark', 'Steve'}]]

这会产生 sessions，直到每个人都遇到了。您可以从生成器中获取 next()，直到您有足够的 session。这种方法的唯一缺点是，它可能会在 session 有更多人开会之前找到少数人正在等待的 sessions。您可以通过按长度对 session 进行排序来解决该问题，但这当然意味着生成所有这些。

编辑：我添加了输入信息，以明确预期的类型是什么，但当然它不需要它来工作。

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

Create a schedule where a group of people all talk to each other - with restrictions

python

algorithm

dynamic-programming

问题陈述

例子

问题