algorithm - 从这些集合的组合中重新创建集合

Question

我遇到了一个特定的问题并正在寻找一些算法来解决它。要解决的问题如下所述。

假设我们有如下组合

1 - 3 - 5

1 - 4 - 5

1 - 8 - 5

2 - 4 - 5

3 - 4 - 5

2 - 4 - 7

这些组合是从给定的集合中生成的，在这种特殊情况下，我们可以说是从

{1},{3,4,8},{5}

{2,3},{4},{5}

{2},{4},{7}

我想做的是从这些组合中重新创建集合。我知道对于这些组合，您有不止一种解决方案，例如

第一个解决方案

{1}、{3、4、8}、{5}

{2, 3}, {4}, {5}

{2}、{4}、{7}

第二种解决方案

{1}、{3、8}、{5}

{1, 2, 3}, {4}, {5}

{2}、{4}、{7}

第三个解决方案

{1}、{3、4、8}、{5}

{3}、{4}、{5}

{2}、{4}、{5、7}

但最终(最佳)解决方案将是集合尽可能少的解决方案或随机解决方案，以防它们在集合计数方面都相等。

是否存在解决此类问题的算法？如果有人一直在处理此类问题可以给我一些提示，我将不胜感激。

编辑:看起来我正在寻找的是 n 元乘积的分解(N 的笛卡尔乘积)

编辑:在对该主题进行更多研究后，我发现该问题在“图论”中被称为“最小集团覆盖”问题

问候，巴兹

Answer 1

这不是一个真正的答案，更像是一个扩展评论。您的“压缩表示”实际上根本不节省任何空间。

在您存储的未压缩表示中:

• 每组由 3 个符号组成的规则；和
• 18 个(在您的示例中)个符号。

这可以存储在 1R+18S 中(其中 R 是存储规则所需的空间，S 是存储符号所需的空间)

在您认为的压缩表示中，您必须存储:

• 每组由 3 组符号组成的规则；
• 每组中的符号；和
• 将每组与下一组分隔开的另一个符号。

在您的第一个“压缩”表示中，我计算 1R+12S+8D(其中 D 是存储一个定界符所需的空间)。如果 S==D 那么这是 1R+20S —— 比你的未压缩表示多。

在您的其他两个“压缩”表示中，我计算相同:1R+12S+8D 和 1R+12S+8D。

我还没有弄清楚这种非压缩是您提案的基本特征，还是您选择的示例的偶然特征。

你是说，当你写那个的时候

the count of elements in combination is actually N

有些组合会有 3 个元素，其他的有 4 个，其他的有 2 个或 5 个等等？

我建议你澄清你的问题。

编辑:@bazeusz:现在看来您正在寻找集合的笛卡尔积。