限制排列的数量

Question

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

假设我们有n个盒子和n个彩球（每个彩球都是不同种类的）。每个盒子只能装一些特定种类的彩球（如下例所示），并且一个盒子只能放一个彩球。 请阅读编辑部分。整个算法已在下面链接的帖子中进行了描述，但没有明确说明，因此我要求重新解释。

问题是: 多项式时间内我可以用多少种方法把彩球放进盒子里？

例如:

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。

- Chate

---

我搞砸了，因为还有一件事情我应该提到的。 - Chate

@Ripi2 我需要一分钟来处理它。您的解决方案复杂度是多少？您所谈论的是哪篇文章？我还必须提到，除了广泛接受的列表之外，一个盒子可接受列表的最大大小为0、1或2个元素。 - Chate

链接的线程很难拼凑在一起。然而，根据您第二次编辑中的信息，我相信可以使用FKT算法在多项式时间内解决这个问题。如果您选择“全部接受”的弹珠和某个盒子B，并将它们从图中移除，则剩余的图不包含K_3,3作为子图，因此FKT算法应该适用于计算完美匹配，并对每个初始盒子B的选择重复此过程。 - kcsquared

@kcsquared，找到完美匹配数量的复杂度是多少？答案可能非常大，约为10^18。 - Chate

@kcsquared，我不太明白你是如何处理“全部接受”的弹珠的。你能具体说明一下吗？最好能用例子来演示一下。 - Chate

Answer 1

正如评论中所指出的，https://cs.stackexchange.com/questions/19924/counting-and-finding-all-perfect-maximum-matchings-in-general-graphs 是这个问题，提供了处理该问题的论文链接，而计算匹配数是#P完全问题。我建议找到这些论文。

至于动态规划，只需编写递归解决方案，然后进行记忆化即可。（这是自顶向下的方法，几乎总是更容易的方法。）对于固定（且相当小）数量的箱子的堆栈交换问题，这种方法是可行的。不幸的是，在您的问题变体中，如果箱子数量较大，则朴素递归版本看起来像这样（未经测试，可能会有错误）。

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个盒子的动态规划方法将变得更快，但你仍然只能处理比朴素解决方案稍微大一点的问题。因此，请查看研究以获取比这种动态规划方法更好的想法。

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

- btilly