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

求解一个排列组合问题

  •  
  •   ziger · 177 天前 · 1528 次点击
    这是一个创建于 177 天前的主题,其中的信息可能已经有所发展或是发生改变。

    code 由 6 个英文字符[A-Z]组成,如 AAAAAA ; 要求每两个 code 最少有两个字符不同, 如 AAAAAA ,AAAABB ; 一共有多少种 code ?

    18 条回复    2023-11-29 13:35:19 +08:00
    i_have_to_pee
        1
    i_have_to_pee  
       177 天前   ❤️ 1
    26^6-26
    dyyseo
        2
    dyyseo  
       177 天前
    10156900
    tool2d
        3
    tool2d  
       177 天前
    @dyyseo 一看就是暴力递归。
    kphcdr
        4
    kphcdr  
       177 天前
    chatgpt: 285610000
    文心一言:总共有 4302433444519237641338639371120181313362464693274530819581089299121177848932103525919463014410024186049242136804762844025498706102485253056693723744312089378816 种不同的 code 满足条件
    clue
        5
    clue  
       177 天前
    26^5 种吧?把某一位当校验位,应该能保证校验位一定不同
    ziger
        6
    ziger  
    OP
       177 天前 via Android
    @i_have_to_pee 不可能只有 26 个不符合条件的吧😂😂
    ziger
        7
    ziger  
    OP
       177 天前 via Android
    @kphcdr 文心一言果然名不虚传
    aaramsiconm1
        8
    aaramsiconm1  
       177 天前
    没太看懂楼主题目,是要求每两个 code 最少有两个字符不同的 code 集合有多少个,还是这样的 code 集合中最多有多少种 code ?
    ziger
        9
    ziger  
    OP
       177 天前 via Android
    @aaramsiconm1 后者,最多有多少种 code
    ziger
        10
    ziger  
    OP
       177 天前
    @clue 应该是,如果只要求 1 位不同,那是 26^6 种, 要求 6 位全部不同,只有 26^1 种,中间应该是符合规律的,只是没想到严格一点的证明思路
    opengps
        11
    opengps  
       177 天前
    考虑了半天,我也是一楼的结果,26^6 标识全部,减掉 AAAAAA -ZZZZZZ 这 26 个极端不满足即可
    kphcdr
        12
    kphcdr  
       176 天前
    @kphcdr #4
    gydi
        13
    gydi  
       176 天前
    26 ^ 6 - 6 * 26 * 25 - 26
    要减去 AAAAAB 和 AAAAAA 这两种吧
    lewuyang
        14
    lewuyang  
       176 天前
    @clue 我觉得就是这个结果。
    w16311
        15
    w16311  
       176 天前   ❤️ 1
    @ziger 把 code 当作一个树,正常的排列因为每个叶子( A ,B ,C...)都是不一样的可以确保每个 code 至少有一位不同。同理,把叶子结点囊括 2 个 letter 即可且保证两个 letter 完全不一样,这样的叶子结点可选元素有 26 个,最后的解为 26^4*26=26^5 。
    ps:证明 2letter 完全不同的最大集合包含元素个数为 26 ,可用反证法。
    NoOneNoBody
        16
    NoOneNoBody  
       176 天前
    两位组合,四位排列
    f056917
        17
    f056917  
       176 天前
    266 - (26 * C(5, 1) * 255) - (26 * C(5, 2) * 254) - (26 * C(5, 3) * 253) ≈ 1,535,316,000
    edward1987
        18
    edward1987  
       175 天前
    虽然我想的也是 26^5 ,但是暴力求解的结果小于这个理论值。
    https://jsfiddle.net/vdtn40hy/8/
    在集合大小为 5 的情况下,分别跑了 长度为 3 、4 、5 、6 的 CODE 集合大小,都比 x^(n-1)小
    run(3); // 19
    run(4);// 89
    run(5);// 421
    run(6);// 2045
    关于   ·   帮助文档   ·   博客   ·   API   ·   FAQ   ·   实用小工具   ·   3992 人在线   最高记录 6679   ·     Select Language
    创意工作者们的社区
    World is powered by solitude
    VERSION: 3.9.8.5 · 29ms · UTC 04:02 · PVG 12:02 · LAX 21:02 · JFK 00:02
    Developed with CodeLauncher
    ♥ Do have faith in what you're doing.