12

我在一家咨询机构工作，大部分时间都在客户所在地。因此，我很少见到我的同事。为了更好地了解彼此，我们将安排一次晚宴。会有很多小桌子，所以人们可以聊天。为了在聚会期间与尽可能多的人交谈，每个人都必须每隔一段时间换桌，比如说每小时。

如何编写创建表切换时间表的程序？只是给你一些数字；在这种情况下，大约有 40 人，每张桌子最多可以有 8 人。但是，算法当然需要通用

4

9 回答 9

12

这是一个想法
，首先从第一个人的角度工作.. 让我们称他为 X
X 必须会见房间里的所有其他人，所以我们应该将剩余的人分成 n 组（其中 n = #_of_people/capacity_per_table ）和让他在每次迭代中与其中一个组坐在一起
现在 X 已经得到照顾，我们将考虑下一个人 Y
WLOG Y 是 X 在第一次迭代中必须坐在一起的人.. 所以我们已经知道 Y 的表组在那个时间范围内..然后我们应该将剩余的人分成几组，使得每个连续迭代的每个组都与 Y 坐在一起..并且对于每次迭代，X 的组和 Y 的组没有共同点
..我想，如果你继续这样做，您将获得最佳解决方案（如果存在）

或者，您可以通过给每个人一张卡片来众筹问题，他们可以在卡片上写下与他们共进晚餐的所有人的名字。在活动结束时，向名字最多的人赠送某种奖品他们的卡

于 2009-06-09T07:54:50.580 回答
6

这听起来像是遗传算法的应用：

  1. 选择 40 位客人的随机排列 - 这是一种座位安排
  2. 重复随机排列N次（n是你晚上要换多少次座位）
  3. 将排列组合在一起——这是一种生物的染色体
  4. 重复你想在一代中繁殖多少生物
  5. 健身分数是每个人在一晚内看到的人数（或者 - 他们没有看到的人数的倒数）
  6. 使用常规方法繁殖、变异和引入新的生物体，然后重复，直到得到满意的答案

您可以在健身中添加您喜欢的任何其他因素，例如男女比例等，而不会大大改变底层方法。

于 2009-06-09T08:26:46.723 回答
6

为什么不模仿现实世界？

class Person { 
    void doPeriodically() {
         do {
             newTable = random (numberOfTables);
         } while (tableBusy(newTable))
         switchTable (newTable) 
    }
}

哦，请注意，有一个类似的算法可以找到一个交配对象，据传它对那些没有把所有空闲时间都花在回答编程问题上的 99% 的人来说是有效的......

于 2009-06-09T20:25:44.267 回答
4

完美的餐桌计划

于 2009-06-09T18:19:39.257 回答
3

您可能想看看组合设计理论。

于 2009-06-09T09:13:11.233 回答
2

直觉上我认为你不能比完美的洗牌做得更好，但这超出了我喝咖啡前的认知来证明这一点。

于 2009-06-09T09:48:36.153 回答
2

这个很搞笑！:D

我尝试了不同的方法，但 adi92（卡片 + 奖品）建议的逻辑比我尝试过的任何其他方法都好。

它是这样工作的：

  1. 一个人来检查所有的桌子
  2. 对于每张有空位的桌子，他计算他还需要见多少人，然后选择一个陌生人较多的桌子
  3. 如果两张桌子有相同数量的陌生人，那么这个家伙会选择空位多的一张，这样就有更多的机会结识更多的新朋友

在每一轮，就座的人的顺序是随机的（这避免了可能的无限循环），这是python中工作算法的“演示”：

import random

