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

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。

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

你的意思是，当你写下这个的时候

组合元素的数量
实际上是N

，某些组合将具有 3 个元素，其他组合将具有 4 个元素，其他组合将具有 2 或 5 个元素等？

我建议你澄清你的问题。

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