脑子突然不好使了,请各位大佬帮我想想这个算法

2020-09-07 11:53:20 +08:00
 lihongming

已知有一个长度为 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;
}

结果效率太差,不行。

我又想用数学的方法直接算,可脑子怎么也想不起该怎么算了,求大佬们指点。

4857 次点击
所在节点    程序员
22 条回复
xuanbg
2020-09-07 12:20:36 +08:00
2^32^26
lihongming
2020-09-07 12:30:25 +08:00
想起来了,应该是各数之和的阶乘除以各数的阶乘
(A + B + C + ...)! / (A! * B! * C! * ...)
git00ll
2020-09-07 13:18:38 +08:00
楼主这题哪里做的,能发下链接吗
lff0305
2020-09-07 15:55:32 +08:00
数学方式直接算:应该是指数生成函数
crackhopper
2020-09-07 16:31:37 +08:00
进一步优化,还需要找到 k!>i*1000000007 的对可以每个出现的 i,最小的 k 。可以快速简化计算。
crackhopper
2020-09-07 16:32:43 +08:00
刚才没考虑,还有除数,比较麻烦。当我之前没说
flowfire
2020-09-07 16:40:32 +08:00
这不是排列组合吗。。。
答案是(假设 a-z 分别代表各个字母的数量,大写 S 代表所有字母总数):
A(S,S) / (A(a,a) * A(b,b) * ...... * A(z,z))
flowfire
2020-09-07 16:44:13 +08:00
guonaihong
2020-09-07 16:55:38 +08:00
对这个问题感兴趣。这些字母是否是互斥事件吗?比如第一位是 26 种可能,互斥的话,第二种是 25 种可能。
我的理解,根据条件有 2 种解 一种,26 * 26 ....n,即 26 的 26 次方。二种是后者就是 26!。
如果是组合的话,就是把重复计算的除掉 m 种取 n 种 =m!/(m-n)!n!。
lff0305
2020-09-07 19:32:42 +08:00
简单写了个程序。题目没有讲太清楚(是否这些字母一定要全部使用)。这里为了简单就假设全部使用。

解法一:排列组合。生成字符串长度是 sum=a0+a1+a2+...+a25 。放 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));
}

// System.out.println(n + "," + k + " = " + r);
return r;
}


解法 2: GEF (指数生成函数)。这是个排列问题所以用指数生成函数。
对于 a: 有 a0 个 a 要放。写成指数函数形式 e0=e^(a0)/a0!
同样对于 b: 有 a1 个 b 要放。写成指数函数形式 e1=e^(a1)/a1!
等等等等
最后到 z, 有 a25 个 z 要放,写成指数函数形式 e25=e^(a25)/a5!

根据指数生成函数的理论,整个排列数就是
E=e0*e1*...*e25,中项 e^(sum)/sum! 的系数。

那么 E=[e^(a0)/a0!][e^(a1)/a1!]*...*[e25=e^(a25)/a25!]
= [e^(a0+a1+...+a25)]/[a0!*a1!*...*a25!]
= [e^sum]/[a0!*a1!*...*a25!]
e ^ sum sum !
= --------------------------- * --------------------
a0! *a1!* ... * a25 !) sum!

e ^ sum sum !
= --------------------------- * --------------------------
sum! a0! *a1!* ... * a25 !

要求的系数就是 ( sum!)/( a0! *a1!* ... * a25 ! )

写成程序就是


// Solve by GEF
private long solve2(int[] a) {
// expr e0 = e^a0/a0!, e1 = e^a1/a1! ... etc
// E = e0*e1*e2 .... * e25
// e^(a0+a1+...+a25)/(a0!*a1*a2*....*a25!)
// ? = e^(a0 + a1 + ... + a25)/(sum!)
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;
}
lff0305
2020-09-07 19:36:49 +08:00
排版乱了, 重新弄下

简单写了个程序。题目没有讲太清楚(是否这些字母一定要全部使用)。这里为了简单就假设全部使用。

解法一:排列组合。生成字符串长度是 sum=a0+a1+a2+...+a25 。放 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));
}

// System.out.println(n + "," + k + " = " + r);
return r;
}

