解决具有依赖关系的简单打包组合 [英] Solve a simple packing combination with dependencies

问题描述

这不是家庭作业问题，而是我正在从事的项目中提出的问题.上图是一组盒子的包装配置，其中A，B，C，D在第一层，E，F，G在第二层.问题是，如果盒子以随机顺序给出，那么盒子可以以给定配置放置的概率是多少?

This is not a homework question, but something that came up from a project I am working on. The picture above is a packing configuration of a set of boxes, where A,B,C,D is on the first layer and E,F,G on the second layer. The question is that if the boxes are given in a random order, what is the probability that the boxes can be placed in the given configuration?

放置的唯一条件是所有盒子都需要从上向下放置，并且一旦放置就无法移动.因此，不允许在现有框下滑动或浮动放置，但是可以在同一层上为框节省空间.例如，仅当A和B已经就位时才可以放置E.如果处理顺序为AEB ...，则无法将其放置在指定的配置中；如果处理顺序为ACBE ...，则可以正确放置E.

The only condition for the placement is all the boxes need to be placed from top down and cannot be moved once placed. Therefore no sliding under the existing box or floating placement is allowed, but it's okay to save room for the box on the same layer. For example, E can only be placed when A and B are already in place. If the handing order is AEB... then it cannot be placed in the specified configuration, if the handing sequence is ACBE... then E can be correctly placed.

更详细的描述是将打包配置转换为一组依赖项或先决条件.第一层的ABCD具有0个依存关系，而E的依存关系为{A和B}，F的依存关系为{B和C}，而G的依存关系为{C和D}，则相应的依存关系必须在E或F或G发生之前发生.同样，尽管它不适用于此问题，但在某些问题中，依赖关系也可以是或"关系，而不是和".

A more formulated description is to translate the packing configuration to a set of dependencies, or prerequisites. ABCD on the first layer has 0 dependencies, while dependencies of E are {A and B}, F are {B and C}, and G are {C and D}, the corresponding dependencies must happen before E or F or G happens. Also while it doesn't apply to this problem, in some problem the dependencies could also be of a "or" relationship instead of "and".

我想知道解决此问题或此类问题的通用确定性算法是什么?我想到的一种方法是，以10,000次随机顺序生成A，B，C，D，E，F，G，并针对每个顺序检查调用每个元素时是否发生了相应的先决条件.但是，这种幼稚的想法很耗时，并且无法产生确切的概率(我相信根据我实现的这种幼稚算法，这个问题的答案是〜1/18).

I wonder what are the general deterministic algorithms to solve this, or this class of problem? A way I could think of is generating A,B,C,D,E,F,G in random order for 10,000 times and for each order check if the corresponding prerequisites have happened when each element is called. This naive idea, however, is time consuming and cannot produce the exact probability(I believe the answer to this problem is ~1/18 based on this naive algorithm I implemented).

我们将不胜感激！

推荐答案

 E F G
A B C D

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

In this particular instance you posted, there are two ways each to arrange ABE and CDG, and the two groups can be interleaved any which way.

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

现在我们只剩下将F放在B和C之后的任何位置.分析F的索引分布，我们得到:

Now we're left with placing F anywhere after B and C. Analyzing the distribution of the index of F, we get:

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

正如您所建议的那样，试图为这组特定的依赖项提供一个公式是混乱".在这种情况下，我可能已经生成了交织的前两个金字塔，然后计算了在每个金字塔中放置F的方式，因为组合解决方案似乎同样复杂.

Trying to come up for a formula for this particular set of dependencies is, as you suggest, "messy." In this case, I might have generated the interleaving first two pyramids and then count the ways to place F in each one since a combinatoric solution seems just as complicated.

通常要解决这样的问题，可以对图形进行搜索并利用对称性.在这种情况下，以A开头类似于以D开头； B和C.

To scale a problem like this generally, one could run a search through the graph as well as exploit symmetries. In this case starting with A would be akin to starting with D; B with C.

Python示例:

nodes = {
  'A': {
    'neighbours': ['B','C','D','E','F','G'], 'dependency': set()},
  'B': {
    'neighbours': ['A','C','D','E','F','G'], 'dependency': set()},
  'C': {
    'neighbours': ['A','B','D','E','F','G'], 'dependency': set()},
  'D': {
    'neighbours': ['A','B','C','E','F','G'], 'dependency': set()},
  'E': {
    'neighbours': ['C','D','F','G'], 'dependency': set(['A','B'])},
  'F': {
    'neighbours': ['A','D','E','G'], 'dependency': set(['B','C'])},
  'G': {
    'neighbours': ['A','B','E','F'], 'dependency': set(['C','D'])}
}

def f(key, visited):
  if len(visited) + 1 == len(nodes):
    return 1

  if nodes[key]['dependency'] and not nodes[key]['dependency'].issubset(visited):
    return 0

  result = 0

  for neighbour in nodes[key]['neighbours']:
    if neighbour not in visited:
      _visited = visited.copy()
      _visited.add(key)
      result += f(neighbour, _visited)

  return result

print 2 * f('A', set()) + 2 * f('B', set()) # 272

# Probability = 272 / 7! = 17 / 315 = 0.05396825396825397

这篇关于解决具有依赖关系的简单打包组合的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！