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

付费问个数组排列问题

  •  
  •   nicevoice · 2021-02-09 18:25:23 +08:00 · 1592 次点击
    这是一个创建于 1143 天前的主题,其中的信息可能已经有所发展或是发生改变。

    已知:允许两个组合之间一个数字相同,5 个整数的组合,1000 个组合至少需要多少个整数?

    组合 1:1,2,3,4,5

    组合 2:1,6,7,8,9

    组合 3:2,6,10,11,12

    ...

    已知:允许两个组合之间一个数字相同,5 个整数的组合,1000 个组合至少需要多少个整数? 组合 1:1,2,3,4,5 组合 2:1,6,7,8,9 组合 3:2,6,10,11,12 谢谢,求多少个,付费求解。

    14 条回复    2021-02-10 00:06:50 +08:00
    waytoexplorewhat
        1
    waytoexplorewhat  
       2021-02-09 20:02:16 +08:00
    两个组合之间一个数字相同,那 1000 个组合共用 1 个整数,其他数字不同就好了。共 4001 个整数
    chocovon
        2
    chocovon  
       2021-02-09 20:45:28 +08:00
    每 15 个数就可以刚好生成 6 个组合,所以只需要 1000/6=166 个这样的 15 个数生成 996 个组合,余下 4 个组合需要至少 14 个数,总共至少需要 166*15+14=2504 个数
    Raven316
        3
    Raven316  
       2021-02-09 21:36:36 +08:00
    我没法用数学的方法来计算,所以我写了一个程序,然后跑了一下。

    程序的思路是:
    一开始只有一个元素的 list:[[1,2,3,4,5]]

    接下来尝试 999 次扩张这个数组:
    1 如果可以不增加所有数组的最大值的情况下,添加一个 5 整数组合,那就添加进去
    2 如果在不增加最大值的情况下无法添加组合,那么遍历所有可能,取增加最大值幅度最小的可能。(在某个时间以后,增加的幅度不是 0 就是 1,我无法证明为什么,只是观察到这个现象)

    注意:以上有两个原则
    1 没有取所有可能,只是取了增加最大值幅度最小的可能
    2 没有取所有同等条件的可能,只是任意取了一个。

    因为我发现如果穷举的话,个人电脑是不可能的,而且我是用 python 写的程序。

    以下稍微证明一下程序的逻辑(不严谨,但是我相信是正确的):

    明确一个概念:
    首先在这个 list 中,所有数字的地位都是同等的,他们只是不同的 symbol,因为并没有数学运算,所以,你可以想象,给定 5 个数字,最多一个组合,给定 9 个数字,最多两个组合,等等,组合个数和数字个数必然是单调的递增关系,因此,我的做法相当于,先尽量利用目前已有的数字个数,得出现有的数字个数可能的最大组合数,然后增加数字的数量,幅度取最小的可能,再把多出来的数字利用完(这里可以显然看出一下子增加过多的数字是没有任何必要的,应该取增加数字个数最小的幅度,而且在程序运行的实际结果看来,在后期基本上都是一次增加一个数字)

    那么为什么任取一种可能是正确的呢?
    你会发现如果给定 9 个数字,有很多种可能
    例如:
    [1,2,3,4,5],[1,6,7,8,9]
    [1,2,3,4,5],[2,6,7,8,9]
    ...
    等等

    但是它们都是“同构”的,你可以想象这些组合可能有很多种,但是具有相同的结构。

    因此,给定一个数字上限,你把它可能有的所有组合全部找了出来,你就找出了唯一可能的结构,具体形式是不重要的。这是我对随便取一种可能的证明(非常不严谨,我其实也有怀疑)。

    我跑的结果 167
    Raven316
        4
    Raven316  
       2021-02-09 21:41:39 +08:00
    。。。太大了贴不下我的天呐。

    https://pan.baidu.com/s/1fj2fqfOirMZoxnndY8UZGA

    vpj7
    nicevoice
        5
    nicevoice  
    OP
       2021-02-09 22:10:21 +08:00
    @Raven316 烦请列一下公式。谢谢
    Raven316
        6
    Raven316  
       2021-02-09 22:11:32 +08:00
    @nicevoice 没公式,每一步都是穷举出来的,有代码,写的很随意
    nicevoice
        7
    nicevoice  
    OP
       2021-02-09 22:15:30 +08:00
    @Raven316 1 和 130 这个组合不见了,。。。
    Raven316
        8
    Raven316  
       2021-02-09 22:21:17 +08:00
    @nicevoice 啥意思
    neteroster
        9
    neteroster  
       2021-02-09 22:39:34 +08:00
    我认为 #2 正确。
    neteroster
        10
    neteroster  
       2021-02-09 22:48:15 +08:00
    C1 = {A1,A2,A3,A4,A5}
    C2 = {A1,A6,A7,A8,A9}
    C3 = {A2,A6,A10,A11,A12}
    C4 = {A3,A7,A10,A13,A14}
    C5 = {A4,A8,A11,A13,A15}
    C6 = {A5,A9,A12,A14,A15}
    ---
    可以发现,C7 将无法使用 A1 - A15 中的任意一个数,因为 C1 - C6 中的每一个元素均被使用两次。形成 1000 组数就需要 166 个这样的 C1 - C6,并且还需要一组 (C1 - C4 (注意 C4 的最后一个数是 14 )),也就是 (166*15 + 14) 个数。
    XiaoxiaoPu
        11
    XiaoxiaoPu  
       2021-02-09 23:04:02 +08:00
    @neteroster 有问题的。C7 不能使用 A1-A15,不代表后面的集合不能用。
    Raven316
        12
    Raven316  
       2021-02-09 23:36:21 +08:00
    @neteroster 兄弟你写答案之前看看我 python 跑出来的答案呗,我觉得 167 就够了
    neteroster
        13
    neteroster  
       2021-02-09 23:55:11 +08:00 via Android
    @XiaoxiaoPu @Raven316 确实应该是我理解错了,我之前想成:不允许一个数字同时出现在两组以上了,仔细想想楼主应该不是这个意思。
    BiteTheDust
        14
    BiteTheDust  
       2021-02-10 00:06:50 +08:00
    n 个数能构成的 5 元组数量似乎与 The Kruskal-Macaulay function K_5(n)很相似?
    oeis.org/A123574
    关于   ·   帮助文档   ·   博客   ·   API   ·   FAQ   ·   我们的愿景   ·   实用小工具   ·   3273 人在线   最高记录 6543   ·     Select Language
    创意工作者们的社区
    World is powered by solitude
    VERSION: 3.9.8.5 · 24ms · UTC 11:51 · PVG 19:51 · LAX 04:51 · JFK 07:51
    Developed with CodeLauncher
    ♥ Do have faith in what you're doing.