限制性安排的数量

我正在寻找一种更快的方法来解决这个问题：

假设我们有n boxes and n 弹珠（他们每个人都有不同的种类）。每个盒子只能包含某种弹珠（如下例所示），并且只有一个大理石适合装在一个盒子里. 请阅读编辑内容。整个算法已在下面链接的帖子中进行了描述，但没有精确描述，所以我要求重新解释。

问题是：我可以通过多少种方式在多项式时间内将弹珠放入盒子中？

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}

我有一个在 O(2^n) 中工作的解决方案，但它太慢了。关于盒子容差还有一个限制，我认为这不是很重要，但我也会写它们。每个盒子都有自己的种类限制，但有一个所有盒子都接受的种类列表（在上面的示例中，广泛接受的种类是 2）。

Edit:我刚刚发现这个问题，但我不确定它是否适合我的情况，并且动态解决方案没有得到很好的描述。有人可以澄清这一点吗？这个问题4年前就已经回答了，所以我不会在那里问。https://math.stackexchange.com/questions/2145985/how-to-compute-number-of-combinations-with-placement-restrictions?rq=1 https://math.stackexchange.com/questions/2145985/how-to-compute-number-of-combinations-with-placement-restrictions?rq=1

Edit#2:我还必须提到，除了广泛接受的列表之外，一个盒子的接受列表的最大大小有 0、1 或 2 个元素。

Edit#3:这个问题参考了我之前的问题（允许的数字 1 到 N 的排列 https://stackoverflow.com/questions/69740876/allowed-permutations-of-numbers-1-to-n），我发现这太笼统了。我附上此链接是因为还有一个更重要的信息 - 可以放置弹珠的盒子之间的距离不大于 2。

正如评论中指出的那样，https://cs.stackexchange.com/questions/19924/counting-and-finding-all-perfect-maximum-matchings-in-general-graphs https://cs.stackexchange.com/questions/19924/counting-and-finding-all-perfect-maximum-matchings-in-general-graphs就是这个问题，其中包含有关如何解决该问题的论文链接，并且计算匹配的数量是#P-complete。我建议找到那些论文。

至于动态规划，只需编写一个递归解决方案，然后将其记住即可。 （这是自上而下的，而且几乎总是更简单的方法。）对于固定（且相当少）数量的框的堆栈交换问题，该方法是易于管理的。不幸的是，在您的带有大量盒子的变体中，天真的递归版本看起来像这样（未经测试，可能有错误）：

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

为了记住它，你必须构造新的集合，也许使用位字符串，但是你会发现你正在用 n 个事物的子集来调用它。它们的数量呈指数级增长。不幸的是，这将花费指数时间并使用指数内存。

如果用 LRU 缓存替换记忆层，您可以控制它使用的内存量，并且可能仍然可以从记忆中获得一些好处。但最终你仍然会使用指数或更差的时间。

如果你走这条路，一个实用的技巧是根据球放入盒子的数量对球进行分类。你想从尽可能少的选择开始。由于这是试图降低指数复杂性，因此在这个排序步骤上做大量的工作是值得的。所以我会首先选择进入盒子最少的球。然后我接下来会选择进入新盒子最少的球，并以最少的总数打破平局。第三个球将是最少的新盒子，以最少的第一个球未使用的盒子打破平局，以最少的盒子打破平局。等等。

这个想法是尽早产生和发现被迫的选择和冲突。事实上，这一点非常重要，值得每一步都进行搜索，尝试发现和记录已经可见的被迫选择和冲突。这感觉违反直觉，但确实有所作为。

但是，如果您完成所有这些，适用于 5 个盒子的动态编程方法将会变得更快，但您仍然只能处理比简单解决方案稍大的问题。因此，请查看研究，寻找比这种动态规划方法更好的想法。

（顺便说一句，包含-排除方法对每个子集都有一个术语，因此它也会呈指数级增长。）