算法问题 - 找到最不常见的子集

Question

a是具有多个"类别"的对象,例如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)在遍历所有类别之前,重复对这样的类别进行分组.但是,这还不完整.我必须以某种方式限制输入域以使其成为可能.

我想念一些明显的东西吗？您可以指向我的任何问题域的提示？有没有人认识到这种问题的任何其他方法.

Answer 1

将您的集合转换为包含以下内容的b集合:

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

确保对新b集的内容进行排序.

按照内容对b组进行排序.

具有相同元素的任何两个相邻集合是出现在相同集合中的b.