高效地确定电子表格中行之间的关系

Question

这是我刚刚遇到的一个问题，或者更确切地说，它是捕获核心问题的简化。

想象一下，我有一个电子表格，其中包含许多列，每个列都标有标签，还有一些行。

我想确定一列中的值何时可以从另一列中的值推断出来。例如，我们可能会发现每次在列a中出现'1'时，总是在列d中出现'5'，但是只要在列a中出现'2'，3总会出现在列d。我们观察到列a中的值可靠地预测了列c中的值。

目标是确定列之间的所有这些关系。 （a，b），（a，c），（a，d）...（b，c），（b，d）的列对开始列表， ... 等等。我们称这些为“合格”列表。

对于这些配对中的每一对，我们都会跟踪配对中第一对的值和第二对中的对应值。如果我们注意到我们看到第一对货币的价值相同，而第二个货币对的价值不同，那么这对货物不再符合条件。

无论在这个过程结束时剩下的是一组有效的关系。

不幸的是，随着列数的增加，这很快就变得不切实际，因为我们必须存储的数据量是按列的平方数量的顺序排列的。

任何人都可以想到一个有效的方法来做到这一点？

Answer 1

我不认为你可以改进n列的O（n^2）：考虑任何一对之间不存在关系的情况。发现这一点的唯一方法是测试所有对，即O（n^2）。

Answer 2

我怀疑你最好是建立关系，而不是缩小关系。

您可能必须存储n^2条信息，其中有n列。例如，如果一个列从不重复（即它的值在每一行上不同），那么该列预测所有其他列。如果每一列都是这样的，那么每一列都可以预测其他列。你可以使用一个二维表，pred表示，按列数索引，pred（a，b）如果是预测b，则为true。 pred（a，b）可以具有3个值中的任何一个：真，假和未知。

预测关系是传递性的，即如果预测b和b预测c然后a预测c。如果行数很大，以便检查一行是否预测另一行很昂贵，那么可能需要使用可传递性来填写可能的内容：如果您刚刚计算pred（a，b）为真，并且您有已经为每个x计算了pred（b，x），那么可以为pred（b，y）为真的每个y设置pred（a，y）true。要填充pred（a ,.），您可以从a构建一对临时数组（值，行索引），然后按值排序;这使您可以轻松访问a不变的索引集。如果这些集合中的每一个都是单例，那么pred（a，b）对于每个b都是真的;否则检查是否预测b（如果它不是已知的），你需要检查b在每个索引集上（不止一个成员）是恒定的，其中a是常数。如果pred（a，b）为真，且pred（b，a）为真，那么对于每个c，pred（a，c）当且仅当pred（b，c） ;因此在这种情况下，如果您已经填写pred（b ,.），您可以通过复制填写所有pred（a ,.）。