我正在寻找一个更快的方法来解决这个问题:
假设我们有n个盒子andn marbles(他们每个人都有不同的种类)。每个盒子只能装几种弹珠(如下面的例子所示)，并且只有一个大理石适合放在一个盒子里．请阅读编辑。整个算法已经在下面链接的帖子中描述了，但它没有精确地描述，所以我要求重新解释。
问题是:在多项式时间里有多少种方法可以把玻璃球放进盒子里?
的例子:
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)。
编辑:我刚刚发现了这个问题，但我不确定它是否适用于我的情况，并且动态解决方案没有很好地描述。有人能解释一下吗?这个问题4年前就有答案了，所以我就不在这里问了。https://math.stackexchange.com/questions/2145985/how-to-compute-number-of-combinations-with-placement-restrictions?rq=1
编辑# 2:我还必须提到，除广泛接受的列表外，一个盒子的接受列表的最大大小有0个1或2个元素。
编辑# 3:这个问题指的是我之前的问题(允许1到N的排列)，我觉得这个问题太笼统了。我附上这个链接是因为还有一个更重要的信息——可以放置弹珠的盒子之间的距离不大于2。
正如评论中所指出的，https://cs.stackexchange.com/questions/19924/counting-and-finding-all-perfect-maximum-matchings-in-general-graphs就是这个问题，有关于如何解决它的论文的链接，并且计算匹配的数量是# p -complete。我建议你去找那些论文。
对于动态规划，简单地写一个递归解，然后记住它。(这是自上而下的，而且几乎总是更简单的方法。)对于具有固定数量(并且相当少)的盒的堆栈交换问题，这种方法是可管理的。不幸的是，在包含大量框的变体中，原始递归版本看起来像这样(未经测试，可能有bug):
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个盒子的动态规划方法将变得更快，但你仍然只能处理比单纯的解决方案稍大的问题。所以，去研究一下比这种动态规划方法更好的想法吧。
(顺便说一下，包含-排除方法对每个子集都有一个术语，所以它也会呈指数增长。)