algorithm - 座位有多少种排列方式

Question

我在其中一次采访中发现了以下问题。请给我建议这个算法。我不需要代码。

电影院里有 N 个人和 N 个座位。每个人都有自己喜欢的座位列表，例如:

人 1 -> 1、2、4

人 2 -> 2 , 5

人 3 -> 1、3 等等 ..

我需要找到可以按稳定顺序排列座位的方式的数量(这意味着每个人都必须从那里的偏好列表中找到座位)。

Answer 1

如果我们用图形语言翻译您的问题，我们将获得 bipartite graph其中人和座位代表两组不相交的顶点。您要查找的是此类图中的多个完美匹配。

我很惊讶你在采访中发现了这个问题，因为这是一个严肃的科学研究课题。您应该查看两篇论文:

• Finding all the perfect matchings in bipartite graphs
• Algorithms for Enumerating All Perfect, Maximum and Maximal Matchings in Bipartite Graphs

简而言之，第一篇论文提供了一种算法来枚举O(c(n+m)+n^(2.5))中的所有完美匹配。时间，而第二篇论文对其进行了改进并给出了 O(mn^(0.5)+ cn) 的算法时间，在哪里n表示顶点数，m表示边数，c表示给定二部图中完美匹配的数量。