algorithm - 集合的组合/笛卡尔积的计算(无重复且无顺序限制)

Question

我有一个组合问题，使用笛卡尔坐标可以低效地解决多套产品。具体来说，我有多个项目和多个元素满足每一项。问题包括找到所有可能的元素组合满足所有项目。例如:

items -> elements
------------------------
1 -> {a,b}     // a and b cover the item 1
2 -> {a,b}     // a and b cover the item 2
3 -> {a,b,c}   // a, b and c cover the item 3
4 -> {a,b,e,f} // a, b, e, f cover the item 4

Alternative representation:
element -> items covered
------------------------
a -> {1,2,3,4}
b -> {1,2,3,4}
c -> {3}
e -> {4}
f -> {4}

目标是找到涵盖项目 1、2、3、4 的所有组合。有效的解决方案是:

{a},{a,b},{a,c},{a,e},{a,f},{a,b,c},{a,b,e},{a,b,f},{a,b,c,e},{a,b,c,f}
{b},{b,c},{b,e},{b,f},{b,c,e},{b,c,f}

注意顺序并不重要，所以{a,b} = {b,a} ({a,b} x {c,d} = {c,d} x {a,b}) .另外，请注意 {a,a,a,a}, {a,a,a,b}...是冗余组合。

如您所见，此问题类似于 set cover problem , 宇宙在哪里此示例的元素是项目 U={1,2,3,4}来自 U 的子集集是 S={ab={1,2,3,4},c={3},ef{4}} , 在哪里设置 {1,2,3,4}是元素 a 涵盖的项目集和 b , {3}是 c 涵盖的元素集, 和 {4}是元素 e 覆盖的元素集和 f .然而，这里的目标不是找到来自 S 的集合的最小组合涵盖了 U 中的所有元素, 但找到元素的所有组合 {a,b,c,e,f}涵盖所有项目{1,2,3,4} .

一个简单的实现可以通过在两者之间执行笛卡尔积来完成设置为 1,2,3 和 4，然后过滤多余的组合。然而，这种方法效率很低。假设我有这种情况:

1 -> {a,b,c,d,e,f,g,h}
2 -> {a,b,c,d,e,f,g,h}
3 -> {a,b,c,d,e,f,g,h}
4 -> {a,b,c,d,e,f,g,h}
5 -> {a,b,c,d,e,f,g,h}
6 -> {a,b,c,d,e,f,g,h,i}

六个集合之间的笛卡尔积将导致 8^5*9=294912组合，当实际上有更少的组合时，它们是:{a,b,c,d,e,f,g} U {a,b,c,d,e,f,g} x {i} .

解决这个问题的另一种方法是枚举所有元素，跳过等同于其他先前生成的组合，以及跳过重复的元素。这有点容易计算并且可以实现作为一次返回组合的迭代器，但我不知道是否有解决此问题的更好方法，或者之前是否研究过此问题。

你会如何解决这个问题？

Answer 1

首先，要意识到如果一组元素不满足所有项，那么它的任何子集也不满足。

其次，意识到如果一个集合满足所有项目，那么它的所有超集也满足。

现在，您所要做的就是:

设 S 为所有元素的集合。令 R 为空集。

定义一个函数 find( s, r ) 做:

If r includes s, return r.
If s does not satisfy all items, return r.

Otherwise add s to r.
For every item I in  s,
     let s' be s-I
     let s be f(s', r)

return s.

只需调用 find(S,R) 即可得到答案。

此方法执行一些重复测试，但总是会在分支被识别时终止分支。这导致对大量元素进行大量修剪。

查找 r 是否包含一组特定的元素和检查 s 是否满足所有项目都可以非常快速地进行，但需要额外的内存。