算法问题 - 查找最小公共子集

Question

a是具有多个“类别”（b）的对象，例如a1具有三个类别b1、b2和b3。 问题在于将类别的数量（可能会变得相当大）减少到总是一起出现的组中。这是一个“最大公共子集”的问题。

例如，给定以下数据集：

a1{ b1,b2,b3 } 
a2{ b2,b3 }
a3{ b1,b4 }

我们可以发现b2和b3总是一起出现。

b23 = {b2,b3}

..我们可以将类别集合减少到这个：

a1{ b1, b23 }
a2{ b23 }
a3{ b1,b4 }

所以，我的问题是找到一些算法来解决这个问题。我已经开始研究最长公共子序列问题，这可能是一个解决办法。例如，像这样重复地对类别进行分组：b' = LCS(set_of_As)，直到遍历完所有类别。然而，这还不够完整。我必须以某种方式限制输入域，以使其成为可能。 我是否错过了一些显而易见的东西？你能指出任何问题领域的提示吗？有人认识到其他解决此类问题的方法吗？

- Petter Nordlander

---

你很有可能是正确的。LCS 绝对是解决手头问题的一种方法。而且，对于你的主要问题，最短的答案是没有你错过任何明显的东西。看起来是个不错的问题。 - Robert Koritnik

实际上，你只需要运行与获取b23对时相同的配对算法即可。重复此过程，直到集合不再发生变化。第一次运行将生成一组对，第二次运行将生成一组对的对或一组对和一个单独元素的对。这样，你就可以涵盖三元组和四元组的重复情况了。 - Ghlitch

我认为你可以通过表明你的类别是有序的来提高性能。因此，如果你绘制一个包含所有类别x所有对象（axb矩阵）的矩阵，你只需要找到相等的列即可。我知道，这也很大，但可能会更快 :) - Plínio Pantaleão

将集合转换为矩阵并比较列与我的下面的答案类似 - 但会占用更多的内存，并且除非您对列进行排序，否则比较列将是低效的。 - Rafael Baptista

确实，你的方法似乎更快。 - Plínio Pantaleão

Answer 1

将您的集合转换为包含a的b集合：

b1 { a1, a3 }
b2 { a1, a2 }
b3 { a1, a2 }
b4 { a3 }

请确保新的 B 集合内容已排序。

按照 B 集合内容进行排序。

任何两个相邻的集合中具有相同元素的均为在同一 A 集合中出现的 B 集合。

- Rafael Baptista

---

另一个优化方法是首先按长度，然后按内容对b集合进行排序。 - coproc

Answer 2

如果您可以对类别进行排序（如果不能，则LCS算法无法识别{b3，b4}和{b4，b3}），那么我认为您在使用LCS方面是正确的。如果您可以强制排序并对它们进行排序，那么我认为以下内容可能有效：

As = {a1={b1, b2},a2={b3},...}
while ((newgroup = LCS(As)) != empty) {
  for (a in As) {
     replace newgroup in a
  }
}

- Kiersten Arnold