c# - 如何根据属性匹配元素？

Question

我正在尝试编写一种算法，根据项目的属性匹配项目。

我有一个类(class)列表，每门类(class)属于一个或多个类别。一个级别必须有每个类别的 1 个主题。一个主题不能用于针对一个级别中超过 1 个类别的证据。

所以，例如:

类(class) x 有类别:类别 1、类别 2、类别 3、类别 4 和类别 5。

Subject A - Cat 1, Cat 2
Subject B - Cat 2, Cat 3
Subject C - Cat 4
Subject D - Cat 2, Cat 4
Subject E - Cat 5

在这种情况下我会把

A Cat 1, 
B Cat 3, 
C Cat 4, 
D Cat 2, 
E Cat 5. 

学生在运行算法时可能没有完成所有类别，因此需要能够应对这种情况。

非常感谢任何帮助/建议/论文/片段。我有 1500 条记录要匹配，必须手动启动此过程才能按时完成。

Answer 1

这看起来像一个 bipartite graph matching problem对我来说，图表由两个方面组成:类别、主题。边是类别与主题的连接。

图的最大匹配，也将是某些类(class)x的最优结果。

在您的示例中，二部图是:

G=(V,U,E)
V = { Cat1, Cat2, Cat3, Cat4, Cat5}
U = { Subject A, Subject B, Subject C, Subject D, Subject E} 
E = { (A,1), (A,2), (B,2), (B,3), (C,4), (D,2), (D,4), (E,5) } 

这可以通过多种方式解决(例如将其转换为 maximal flow problem ，或使用 Hopcroft-Karp algorithm )