Solve a simple packing combination with dependencies

Question

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?

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.

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".

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).

And advice will be greatly appreciated!

Answer 1

 E F G
A B C D

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

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}

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.

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 example:

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