V2EX = way to explore
V2EX 是一个关于分享和探索的地方
现在注册
已注册用户请  登录
推荐学习书目
Learn Python the Hard Way
Python Sites
PyPI - Python Package Index
http://diveintopython.org/toc/index.html
Pocoo
值得关注的项目
PyPy
Celery
Jinja2
Read the Docs
gevent
pyenv
virtualenv
Stackless Python
Beautiful Soup
结巴中文分词
Green Unicorn
Sentry
Shovel
Pyflakes
pytest
Python 编程
pep8 Checker
Styles
PEP 8
Google Python Style Guide
Code Style from The Hitchhiker's Guide
Gawain
V2EX  ›  Python

如何优雅的解这个题?

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

    a=[1,2,3,4,5,6,7,8]

    b=[1,2,3,4,5,6,7,8]

    b=[1,2,3,4,5,6,7,8]

    已知 a + b + c = 16

    求全部 abc 的组合

    线性代数还是数组啥的,都还给老师了,只会 for 循环了...

    第 1 条附言  ·  101 天前
    修正一下题目的说明,语文不好,引起歧义了。

    假定有一串整数组成的数组,从中取出三个值,允许重复,三个值的和为一个特定值。

    那么,这样的组合有哪些?


    感谢回复中的各位大佬,这里我结合 7 楼和 14 楼给出的方案,写了个答案。

    from itertools import combinations,combinations_with_replacement
    import numpy as np


    X=852
    Y=[165,180,204,235,240,265,270,296,306,337,360,382,396,400]

    def summation(data):
    return np.sum(data) == X

    res = list(filter(test, list(combinations_with_replacement(Y,3))))
    print(res)

    输出为[(235, 235, 382), (240, 306, 306)]
    完美解决
    第 2 条附言  ·  101 天前
    res = list(filter(summation, list(combinations_with_replacement(Y,3))))

    上文那句写错了,不是 test...
    25 条回复    2022-08-22 17:15:00 +08:00
    Itoktsnhc
        1
    Itoktsnhc  
       102 天前
    呃 这是《三数之和》吗
    Itoktsnhc
        2
    Itoktsnhc  
       102 天前
    @Itoktsnhc
    如果是三数之和, 一般是做好排序,在循环中固定其中一个值,然后左右两侧指针遍历才能保证单调性。
    fkdtz
        3
    fkdtz  
       102 天前
    我先努力优雅的读懂这个题
    JasonLaw
        4
    JasonLaw  
       102 天前 via iPhone
    我不太理解“ 已知 a + b + c = 16”,a 、b 、c 不是数组吗?
    JasonLaw
        5
    JasonLaw  
       102 天前 via iPhone
    @fkdtz #3 me too
    singerll
        6
    singerll  
       102 天前
    题干里面是等于还是属于。。。
    如果是属于,b+c=16-a ,先列举 a 的值,再确定 b+c 的数组边界,然后在边界里面循环吧。比如 1+1+1 的组合,是不需要循环的。
    brucmao
        7
    brucmao  
       102 天前
    lyang
        8
    lyang  
       102 天前
    思考的时间,代码已经写完了,for 循环还好吧
    kiroter
        9
    kiroter  
       102 天前   ❤️ 2
    先遍历 a,b 相加得 ab, 在转 map ,遍历 c, key = 16-3, ab.get(key)
    kiroter
        10
    kiroter  
       102 天前
    key=16-c
    FYFX
        11
    FYFX  
       102 天前
    你给的这个例子就这个数据量为什么不循环,还是说这只是题目中的一个测试用例?
    BeautifulSoap
        12
    BeautifulSoap  
       102 天前 via Android
    9 楼思路对的,把 a 和 b 相加然后用 16 一个个去减,结果到 c 里找,存在的话就是对应的组合只需要 8x8+64 次计算,比穷举的 8x8x8 好

    可问题在于上面说的,总共就这么小的数组,直接穷举也没问题
    Gawain
        13
    Gawain  
    OP
       102 天前
    @JasonLaw
    @fkdtz
    @singerll

    我的错,应该 a b c 属于三个数组,是其中之一,相找这样的组合
    cccjh
        14
    cccjh  
       102 天前   ❤️ 3
    以前大学高数满分,现在只会普通思维了

    Gawain
        15
    Gawain  
    OP
       102 天前
    @FYFX
    @BeautifulSoap

    实际问题虽然不是这么小的数组,但是也多大,确实可以循环穷举。

    但是总觉得这样不够优雅

    在想是不是有别的数学方法 比如用 nump 数组操作之类的 但是这方面的知识早就忘光了

    总之,穷举完全没问题,就是抱着学习的态度,问问有没有别的方法
    Gawain
        16
    Gawain  
    OP
       102 天前
    @cccjh

    非常感谢
    ji39
        17
    ji39  
       102 天前
    能不能用心算
    wangyzj
        18
    wangyzj  
       102 天前
    @cccjh #14 我就喜欢这样的直给
    wxf666
        19
    wxf666  
       102 天前   ❤️ 1
    这样?我没测试过


    from bisect import bisect_left, bisect_right

    a = set([1, 2, 3, 4, 5, 6, 7, 8])
    b = sorted([1, 2, 3, 4, 5, 6, 7, 8])
    c = set([1, 2, 3, 4, 5, 6, 7, 8])

    for x in a:
      for i in range(bisect_left(b, 16 - x - max(c)), bisect_right(b, 16 - x - min(c))):
       print(f'{x} + {b[i]} + {16 - x - b[i]} = 16')
    Jooooooooo
        20
    Jooooooooo  
       102 天前
    你搜下 three sum leetcode.

    这题当然暴力解是可以的, 不过有更好的方法.
    fkdtz
        21
    fkdtz  
       102 天前
    three sum 乃至于 n sum 问题
    wangtian2020
        22
    wangtian2020  
       102 天前
    选择内存最小方案 ×
    选择运行时间最短方案 ×
    考虑到循环总次数尚可接受,选择不用动脑自己写的最快的 for 循环方案 √
    Gawain
        23
    Gawain  
    OP
       102 天前
    @brucmao
    @Jooooooooo

    非常感谢,这个貌似就是我要找到
    UIXX
        24
    UIXX  
       102 天前
    比较同意循环方案,省脑。

    实际上,从几何的角度看,就是一个求平面上格点的问题。由于公式的特殊性(整个平面的倾斜角为 45 度),以及数值的特殊性(和为偶数),这些格点并不需要计算,可以被直接列出来。复杂度等同于输出规模。

    和为奇数的情况也差不多。

    如果公式变了(平面倾斜度不再是 45 度,甚至不再是平面),那代数法更好。
    akira
        25
    akira  
       102 天前
    @cccjh #14 楼 老凡尔赛。。 高数勉强及格的路过。。
    关于   ·   帮助文档   ·   API   ·   FAQ   ·   我们的愿景   ·   广告投放   ·   感谢   ·   实用小工具   ·   4620 人在线   最高记录 5497   ·     Select Language
    创意工作者们的社区
    World is powered by solitude
    VERSION: 3.9.8.5 · 48ms · UTC 09:16 · PVG 17:16 · LAX 01:16 · JFK 04:16
    Developed with CodeLauncher
    ♥ Do have faith in what you're doing.