将球分配到尺寸有限的篮子

Question

几个小时以来，我一直在努力寻找这个问题的解决方案：我有 L 个球和 n 个篮子标记为 X1, X2, ... Xn ，每个容器可以容纳 LXn 个球。现在我想计算我可以将那些 L 个球分配到篮筐中的方式的数量。

例子：

有3个篮子X1、X2、X3，X1、X3的容量是2球，X2的容量是3球.现在 5 个球 被分配到这些篮子中：

X1 X2 X3

0 3 2
1 2 2
1 3 1
2 1 2
2 2 1
2 3 0

我想知道有多少种分配给定值的球的方法。

数学解：

p_n(x) = x^0 + x^1 + .. + x^(LXn)
P(x) = p_1(x) * ... * p_N(x)

关键是x^L前的系数（看下一个等式）表示分配给定L的方式数球进入 n 个篮筐。

对于上面的示例，这将导致
P(x) = (1+x+x^2) * (1+x+x^2+x^3) * (1+x+x^2) = 1 + 3x + 6x^2 + 8x^3 + 8x^4 + 6x^5 + 3x^6 + x^7
所以对于 L=5 它显示 6 种不同的排列方式

（来源：http://narkive.com/9a0CvErb.2（德语））

现在我的实际问题是：在 java 中有没有办法做到这一点或类似的事情？

谢谢！

Answer 1

"creating polynomials" 中解释的 link 方法为每个篮子创建一个多项式并将它们相乘。

您可以将多项式表示为系数向量，因此 p[i] 是度数 i 的系数。容量为 n 的篮子的多项式是长度为 n + 1 且所有系数都等于 1 的多项式。

您需要一种乘以多项式的方法，您可以在两个多项式的项上的两个嵌套循环中将其实现为成对乘法和加法。

最后，m 个球的所需数量是结果多项式的 p[m]。

这是一个快速 Java 实施。（免责声明：我对 Java 一点都不擅长。此代码在在线编译器中编译和运行，但可能不是很 Java-esque。）

import java.util.*;

public class Main
{
    static int[] basket(int n)
    {
        int[] p = new int[++n];

        while (n-- > 0) p[n] = 1;
        return p;
    }

    static int[] mult(int[] p, int[] q)
    {
        int[] r = new int[p.length + q.length - 1];

        for (int i = 0; i < p.length; ++i) {
            for(int j = 0; j < q.length; ++j) {
                r[i + j] += p[i] * q[j];
            } 
        }

        return r;
    }

    public static void main(String[] args)
    {
        int[] res = basket(0);

        res = mult(res, basket(2));
        res = mult(res, basket(3));
        res = mult(res, basket(2));

        System.out.println(res[5]);
    }
}

此代码段实现了将 5 个球分配到大小为 2、3 和 2 的篮子中的示例。起始多项式 basket(0) 只是常数 1，是多项式乘法的中性元素。

将球分配到尺寸有限的篮子

Distributing balls to baskets with limited size

java

algorithm

combinatorics