创建一个时间表，一群人互相交谈-有限制 [英] Create a schedule where a group of people all talk to each other - with restrictions

问题描述

我想实现以下目标:(例如可以用来为学生组织某种类型的加速活动)

I would like to achieve the following: (could be used for example to organize some sort of a speeddating event for students)

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

Create a schedule so people talk to each other one-on-one and this to each member of the group. but with restrictions.

• 输入:人员列表.(例如30人)
• 限制:有些人不应该互相交谈(例如，彼此认识)
• 输出:成对列表(分成多个会话)只有一种解决方案是可行的，无需知道所有可能的结果

• Input: list of people. (eg. 30 people)
• Restrictions: some of the people should not talk to each other (eg. they know each other)
• Output: List of pairs (separated into sessions) just one solution is ok, no need to know all of the possible outcomes

例如四人一组

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

限制:John-Mellisa->否

Restrictions: John - Mellisa -> NO

结果

第一场

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

第二场

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

第三场

• 史蒂夫-马克

由于限制，约翰和梅丽莎将不参加第三场会议.

John and Mellisa will not join session three as it is restriction.

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

Is there a way to approach this using Python or even excel?

我特别在寻找一些指示该问题的方法，因为我假设这是一些问题，我应该寻找一些求解器吗?动态编程等?

I am especially looking for some pointers how this problem is called as I assume this is some Should I look towards some solver? Dynamic programming etc?

推荐答案

这是一个非常幼稚的实现:

This is a fairly naive implementation:

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'}])))

结果(由于集合的无序性质，可能有所不同):

Result (can vary, due to unordered nature of sets):

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

这会生成会话，直到每个人都见面为止.您可以从生成器中获取 next()，直到拥有足够的会话为止.这种方法的唯一缺点是，它可能会在有更多人开会的会议之前找到几个人正在等待的会议.您可以通过按长度对会话进行排序来解决此问题，但这当然意味着生成所有会话.

This generates sessions until everyone has met. You could just get the next() from the generator until you have enough sessions. The only downside to this approach is that it may find a sessions where a few people are waiting before a session that has more people meeting. You could solve that by sorting the sessions by length, but of course that means generating all of them.

我添加了键入信息，以清楚说明期望的类型是什么，但当然不需要它.

I added typing info, to make it clear what the expected types are, but of course it doesn't need that to work.

这篇关于创建一个时间表，一群人互相交谈-有限制的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！