algorithm - 如何快速将元素组合映射到另一个向量

Question

假设我有两组元素，X 和 Y。两组都包含数万(或更多)独特的元素。 X 中元素的任意组合，如 (X1, X4, X6, X100, ...)，可以映射到 Y 中的零个、一个或多个元素。

我应该如何将数据存储在 SQL 数据库中，或者如何通过算法确定 Y 是否包含与给定的 X 元素集相对应的元素，以及哪些元素？

如有任何想法，我们将不胜感激。

Answer 1

您面临的主要问题是您映射的其中一个集合是幂集 (2^X)，它有 2^|X| 个元素.如果 2^X 被密集使用(例如，如果 Y 中的每个元素对应于 X 的任意大且不规则数量的子集)，那么您将有 |Y|*2^{|X |} 映射中的边，这在计算上无法以任何方式表示。

可解案例的两个例子:

1. 如果 Y 中的每个 y 仅对应于 X 的一个子集，您可以用 Y 的单个元素和 X 的单个元素表示关系，并在 X 和 Y 上建立索引。该表的最大大小为O(|Y|*|X|)。查询将是表自身的一系列连接(匹配 ys)，其中 x 是子集中的每个元素。
2. 如果对于 X 中的每个 x 和 Y 中的 y，y 要么映射到包含 x 的任何子集，要么映射到不包含 x 的子集，那么这可以用同一个表表示，但查询会容易得多。