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

Question

给定一个简单的 table 像这样：

+---------+---------+---------+
| 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       |
+---------+---------+---------+

是否可以确定此 table 中是否存在 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 行给定的 table.

我会这样开始：

如果您已经找到一个值（例如散列图），请创建用于查找的数据结构
创建一个数据结构来存储符合匹配条件（所有值都不同）的结果行
迭代输入 table 行，直到达到所需的子集大小或到达 table
从第一行开始
在迭代一行时，检查每个值，如果它在您的结构中（在 1. 中创建），如果是 -> 中止，否则将值添加到查找结构中。检查所有行值后，此行没问题，可以添加到您的结果集中。
迭代下一行，如果存在的话

但是正如评论中指出的那样，该算法是一种贪心算法，不会总能找到可能的解决方案

Answer 3

Is there a simple algorithm to conclude on such a question?

答案是严格的"yes"；您可以对 K 行的所有（R 选择 K）个子集执行 brute-force search，其中 R 是整个 table 中的行数。该算法非常简单，可以用 Python.

这样的语言在几行中实现

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

归约如下：给定一个图，构造一个table，每个顶点一行。对于图中的每条边，将一列添加到 table；在此列中，在边缘连接的两行中写下相同的字母，然后在该列的其余各行中写下不同的其他字母。结果table有V行E列，所以它的大小是原图大小的多项式，在多项式时间内构造。

然后，在每列中具有不同值的任何一组 K 行给出原始图中没有任何边连接的 K 个顶点。也就是说，如果你能在多项式时间内回答yes/no是否存在这样的K行集合，那么你也能在多项式时间内回答最大独立集问题的判定形式。后者是 NP 完全的，因此你的问题是 NP 难的。

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

Find a subset with distinct values for each column

algorithm

subset

distinct-values