python - 如何让每个人都按喜好入座？

Question

这个问题来自CodeEval problem 118

Your team is moving to a new office. In order to make them feel comfortable in a new place you decided to let them pick the seats they want. Each team member has given you a list of seats that he/she would find acceptable. Your goal is to determine whether it is possible to satisfy everyone using these lists.

The seats in the new office are numbered from 1 to N. And the list of seating preferences each team member has given you is unsorted.

Example input and output:

1:[1, 3, 2], 2:[1], 3:[4, 3], 4:[4, 3] --> Yes # possible
1:[1, 3, 2], 2:[1], 3:[1] --> No # not possible

如何解决？

---

我尝试了什么？我相信解决方案将是递归的，这就是我到目前为止提出的解决方案，但我认为我没有将问题正确分解为更小的子问题。

def seat_team(num_seats, preferences, assigned):
    if len(preferences) == 1:
        for seat in range(len(preferences)):
            print preferences
            seat_wanted = preferences[0][1][seat]
            if not assigned[seat_wanted-1]:
                assigned[seat_wanted-1] = True
                return True, assigned
        return False, assigned
    else:
        for i in range(len(preferences)):
            current = preferences[i]
            for seat in current[1]:
                    found, assigned = seat_team(num_seats, [preferences[i]], assigned)
                    if not found:
                        return False
                    found, assigned = seat_team(num_seats, preferences[i+1:], assigned)
                    if not found:
                        return False
        return True

num_seats = 4
preferences = [(1,[1,3,2]), (2,[1]), (3,[4,3]), (4,[4,3])]
assigned = [False] * num_seats

print seat_team(4, preferences, assigned)

有什么想法吗？我确信这类问题有一个通用名称，以及解决它的算法，但我无法在网上找到类似的问题(或解决方案)。如果您知道任何示例，请分享示例，我将不胜感激。

Answer 1

这是一个标准最大值 Bipartite Matching问题。

集合 S 代表 M 个顶点，每个顶点属于一个成员，集合 T 代表 N 个顶点，每个顶点代表一个座位。如果 i^th 成员想要 j^th 席位，则存在从 S_i 到 T_j 的边。这是必需的二分图。如果maximum matching结果是M，那么我们有解决方案，否则没有。