class Person(object):

    def __init__(self, name):
        self.name = name
        self.known_people = dict()

    def meets(self, a_guy, propagation = True):
        "self meets a_guy, and a_guy meets self"
        if a_guy not in self.known_people:
            self.known_people[a_guy] = 1
        else:
            self.known_people[a_guy] += 1

        if propagation: a_guy.meets(self, False)

    def points(self, table):
        "Calculates how many new guys self will meet at table"
        return len([p for p in table if p not in self.known_people])

    def chooses(self, tables, n_seats):
        "Calculate what is the best table to sit at, and return it"
        points = 0
        free_seats = 0
        ret = random.choice([t for t in tables if len(t)<n_seats])

        for table in tables:
            tmp_p = self.points(table)
            tmp_s = n_seats - len(table)
            if tmp_s == 0: continue
            if tmp_p > points or (tmp_p == points and tmp_s > free_seats):
                ret = table
                points = tmp_p
                free_seats = tmp_s

        return ret

    def __str__(self):
        return self.name
    def __repr__(self):
        return self.name


def Switcher(n_seats, people):
    """calculate how many tables and what switches you need
        assuming each table has n_seats seats"""

    n_people = len(people)
    n_tables = n_people/n_seats

    switches = []
    while not all(len(g.known_people) == n_people-1 for g in people):
        tables = [[] for t in xrange(n_tables)]

        random.shuffle(people) # need to change "starter"

        for the_guy in people:
            table = the_guy.chooses(tables, n_seats)
            tables.remove(table)
            for guy in table:
                the_guy.meets(guy)
            table += [the_guy]
            tables += [table]

        switches += [tables]

    return switches



lst_people = [Person('Hallis'),
      Person('adi92'),
      Person('ilya n.'),
      Person('m_oLogin'),
      Person('Andrea'),
      Person('1800 INFORMATION'),
      Person('starblue'),
      Person('regularfry')]    



s = Switcher(4, lst_people)

print "You need %d tables and %d turns" % (len(s[0]), len(s))
turn = 1
for tables in s:
    print 'Turn #%d' % turn
    turn += 1
    tbl = 1
    for table in tables:
        print '  Table #%d - '%tbl, table
        tbl += 1
    print '\n'

这将输出如下内容：

You need 2 tables and 3 turns
Turn #1
  Table #1 -  [1800 INFORMATION, Hallis, m_oLogin, Andrea]
  Table #2 -  [adi92, starblue, ilya n., regularfry]


Turn #2
  Table #1 -  [regularfry, starblue, Hallis, m_oLogin]
  Table #2 -  [adi92, 1800 INFORMATION, Andrea, ilya n.]


Turn #3
  Table #1 -  [m_oLogin, Hallis, adi92, ilya n.]
  Table #2 -  [Andrea, regularfry, starblue, 1800 INFORMATION]

由于随机性，它并不总是带有最少的切换次数，尤其是在人数较多的情况下。然后你应该运行它几次并以更少的轮次获得结果（这样你就不会给聚会上的所有人施加压力：P），而且编写代码很容易：P

PS：是的，您可以节省奖金：P

于 2009-06-11T23:29:48.607 回答
1

您还可以查看稳定匹配问题。这个问题的解决方案涉及使用最大流算法。http://en.wikipedia.org/wiki/Stable_marriage_problem

于 2009-06-09T18:10:32.360 回答
1

我不会打扰遗传算法。相反，我会做以下事情，这是对重复完美洗牌的轻微改进。

虽然（有两个人没见过）：

  1. 考虑图中每个节点都是客人，如果 A 和 B 没有坐在同一张桌子上，则存在边 (A, B)。找到该图的所有连通分量。如果有任何大小 < tablesize 的连接组件，则将这些连接组件安排在表中。请注意，即使这实际上是一个称为 Bin 打包的难题的实例，但首先拟合递减可能会很好，这可以通过按从大到小的顺序对连接的组件进行排序，然后将它们中的每一个放入转到他们适合的第一张桌子。
  2. 对剩余元素执行随机排列。（换句话说，让剩下的人随机入座，一开始是每个人。）
  3. 指示轮数的增量计数器。

重复上述操作一段时间，直到轮数似乎收敛。

于 2009-06-10T01:22:53.573 回答