我有一个组合问题,可以使用多组的笛卡尔积来低效解决。具体来说,我有多个项目和满足每个项目的多个元素。该问题包括找到满足所有项目的元素的所有可能组合。例如:
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}
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}
.
解决这个问题的另一种方法是枚举所有元素,跳过与之前生成的其他等效的组合,也跳过重复的元素。这有点容易计算,可以实现为一次返回组合的迭代器,但我不知道是否有更好的方法来解决这个问题,或者这个问题之前是否研究过。
你将如何解决这个问题?