压缩/合并数字组合的算法

Question

使用赛马博彩场景，假设我有许多单独的投注来预测比赛的前 4 名选手 (superfecta)。

赌注如下...

1/2/3/4  
1/2/3/5  
1/2/4/3  
1/2/4/5  
1/2/5/3  
1/2/5/4 

我想做的是尽可能地组合或浓缩这些单独的组合。对于上面的投注，它们都可以浓缩成1行......

1/2/3,4,5/3,4,5

但是如果我从列表中删除最后一个赌注:1/2/5/4 ...

1/2/3/4  
1/2/3/5  
1/2/4/3  
1/2/4/5  
1/2/5/3  

压缩的赌注现在必须是 2 行:

1/2/3,4/3,4,5  
1/2/5/3  

算法会是什么样子？

Answer 1

我发现用漂亮的图片来思考这种事情是最容易的。我们尝试构建一些图表怎么样？

第一个例子

1/2/3/4  
1/2/3/5  
1/2/4/3  
1/2/4/5  
1/2/5/3  
1/2/5/4 

...可能看起来像这样，以图表形式:

从上到下的每条路径(例如 1->2->4->3)对应于初始格式中的一行。

如果我们从该图开始，那么(也许)我们可以在该图上运行一个小算法，以您正在寻找的方式简化它。这是我们将要尝试的:

• 从图表的顶部开始，逐级向下移动。 (第一层仅包含蓝色节点 1。)
• 对于当前层级的每个节点，计算 child 的数量。如果只有一个 child ，则跳过该节点。 (由于蓝色节点 1 只有一个 child ，我们将跳到绿色节点 2。)
• 对于多个 child 中的每一个，构建一个包含该 child 及其孙辈的集合。 (红色节点3有一个集合{3,4,5}，红色节点4有一个集合{3,4, 5}，红色5有一组{3,4,5}。)
• 如果这些集合中的任何一个相同，将关联的子/孙替换为包含子的单个节点，指向包含该集合的孙。 (因为所有三个红色节点都具有相同的集合，所以它们都被替换了。)

---

第二个例子

1/2/3/4  
1/2/3/5  
1/2/4/3  
1/2/4/5  
1/2/5/3 

...可能看起来像这样，以图表形式:

红色节点 3 和 4 具有相同的集合(即 {3,4,5})，因此它们被替换。红色节点 5 与红色节点 3 和 4 没有相同的集合，所以我们不用管它。

和以前一样，通过简化树的每条路径代表输出的一行。

(我没有介绍如果您在有曾孙辈的情况下替换 child /孙辈会发生什么情况。您可能实际上应该从最后一行开始，然后逐步向上。)