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.
And advice will be greatly appreciated!
Aucun commentaire:
Enregistrer un commentaire