通过并集减少集合的大小，受最大并集大小的限制

Question

我有一组不同的集合，其中没有一个不同的集合具有多个k元素。例如：k​4

\n

set([frozenset({0, 3, 6}),\n     frozenset({0, 1, 2}),\n     frozenset({6, 7}),\n     frozenset({8, 7}),\n     frozenset({1, 2}),\n     frozenset({9, 11, 6, 7}),\n     frozenset({0, 11, 6, 7}),\n     frozenset({9, 6, 7}),\n     frozenset({11, 6, 7}),\n     frozenset({0, 6, 7}),\n     frozenset({0, 6}),\n     frozenset({0, 3, 6, 7}),\n     frozenset({11}),\n     frozenset({8}),\n     frozenset({8, 6, 7}),\n     frozenset({0, 1, 3, 6}),\n     frozenset({0, 1, 6}),\n     frozenset({0, 1}),\n     frozenset({3, 4, 5}),\n     frozenset({9, 6}),\n     frozenset({9, 10}),\n     frozenset({4, 5}),\n     frozenset({11, 9, 3, 6}),\n     frozenset({9, 11, 6}),\n     frozenset({9, 3, 6}),\n     frozenset({3, 6}),\n     frozenset({0, 9, 3, 6}),\n     frozenset({10}),\n     frozenset({9, 10, 6}),\n     frozenset({0, 3, 4, 6}),\n     frozenset({3, 4, 6}),\n     frozenset({3, 4}),\n     frozenset({11, 6})])\n

\n

我想将冻结集彼此联合起来，以使周围集中的条目数量尽可能小。然而，上述条件（集合的大小不得大于该值）k必须仍然成立。如果我要暴力破解，这将在 O(n\xc2\xb3) 时间内完成(oof)和 O(n!) 时间 (oooof) 内根据匹配可能并集的顺序，可以创建不再能够达到正确解决方案的状态。

\n

例如：如果给定{1, 3}, {1, 2}, {3, 4}, {3, 5}每组 3 个元素的限制，我将联合起来{1, 3}，{3, 4}这将产生{1, 3, 4}, {1, 2}, {3, 5}。如果我改为联合{3, 4}和{3, 5}，我就会得到{1, 3}, {1, 2}, {3, 4, 5}和 然后{1, 2, 3}, {3, 4, 5}（少一盘）。

\n

我在这里没有看到明显的策略。在该示例中，所有 4 个最初可用的集合都具有相同的大小，{1, 2}并且{3, 4}它们彼此之间完全共享一个元素。那么：如何通过内部集合的并集尽可能地减少集合的大小，同时使内部集合不超过给定的大小？

\n

编辑 1：我能够编写一个函数来消除 O(n\xc2\xb2) 中的子集，这是一个好的开始。

\n

set([frozenset({0, 3, 6}),\n     frozenset({0, 1, 2}),\n     frozenset({6, 7}),\n     frozenset({8, 7}),\n     frozenset({1, 2}),\n     frozenset({9, 11, 6, 7}),\n     frozenset({0, 11, 6, 7}),\n     frozenset({9, 6, 7}),\n     frozenset({11, 6, 7}),\n     frozenset({0, 6, 7}),\n     frozenset({0, 6}),\n     frozenset({0, 3, 6, 7}),\n     frozenset({11}),\n     frozenset({8}),\n     frozenset({8, 6, 7}),\n     frozenset({0, 1, 3, 6}),\n     frozenset({0, 1, 6}),\n     frozenset({0, 1}),\n     frozenset({3, 4, 5}),\n     frozenset({9, 6}),\n     frozenset({9, 10}),\n     frozenset({4, 5}),\n     frozenset({11, 9, 3, 6}),\n     frozenset({9, 11, 6}),\n     frozenset({9, 3, 6}),\n     frozenset({3, 6}),\n     frozenset({0, 9, 3, 6}),\n     frozenset({10}),\n     frozenset({9, 10, 6}),\n     frozenset({0, 3, 4, 6}),\n     frozenset({3, 4, 6}),\n     frozenset({3, 4}),\n     frozenset({11, 6})])\n

\n

Answer 1

如果有一个简单的解决方案，我会感到惊讶。因此，这里是一个实用方法的概述，该方法可以根据您输入的大小而起作用。

从稍微修改开始。假设我们正在寻找集合的最小“覆盖”集合c_1，... c_n（每个大小 <= k），使得每个给定的集合s_i都是一个或多个覆盖集的子集。

找到封面上的所有候选人。为此，对给定集合进行重复并集s_i，并保存所有可能的基数小于 的结果k。

然后制定约束规划问题。为每个候选人分配一个指示变量。为每个s_i添加一个约束，指定包含该约束的候选对应的变量总和大于 1。在指标变量总和上添加一个最小化目标。解决。ortools可以处理这个（https://google.github.io/or-tools/python/ortools/sat/python/cp_model.html）

最后修改解决方案，从覆盖集中删除一些不必要的元素（如果有的话）。