算法: 代表字母的整形数组组合字符串的可能性
问题描述
已知有一个长度为 26 的整型数组, 分别代表 26 个字母的个数, 问这些字母能组成多少种不同的字符串(取模 1000000007).
问题求解
纯暴力
开始觉得很简单, 纯迭代问题, 抬手就来.
int calc(int[] nums) {
int ret = 0;
for (int i = 0; i < nums.length; i++) {
if (nums[i] > 0) {
nums[i]--;
ret += calc(nums);
ret %= 1000000007;
nums[i]++;
}
}
return ret > 0 ? ret : 1;
}
结果超时, 不行, 看来只能用数学方法求解.
数学方法
$$ Sum=\dfrac{A_{字母总数}^{字母总数}}{A_{A的数量}^{A的数量}\times……\times A_{2}^{2}} $$
题目没有讲太清楚(是否这些字母一定要全部使用), 这里为了简单就假设全部使用.
解法一：排列组合.
生成字符串长度是 $sum=a_0+a_1+a_2+…+a_{25}$.
放 $a$ , 有$(sum, a0)$种选择的方法; 放$ b$, 有$(sum - a0, a1)$种方法; 放 $c$, 有$(sum - a0 - a1, a2)$种方法…..直到最后
程序
private long solve1(int[] letters) {
int sum = 0;
for (int c : letters) {
sum += c;
}
BigInteger r = BigInteger.ONE;
for (int c : letters) {
BigInteger s = choose(sum, c);
r = r.multiply(s);
sum -= c;
}
return r.longValue();
}
private static BigInteger choose(int n, int k) {
BigInteger r = BigInteger.ONE;
for (int i=0; i<k; i++) {
r = r.multiply(BigInteger.valueOf(n - i));
}
for (int i=2; i<=k; i++) {
r = r.divide(BigInteger.valueOf(i));
}
return r;
}
解法 2: EGF (指数生成函数)。
这是个排列问题所以用指数生成函数.
对于$a$: 有$ a_0$ 个$ a$ 要放.写成指数函数形式 $e_0=e^{(a_0)/a_0!}$ .
同样对于 $b$ : 有 $a_1$ 个 $b$ 要放。写成指数函数形式 $e_1=e^{(a_1)/a_1!}$ 等等等等 最后到 $z$ , 有 $a_{25}$ 个 z 要放，写成指数函数形式 $e_{25}=e^{(a_{25})/a_5!} $根据指数生成函数的理论，整个排列数就是 $E=e_0e_1…*e_{25}$
中项 $e^{(sum)/sum!}$ 的系数.
// Solve by GEF
private long solve2(int[] a) {
int sum = 0;
for (int c : a) {
sum += c;
}
BigInteger p = p(sum);
BigInteger c = BigInteger.ONE;
for (int i : a) {
c = c.multiply(p(i));
}
return p.divide(c).longValue();
}
private BigInteger p(int sum) {
BigInteger r = BigInteger.ONE;
for (int i= sum; i>=2; i--) {
r = r.multiply(BigInteger.valueOf(i));
}
return r;
}
完毕.