```
解法 2: GEF (指数生成函数)。这是个排列问题所以用指数生成函数。
对于 a: 有 a0 个 a 要放。写成指数函数形式 e0=e^(a0)/a0!
同样对于 b: 有 a1 个 b 要放。写成指数函数形式 e1=e^(a1)/a1!
等等等等
最后到 z, 有 a25 个 z 要放,写成指数函数形式 e25=e^(a25)/a5!

根据指数生成函数的理论,整个排列数就是
E=e0*e1*...*e25,中项 e^(sum)/sum! 的系数。

那么
```
E=[e^(a0)/a0!][e^(a1)/a1!]*...*[e25=e^(a25)/a25!]
= [e^(a0+a1+...+a25)]/[a0!*a1!*...*a25!]
= [e^sum]/[a0!*a1!*...*a25!]
e ^ sum sum !
= --------------------------- * --------------------
a0! *a1!* ... * a25 !) sum!

e ^ sum sum !
= --------------------------- * --------------------------
sum! a0! *a1!* ... * a25 !
```
要求的系数就是 ( sum!)/( a0! *a1!* ... * a25 ! )

写成程序就是

```
// Solve by GEF
private long solve2(int[] a) {
// expr e0 = e^a0/a0!, e1 = e^a1/a1! ... etc
// E = e0*e1*e2 .... * e25
// e^(a0+a1+...+a25)/(a0!*a1*a2*....*a25!)
// ? = e^(a0 + a1 + ... + a25)/(sum!)
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;
}
```
QingchuanZhang
2020-09-07 22:03:53 +08:00
@lff0305 EGF 。。。
lihongming
2020-09-08 00:49:54 +08:00
@guonaihong 是的,要全用上。比如给你 2 个 a 和 2 个 b,那么能组成 aabb, abab, abba, baab, baba, bbaa 六种字符串
waruqi
2020-09-08 07:39:58 +08:00
不就是 26 进制的 26 位数累加迭代么,直接用个 uint64 累加遍历么,然后将每个 10 进制数转成 26 进制,按每位映射到对应字母就好了,迭代到 26 位后结束,uint64 不够 就换 uint128 uint256
toaruScar
2020-09-08 10:30:43 +08:00
<amp-youtube data-videoid="Mm0VNPars2M" layout="responsive" width="480" height="270"></amp-youtube>难道这个不是基础的 permutations with pepetitions 吗?
no1xsyzy
2020-09-08 15:38:09 +08:00
@lihongming @flowfire @lff0305 @toaruScar 问题是,整除是不是模数空间上的群?
当然,拿 BigInt 之类做归做,效率是问题。

@waruqi uint32 遍历需要大约 42 秒
uint64 已经要遍历到天荒地老。
怎么会想到遍历的,服(
no1xsyzy
2020-09-08 15:47:49 +08:00
简单重排一下的话
(A + B + C + ...)! / (A! * B! * C! * ...)
其实等于
A!/A! * ((A+B)!/A!/B!) * ((A+B+C)!/(A+B)!/C!) * ...
每块都是整数。
flowfire
2020-09-08 16:07:01 +08:00
@no1xsyzy #17 你这算法跟我的不一样吗。。。无非是表达方法不同罢了。。。

A(m,m) 就是 m! 啊。。。。
toaruScar
2020-09-08 17:40:10 +08:00
@flowfire #18 @no1xsyzy 的意思是,题目最后一步要求 mod,那不如就直接在 mod 的空间里计算。就是每步运算之后都去来个 mod,这样数字能小一点。然而 mod 空间里只有加减乘能用,也就是
( a + b) % c = ( ( a % c ) + ( b % c ) ) % c
( a * b) % c = ( ( a % c ) * ( b % c ) ) % c
( a – b) % c = ( ( a % c ) – ( b % c ) ) % c
而( a / b) % c 是没有这个性质的
重排一下发现可以相消,于是分母都是 1,也就是只剩下乘法了。
no1xsyzy
2020-09-08 17:59:21 +08:00
刚地铁上突然意识到一点,整除有可能是模数空间上的群,因为给定整除,采用启发式算法的话,可能可行……
等我稍微写写 test 一下

这是一个专为移动设备优化的页面(即为了让你能够在 Google 搜索结果里秒开这个页面),如果你希望参与 V2EX 社区的讨论,你可以继续到 V2EX 上打开本讨论主题的完整版本。

https://www.v2ex.com/t/704808

V2EX 是创意工作者们的社区,是一个分享自己正在做的有趣事物、交流想法,可以遇见新朋友甚至新机会的地方。

V2EX is a community of developers, designers and creative people.

© 2021 V2EX