为每列查找具有不同值的子集

Question

给出一个简单的表，如下所示：

+---------+---------+---------+
| Column1 | Column2 | Column3 |
+---------+---------+---------+
| A       | J       | Q       |
| A       | K       | S       |
| B       | M       | R       |
| B       | N       | S       |
| B       | J       | Q       |
| C       | K       | R       |
| D       | J       | R       |
| D       | J       | Q       |
| E       | L       | Q       |
+---------+---------+---------+

是否有可能确定该表中是否存在N行的子集，以便对于每一列，所有N值都是不同的？

例如，如果N = 3，答案将是是

+---------+---------+---------+
| Column1 | Column2 | Column3 |
+---------+---------+---------+
| A       | J       | Q       |
| B       | N       | S       |
| C       | K       | R       |
+---------+---------+---------+

是否有简单的算法可以得出这样的结论？

Answer 1

简单的解决方案是简单的搜索（回溯）。

但是每个解决CSP (Constraint satisfaction problem)的工具/库都可以找到解决方案。

Answer 2

由于您正在明确要求算法来解决此问题：

如果我正确地理解了这个问题（您在这里使用N两次，第一次是用于行，第二次是用于值，这有点令人困惑），您想在给定表中找到具有所有不同值的N行。

我会这样开始：

1. 如果已经找到值（例如，哈希表），则为查找创建数据结构
2. 创建一个数据结构来存储符合匹配条件的结果行（所有值都不同）
3. 迭代输入表的行，直到达到所需的子集大小或到达表的末尾
4. 从第一行开始
5. 在迭代一行时，检查每个值，如果它在您的结构中（在1中创建），如果是->中止，否则将其添加到查找结构中。选中所有行值后，此行就可以了，可以将其添加到您的结果集中。
6. 如果存在，请迭代下一行

Answer 3

是否有简单的算法可以得出这样的结论？

答案严格是“是”；您可以对K行的所有（R选择K）子集进行brute-force search，其中R是整个表中的行数。该算法非常简单，可以用Python之类的语言几行实现。

但是我不认为这是您要找的答案；我想您想知道是否有一种简单的算法所花费的时间少于指数时间。答案几乎肯定不是；通过maximum independent set problem的简化，问题是NP难的，因此没有已知的算法可以在多项式时间内给出正确的答案，并且很可能没有这种算法。

简化如下：给定一个图，构造一个表，每个顶点一行。对于图形中的每个边，在表中添加一列；在此列中，在边连接的两行中写入相同的字母，然后在该列的其​​余各行中写入不同的其他字母。结果表具有V行和E列，因此它是在图形大小的多项式时间内构造的。

然后，在每列中具有不同值的K行的任何集合都会给原始图形中的K个顶点带来任何边都不相连的情况。这回答了最大独立集问题的决策形式，该问题形式是NP完全的，因此，原始问题至少与之一样困难。