4

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

假设我们有如下组合

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 的笛卡尔积）

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

问候，巴兹

4

1 回答 1

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：现在看来您正在寻找集合的笛卡尔积。

于 2010-09-24T16:54:44.853 回答