8

假设有一个七口之家，比如说，

["John", "James", "Jenna", "Joseph", "Jane", "Jacob", "Joanne"]

他们都在为圣诞节送礼季节做准备。他们已经商定了一些规则，以确保一切顺利进行：

  • 每个人都必须送一份礼物。
  • 每个人都必须收到一份礼物。
  • 没有人可以给自己送礼物。
  • 任何人不得向其配偶赠送礼物。（简和约翰是夫妻）
  • 没有人可以给他去年给的同一个人。（去年，约翰给了詹姆斯，詹姆斯给了珍娜，珍娜给了约瑟夫，约瑟夫给了简，简给了雅各布，雅各布给了乔安妮，乔安妮给了约翰）
  • 最后，没有两个人可以互相赠送礼物。例如，如果约翰正在给珍娜，珍娜可能不会回馈给约翰。

规则如此复杂，他们很难在遵守规则的情况下弄清楚谁能给谁。因此，他们聘请我编写一个程序，该程序将显示人们可以相互给予的所有可能的合法方式。

我可以使用什么算法优雅地解决这个问题？

4

2 回答 2

4

我会使用一个简单的回溯算法。使用 Python 生成器函数：

def calc_gifts(names, blacklist, gifts={}):
    if len(names) > 0:
        name, rest = names[0], names[1:]
        for other in names + list(gifts):
            if (other != name and 
                    other not in blacklist[name] and
                    (other not in gifts or gifts[other] != name) and
                    other not in gifts.values()):

                gifts_new = dict(gifts.items() + [(name, other)])
                for solution in calc_gifts(rest, blacklist, gifts_new):
                    yield solution
    else:
        yield gifts

现在，我们设置名称和黑名单，并让生成器生成解决方案：

all_names = ["john", "james", "jenna", "joseph", "jane", "jacob", "joanne"]
blacklist = {"john":   ["james", "jane"],
             "james":  ["jenna"],
             "jenna":  ["joseph"],
             "joseph": ["jane"],
             "jane":   ["jacob", "john"],
             "jacob":  ["joanne"],
             "joanne": ["john"]}
generator = calc_gifts(all_names, blacklist)
solution = next(generator)

solutionthen 是dict送礼者和接受者的一个，例如{'joanne': 'joseph', 'james': 'john', 'jane': 'joanne', 'joseph': 'jacob', 'jacob': 'jane', 'john': 'jenna', 'jenna': 'james'}.

对于第一个解决方案，即 using next(generator)，calc_gifts仅调用了 10 次；对于所有 224 个解决方案，例如使用list(generator)它被调用大约。1000 次。

于 2012-10-30T10:52:31.273 回答
1

如果你从一个 7x7 的网格开始，每个人有一行和一列，表示是否允许行中提到的人向列中提到的人赠送礼物。

最初，将每个组合标记为允许，然后开始删除约束 3、4 和 5 明确禁止的组合。每个有效的礼物组合必须是您此时剩下的组合的子集。这将是您的起始位置。

现在你必须开始做决定，每一个决定都会影响你剩下的可能性。有些决定可能会被证明是错误的，最终导致并非每个人都能得到礼物。在这种情况下，您应该收回该决定并尝试另一个决定（提示：为此使用递归）。

如果您以结构化的方式尝试所有可能性，那么您一定会找到所有解决方案（如果存在）。

现在，让他们的钱物有所值:)

于 2012-10-26T16:43:33.970 回答