V2EX = way to explore
V2EX 是一个关于分享和探索的地方
现在注册
已注册用户请  登录
V2EX 提问指南
naix1573
V2EX  ›  问与答

Python 高效遍历 集合所有子集的全组合

  •  
  •   naix1573 · 2020-08-25 10:58:28 +08:00 · 986 次点击
    这是一个创建于 1535 天前的主题,其中的信息可能已经有所发展或是发生改变。

    最近在用 Python 做一个图形化界面 tkinter 的小工具,目的是为了把一个集合里的所有组合给遍历出来,与另外给定的一个值相匹配,把相等的那些组合输出。

    本来用的 combinations,但是后来集合里的数一多之后,程序容易未响应

    后来查到用二进制位运算的方法,https://blog.csdn.net/bquau/article/details/88836357

    但是当集合里的数达到 47 个的时候,程序也未响应了,不知道各位大佬有没有什么办法啊~

    arr = "$57,297.60 $53,573.02 $109,771.72 $43,386.68 $50,667.74 $50,171.84 $50,116.20 $54,679.96 $180,469.76 $48,363.96 $53,830.44 $54,882.94 $39,291.00 $42,284.76 $56,562.80 $50,566.64 $49,074.30 $49,547.44 $57,377.27 $78,517.60 $98,067.60 $59,814.15 $48,171.20 $53,398.52 $53,855.76 $159,975.77 $104,100.16 $49,196.98 $56,236.80 $48,394.16 $48,516.08 $51,086.12 $176,979.69 $48,359.82 $38,507.20 $47,707.80 $45,640.80 $45,691.18 $39,096.42 $39,102.40 $48,984.36 $101,147.01 $96,127.95 $38,416.00 $36,247.80 $35,989.12 $40,142.10"

    su = "537754.94"

    7 条回复    2020-08-25 11:58:34 +08:00
    naix1573
        1
    naix1573  
    OP
       2020-08-25 11:31:58 +08:00
    找到一个 java 实现的,用着没问题,可惜我不知道这个用 python 要怎么写啊,头疼
    https://www.cnblogs.com/zlingh/p/4040742.html

    我把数组重新发一下 ['57297.60', '53573.02', '109771.72', '43386.68', '50667.74', '50171.84', '50116.20', '54679.96', '180469.76', '48363.96', '53830.44', '54882.94', '39291.00', '42284.76', '56562.80', '50566.64', '49074.30', '49547.44', '57377.27', '78517.60', '98067.60', '59814.15', '48171.20', '53398.52', '53855.76', '159975.77', '104100.16', '49196.98', '56236.80', '48394.16', '48516.08', '51086.12', '176979.69', '48359.82', '38507.20', '47707.80', '45640.80', '45691.18', '39096.42', '39102.40', '48984.36', '101147.01', '96127.95', '38416.00', '36247.80', '35989.12', '40142.10']
    bnm965321
        2
    bnm965321  
       2020-08-25 11:36:37 +08:00
    是直接遍历 combinations 生成器么?
    binux
        3
    binux  
       2020-08-25 11:43:26 +08:00
    你的意思是 k-sum ?
    naix1573
        4
    naix1573  
    OP
       2020-08-25 11:52:57 +08:00
    @bnm965321 #2 对 但是这样效率比较低,像=想找个高效的方法。

    @binux #3 恩恩,好像是这个。
    binux
        5
    binux  
       2020-08-25 11:56:47 +08:00
    @naix1573 你不限制下数据范围,那效率可是 n^(k-1) 啊
    JeffGe
        6
    JeffGe  
       2020-08-25 11:57:00 +08:00 via Android
    程序未响应只是你的计算比较花时间,计算过程中单线程的 Python 没法响应图形更新而已,你把计算交给另一个进程就可以了
    renmu123
        7
    renmu123  
       2020-08-25 11:58:34 +08:00 via Android
    笛卡尔积?我记得 Python 的 itertools 标准库有实现,你看一下
    关于   ·   帮助文档   ·   博客   ·   API   ·   FAQ   ·   实用小工具   ·   1343 人在线   最高记录 6679   ·     Select Language
    创意工作者们的社区
    World is powered by solitude
    VERSION: 3.9.8.5 · 23ms · UTC 23:36 · PVG 07:36 · LAX 15:36 · JFK 18:36
    Developed with CodeLauncher
    ♥ Do have faith in what you're doing.