我遇到了一个特定的问题并正在寻找一些算法来解决它。要解决的问题如下所述。
假设我们有如下组合
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 的笛卡尔乘积)
编辑:在对该主题进行更多研究后,我发现该问题在“图论”中被称为“最小集团覆盖”问题
问候, 巴兹
最佳答案
这不是一个真正的答案,更像是一个扩展评论。您的“压缩表示”实际上根本不节省任何空间。
在您存储的未压缩表示中:
- 每组由 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:现在看来您正在寻找集合的笛卡尔积。
关于algorithm - 从这些集合的组合中重新创建集合,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/3788508/