我正在寻找一个更快解决这个问题的方法:
假设我们有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。