寻找最小基组的算法？

Question

假设我们有 N 个集合 { x₁, x₂, x₃, …, x_N }.

这 N 个集合的“基”是 M 个集合的集合 { y₁, < em>y₂, y₃, …, y_M } 这样每个 { x₁, x₂, x₃, …, x_N } 是 { < em>y₁, y₂, y₃, …, y_M }.

我怎样才能找到“最小”基础，即具有最少 M 的基础？

Answer 1

想到的一个类似问题是找到 basis of a vector space或找到最小的 generating set , 分别。

由于集合的数量以及所有可能元素的宇宙是有限的，我们可以将每个集合重写为这样的向量(假设整数作为集合中的元素):

{ 1, 2, 5 } => ( 1, 1, 0, 0, 1, 0 , ... )
{ 4 }       => ( 0, 0, 0, 1, 0, ... )

所有向量 x_i 的集合现在形成一个(平凡的)生成集 G，用于所有集合 x_i 的宇宙。

您搜索最小生成器。为此，我们必须从向量集 G 中消除所有线性相关性。一种天真的方法是检查所有包含 G 元素的三元组是否满足以下条件(x,y,z 向量 G 和 k,l,m 数字):

  k * x + l * y  + m * z == 0

如果满足条件，我们将消除这三个向量中的一个。 (哪一个并不重要)。

这样减少的向量集(及其各自的集合)构成了你的集合集的基础。

^{上述论点的一个要求是，您允许 set difference作为生成集合的操作。}