V2EX = way to explore
V2EX 是一个关于分享和探索的地方
现在注册
已注册用户请  登录
lihongming
V2EX  ›  程序员

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

  •  
  •   lihongming · 2020-09-07 11:53:20 +08:00 · 4818 次点击
    这是一个创建于 1299 天前的主题,其中的信息可能已经有所发展或是发生改变。

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

    结果效率太差,不行。

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

    22 条回复    2020-09-08 18:30:09 +08:00
    xuanbg
        1
    xuanbg  
       2020-09-07 12:20:36 +08:00   ❤️ 1
    2^32^26
    lihongming
        2
    lihongming  
    OP
       2020-09-07 12:30:25 +08:00   ❤️ 1
    想起来了,应该是各数之和的阶乘除以各数的阶乘
    (A + B + C + ...)! / (A! * B! * C! * ...)
    git00ll
        3
    git00ll  
       2020-09-07 13:18:38 +08:00
    楼主这题哪里做的,能发下链接吗
    lff0305
        4
    lff0305  
       2020-09-07 15:55:32 +08:00
    数学方式直接算:应该是指数生成函数
    crackhopper
        5
    crackhopper  
       2020-09-07 16:31:37 +08:00
    进一步优化,还需要找到 k!>i*1000000007 的对可以每个出现的 i,最小的 k 。可以快速简化计算。
    crackhopper
        6
    crackhopper  
       2020-09-07 16:32:43 +08:00
    刚才没考虑,还有除数,比较麻烦。当我之前没说
    flowfire
        7
    flowfire  
       2020-09-07 16:40:32 +08:00   ❤️ 1
    这不是排列组合吗。。。
    答案是(假设 a-z 分别代表各个字母的数量,大写 S 代表所有字母总数):
    A(S,S) / (A(a,a) * A(b,b) * ...... * A(z,z))
    flowfire
        8
    flowfire  
       2020-09-07 16:44:13 +08:00
    guonaihong
        9
    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
        10
    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
        11
    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
        12
    QingchuanZhang  
       2020-09-07 22:03:53 +08:00
    @lff0305 EGF 。。。
    lihongming
        13
    lihongming  
    OP
       2020-09-08 00:49:54 +08:00 via iPhone
    @guonaihong 是的,要全用上。比如给你 2 个 a 和 2 个 b,那么能组成 aabb, abab, abba, baab, baba, bbaa 六种字符串
    waruqi
        14
    waruqi  
       2020-09-08 07:39:58 +08:00 via Android
    不就是 26 进制的 26 位数累加迭代么,直接用个 uint64 累加遍历么,然后将每个 10 进制数转成 26 进制,按每位映射到对应字母就好了,迭代到 26 位后结束,uint64 不够 就换 uint128 uint256
    toaruScar
        15
    toaruScar  
       2020-09-08 10:30:43 +08:00
    难道这个不是基础的 permutations with pepetitions 吗?
    no1xsyzy
        16
    no1xsyzy  
       2020-09-08 15:38:09 +08:00
    @lihongming @flowfire @lff0305 @toaruScar 问题是,整除是不是模数空间上的群?
    当然,拿 BigInt 之类做归做,效率是问题。

    @waruqi uint32 遍历需要大约 42 秒
    uint64 已经要遍历到天荒地老。
    怎么会想到遍历的,服(
    no1xsyzy
        17
    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
        18
    flowfire  
       2020-09-08 16:07:01 +08:00
    @no1xsyzy #17 你这算法跟我的不一样吗。。。无非是表达方法不同罢了。。。

    A(m,m) 就是 m! 啊。。。。
    toaruScar
        19
    toaruScar  
       2020-09-08 17:40:10 +08:00 via iPhone
    @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
        20
    no1xsyzy  
       2020-09-08 17:59:21 +08:00
    刚地铁上突然意识到一点,整除有可能是模数空间上的群,因为给定整除,采用启发式算法的话,可能可行……
    等我稍微写写 test 一下
    no1xsyzy
        21
    no1xsyzy  
       2020-09-08 18:20:42 +08:00
    竟然是可以的…… 之前拍脑袋了
    已知整除的话,整除是模数空间上的群……
    那没关系了,用模数空间上的整除做就行了。
    no1xsyzy
        22
    no1xsyzy  
       2020-09-08 18:30:09 +08:00
    关于   ·   帮助文档   ·   博客   ·   API   ·   FAQ   ·   我们的愿景   ·   实用小工具   ·   5702 人在线   最高记录 6543   ·     Select Language
    创意工作者们的社区
    World is powered by solitude
    VERSION: 3.9.8.5 · 28ms · UTC 06:27 · PVG 14:27 · LAX 23:27 · JFK 02:27
    Developed with CodeLauncher
    ♥ Do have faith in what you're doing.