解决与依赖关系的简单打包组合

Question

这不是一个家庭作业问题,而是来自我正在研究的项目的一些问题.上图是一组盒子的包装配置,其中A,B,C,D在第一层上,E,F,G在第二层上.问题是如果这些方框是以随机顺序给出的,那么这些方框可以放在给定配置中的概率是多少？

放置的唯一条件是所有盒子需要从上到下放置,放置后不能移动.因此,不允许在现有盒子或浮动位置下滑动,但是可以为同一层上的盒子节省空间.例如,E只能在A和B已经到位时放置.如果处理顺序是AEB ...那么它不能被放置在指定的配置中,如果处理顺序是ACBE ...则可以正确放置E.

更具体的描述是将打包配置转换为一组依赖关系或先决条件.第一层上的ABCD具有0个依赖关系,而E的依赖关系是{A和B},F是{B和C},G是{C和D},相应的依赖关系必须在E或F或G发生之前发生.虽然它不适用于这个问题,但在某些问题中,依赖关系也可以是"或"关系而不是"和".

我想知道解决这个问题的一般确定性算法是什么,还是这类问题？我能想到的一种方法是以随机顺序生成A,B,C,D,E,F,G 10,000次,并且对于每个订单检查是否在调用每个元素时发生了相应的先决条件.然而,这种天真的想法是耗时的,并且不能产生确切的概率(我相信这个问题的答案是基于我实施的这种天真算法的1/18).

建议将不胜感激!

Answer 1

 E F G
A B C D

在您发布的这个特定实例中，有两种方法可以分别排列ABE和CDG，并且这两个组可以以任何方式交错。

4 * (3 + 4 - 1) choose 3 = 80

现在我们只能将其放置在和F之后的任何位置。分析 的指数分布，我们得到：BCF

{2: 12, 3: 36, 4: 64, 5: 80, 6: 80}

正如您所建议的，尝试为这组特定的依赖关系找到一个公式是“混乱的”。在这种情况下，我可能生成了交错的前两个金字塔，然后计算放置的方式F，因为组合解决方案似乎同样复杂。

为了一般地解决这样的问题，人们可以对图表进行搜索并利用对称性。在这种情况下，从 开始A类似于从D;开始。B和C。

Python 示例：

 E F G
A B C D