在少于O(n^2)的时间内找到通配符重叠。

Question

假设我有一个长度相等的元组列表，其中每个元素都是整数或者是一个"星号"，例如：

[
(1, 2, *, 4, 5),
(1, *, 3, 4, 6),
(1, *, 3, 4, 5),
(1, 2, 3, 4, 6),
(4, *, *, 5, 6),
(*, *, 1, 5, 6)
]

在这种情况下，元素1和3重叠，2和4重叠，5和6重叠。

有没有一种方法可以在比传统方法更短的时间内确定是否存在重叠（我实际上不需要所有的重叠，只需回答是否存在至少一个）？传统方法是将所有可能的对进行检查（自然地是O(n^2)）。

来自评论的澄清：

- 上述的n是行数。这是可能会变得很大的事情。为了解决这个问题，假设列数相对较小，比如不超过20。 - “星号”代表确切的一个元素。

- Clinton

---

你可以创建一个以整数作为节点的字典树，然后扫描当前节点的所有元素，如果操作是*，则转到该子节点。 - Albin Paul

你可以创建一个以整数作为节点的字典树，然后扫描当前节点的所有元素，如果操作是*，则转到该子节点。 - Albin Paul

整数的范围是多少？它们受到一个相对较小的值的限制吗？ - Damien

整数的范围是多少？它们是否受到相对较小的值的限制？ - Damien

检查所有的配对需要 O(n^2 k) 的时间，其中 n 是元组的数量，k 是每个元组中的元素数量。 - Stef

Answer 1

由于列可以以任何方式排序，所以只要存在没有通配符的列，trie概念可能就不那么有用，因为这些列可以进行划分，从而减少搜索空间，它们包含的唯一元素越多。我建议按照以下方式对列进行排序：（1）通配符数量升序排列，（2）唯一元素数量降序排列，并执行深度优先搜索（DFS），优先将下一组需要排队的列按照其中除去用于下一划分的通配符外的通配符总数最高的比例来确定顺序。 例如，输入为：

(1, 2, *, 4, 5),
(1, *, 3, 4, 6),
(1, *, 3, 4, 5),
(1, 2, 3, 4, 6),
(4, *, *, 5, 6),
(*, *, 1, 5, 6)

从右到左排序的列：

A (2, *, 1, 4, 5),
B (*, 3, 1, 4, 6),
C (*, 3, 1, 4, 5),
D (2, 3, 1, 4, 6),
E (*, *, 4, 5, 6),
F (*, 1, *, 5, 6)

第一个分区：

{A, C} {B, D, E, F}
 1/4       5/16     wildcard ratio

第二个分区：

{B, D} {E, F}
 1/6    4/6         wildcard ratio

等等。

- גלעד ברקן

---

我想知道是否有一些巧妙的技巧可以使用scikit-learn的DecisionTree来实现这个功能，或者算法需要从头开始重新编写。 - Stef

我在想，我们是否能用一些巧妙的技巧来使用scikit-learn的DecisionTree，或者算法需要从头开始重新编写。 - Stef

Answer 2

稍微简化一下之前的回答。这些数字形成了不相交的集合，然后对于每条边，将星号添加到所有属于入边的位置上。然后在深度优先搜索中，根据元组的数量进行优先级排序，而不管它们是否是星号。（如果只剩下一个元组且没有重叠，则进行剪枝。）

我认为在最坏的情况下，我们有所有唯一的数字和一个星号在第一个位置，并且只在最后才发现它是不可行的。考虑到一个固定的元组，我认为它的时间复杂度将是O(tuples)。

- Neil