Number of restricted arrangements

user_17245497 0
Viewed 184

I am looking for a faster way to solve this problem:

Let's suppose we have n boxes and n marbles (each of them has a different kind). Every box can contain only some kinds of marbles (It is shown it the example below), and only one marble fits inside one box. Please read the edits. The whole algorithm has been described in the post linked below but it was not precisely described, so I am asking for a reexplenation.

The question is: In how many ways can I put marbles inside the boxes in polynomial time?

Example:

n=3

Marbles: 2,5,3

Restrictions of the i-th box (i-th box can only contain those marbles): {5,2},{3,5,2},{3,2}

The answer: 3, because the possible positions of the marbles are: {5,2,3},{5,3,2},{2,5,3}

I have a solution which works in O(2^n), but it is too slow. There are also one limitation about the boxes tolerance, which I don't find very important, but I will write them also. Each box has it's own kind-restrictions, but there is one list of kinds which is accepted by all of them (in the example above this widely accepted kind is 2).

Edit: I have just found this question but I am not sure if it works in my case, and the dynamic solution is not well described. Could somebody clarify this? This question was answered 4 years ago, so I won't ask it there. https://math.stackexchange.com/questions/2145985/how-to-compute-number-of-combinations-with-placement-restrictions?rq=1

Edit#2: I also have to mention that excluding widely-accepted list the maximum size of the acceptance list of a box has 0 1 or 2 elements.

Edit#3: This question refers to my previos question(Allowed permutations of numbers 1 to N), which I found too general. I am attaching this link because there is also one more important information - the distance between boxes in which a marble can be put isn't higher than 2.

combinations combinatorics algorithm
1 Answers

As noted in the comments, https://cs.stackexchange.com/questions/19924/counting-and-finding-all-perfect-maximum-matchings-in-general-graphs is this problem, with links to papers on how to tackle it, and counting the number of matchings is #P-complete. I would recommend finding those papers.

As for dynamic programming, simply write a recursive solution and then memoize it. (That's top down, and is almost always the easier approach.) For the stack exchange problem with a fixed (and fairly small) number of boxes, that approach is manageable. Unfortunately in your variation with a large number of boxes, the naive recursive version looks something like this (untested, probably buggy):

def solve (balls, box_rules):
    ball_can_go_in = {}
    for ball in balls:
        ball_can_go_in[ball] = set()
    for i in range(len(box_rules)):
        for ball in box_rules[i]:
            ball_can_go_in[ball].add(i)

    def recursive_attempt (n, used_boxes):
        if n = len(balls):
            return 1
        else:
            answer = 0
            for box in ball_can_go_in[balls[n]]:
                if box not in used_boxes:
                    used_boxes.add(box)
                    answer += recursive_attempt(n+1, used_boxes)
                    used_boxes.remove(box)
             return answer

    return recursive_attempt(0, set())

In order to memoize it you have to construct new sets, maybe use bit strings, BUT you're going to find that you're calling it with subsets of n things. There are an exponential number of them. Unfortunately this will take exponential time AND use exponential memory.

If you replace the memoizing layer with an LRU cache, you can control how much memory it uses and probably still get some win from the memoizing. But ultimately you will still use exponential or worse time.

If you go that route, one practical tip is sort the balls by how many boxes they go in. You want to start with the fewest possible choices. Since this is trying to reduce exponential complexity, it is worth quite a bit of work on this sorting step. So I'd first pick the ball that goes in the fewest boxes. Then I'd next pick the ball that goes in the fewest new boxes, and break ties by fewest overall. The third ball will be fewest new boxes, break ties by fewest boxes not used by the first, break ties by fewest boxes. And so on.

The idea is to generate and discover forced choices and conflicts as early as possible. In fact this is so important that it is worth a search at every step to try to discover and record forced choices and conflicts that are already visible. It feels counterintuitive, but it really does make a difference.

But if you do all of this, the dynamic programming approach that was just fine for 5 boxes will become faster, but you'll still only be able to handle slightly larger problems than a naive solution. So go look at the research for better ideas than this dynamic programming approach.

(Incidentally the inclusion-exclusion approach has a term for every subset, so it also will blow up exponentially.)

user_5854110
Related