假设我有两套，set1 = {a,b,c,d,e,f}和set2 = {a,b,c,d,e,g}。我不想明确地表达这些，而是想创造一些
common = {a,b,c,d,e}
set1 = common + f
set2 = common + g
如果我们想表示
{a,b,c,h}，我们可以表示为common - d - e + h。我的目标基本上是能够生成要使用的最佳公共部分。只有一个共同的部分，这并不太具有挑战性，但我需要允许不止一个（但不是无限的，否则获得的好处将是微不足道的）。
我说的“最优”是指“表示的元素最少”。因此在上面的例子中，将
common变量设为“花费”5（元素数）。然后分别设置1和2 cost 2（一个用于引用common，一个用于添加额外元素），总计为7。如果没有替换，存储这些元素需要12英镑（每个元素6英镑）。类似地，从引用中减去一个元素将“花费”1。另一个例子，
{a,b,c,d}, {a,c,d,e}, {e,f,g,h} and {e,f}可以是
common1 = {a,c,d}
common2 = {e,f,g}
set1 = common1 + b
set2 = common1 + e
set3 = common2 + h
set4 = common2 - g
通过允许多个公共部分，这变得更具挑战性。这类问题是有名字的，还是类似的？看起来这可能与压缩有关，但是我还没有找到太多的资源来说明从哪里开始。
其他一些可能相关的细节：
允许引用多个公共部分来表示一个集合是有效的，但不是必需的。
对于我的用例，集合通常是大约20个元素和大约10个不同的集合。
最佳答案
你可以找到所有的原子集，也就是所有从未分开的集。
{a,b,c,d,e,f,g,h} | {a,b,c,d} = {a,b,c,d},{e,f,g,h}
{a,b,c,d},{e,f,g,h} | {a,c,d,e} = {a,b,c,d},{e,f,g,h}
{a,c,d},{b},{e},{f,g,h} | {e,f,g,h} = {a,c,d},{b},{e},{f,g,h}
{a,c,d},{b},{e},{f,g,h} | {e,f} = {a,c,d},{b},{e},{f},{g,h}
{a,b,c,d} = {a,c,d},{b}
{a,c,d,e} = {a,c,d},{e}
{e,f,g,h} = {e},{f},{g,h}
{e,f} = {e},{f}
这有点接近，但不能解决最小的故障。
我不认为你能找到最小的，因为我怀疑这是np难。如果考虑一个集合s并创建一个图，其中s的每个可能子集都是一个节点g。现在根据子集的长度赋予一个节点权重，并在每个节点之间绘制一条与更改量相对应的边。{abc}->{a}的权重为2。{bcd}->{abe}的权重为4。现在要找到公共集问题的最小解，您需要找到覆盖您感兴趣的每个集的最小权值生成树。如果你发现你可以用它来建立一个最小的公共集——这些是等价的。在节点加权图中寻找最小权树称为节点加权steiner树问题。节点加权steiner树问题可以等价于steiner树问题。steiner树问题是np难问题。所以我强烈怀疑你要解决的问题是np难的。
http://theory.cs.uni-bonn.de/info5/steinerkompendium/node15.html
http://theory.cs.uni-bonn.de/info5/steinerkompendium/node17.html