sql - 如何修剪重复的关联以产生唯一的最完整的集合

Question

我几乎不知道如何陈述这个问题，更不用说寻找答案了。但这是我最好的机会。假设我有一张 table

Col1   Col2
-----+-----
 A   | 1
 A   | 2
 A   | 3
 A   | 4
 B   | 1
 B   | 2
 B   | 3
 C   | 1
 C   | 2
 C   | 3
 D   | 1

我想找到关联(行)的子集，其中:

1. Col1 中没有重复项
2. Col2没有重复
3. Col1 中的每个值都与 Col2 中的值相关联

所以上面的例子可以产生这个结果

Col1   Col2
-----+-----
 A   | 4
 B   | 2
 C   | 3
 D   | 1

请注意，A-4 必须在结果中，因为有 4 个唯一字母和 4 个唯一数字，所以如果您不将 A 与 4 相关联，则没有子集不映射 Col1 中的每个值，同时保留Col2的独特性。

另请注意，将 B-2 和 C-3 替换为 B-3 和 C-2 同样有效。我不在乎选择了哪个子集，但我想要一个满足所有要求的子集。

并非每组数据都有满足所有要求的子集，但我希望尽可能接近。

我正在尝试使用 SQL 查询来执行此操作。我有一个查询似乎可以针对一组数据完成此操作，但后来我不得不针对稍微不同的一组(其中 Col2 实际上是一对列)重写它，并且无法重现我之前的成功。我的第一个解决方案使用 Min() 和 Group By 以及聚合结果上的几个 Join 来标记要在循环中消除的重复项，直到没有任何东西可以安全消除为止。我最近的解决方案将 Group By 查询替换为使用 PARTITION_BY 的 ROW_NUMBER() 表达式。但是我无法弄清楚如何处理上面示例中的 B 和 C 等多重交叉链接对存在多个有效结果集的情况。我之前的查询可能已经处理了它，但我不太明白我做了什么(我写那个查询时一定过得很愉快)。也许我需要对子查询中的 ROW_NUMBER 表达式进行 JOIN？我的大脑今天用完了。我希望有人能帮我找到一个巧妙简单的解决方案。

Answer 1

问题相当于找一个maximum matching in a bipartite graph .每列元素代表一个顶点，每行代表一条边。链接的维基百科文章提供了一些指向解决此问题的算法的指针。 Google's or-tools library 中有匈牙利算法的实现。 .

这里是给定的示例，用图形表示，红色边代表给定的解决方案:

如果您能找到完全使用 SQL 的解决方案，我会感到很惊讶。