Python查找类似于123-45-67+89 = 100的组合的性能分析

niaiai 2018-02-28 PM 371℃ 0条

今天在微信公众号Python小屋看到Python查找所有类似于123-45-67+89 = 100的组合这篇文章,很感兴趣就手敲了一遍

点开链接就可以看到原文,这里就描述一下问题

在123456789这9个数字中间插入任意多个+和-的组合,使得表达式的值为100,输出所有符合条件的表达式。

第一版-排列组合

对九个数字的八个插入位置进行组合,通过对不同个数插入位,使用排列出计算所有可以出现的运算符

  • 代码如下
from itertools import combinations, permutations
def getTotal(digits='123456789', total=100):
    # 暴力测试100的组合 使用 permutations组合构建运算符
    for i in range(1, len(digits)):
        for cut in combinations(range(1, len(digits)), i):
            cutindex = 0
            d = []
            for c in cut:
                d.append(digits[cutindex:c])
                cutindex = c
            for op in set(permutations('+-'*i, i)):
                exp = ''.join((ds+o for ds,o in zip(d, op)))+digits[c:]
                if eval(exp)== total:
                    print(exp, '=', total)

'''结果
原始排列组合用set时
123-45-67+89 = 100
123+4-5+67-89 = 100
123+45-67+8-9 = 100
1+2+34-5+67-8+9 = 100
1+23-4+5+6+78-9 = 100
1+23-4+56+7+8+9 = 100
12+3+4+5-6-7+89 = 100
12-3-4+5-6+7+89 = 100
12+3-4+5+67+8+9 = 100
123-4-5-6-7+8-9 = 100
1+2+3-4+5+6+78+9 = 100
Use Time  45.39615345001221
'''

注意: 第十一行使用setpermutations的结果进行去重,计算耗时45s左右,不使用去重则时间更长,对于i值越大,返回的结果集越多,当i=8时我的内存已经爆表了,请也许我使用笨方法计算个数

In [3]: len(list(permutations('+-'*8, 8)))
---------------------------------------------------------------------------
MemoryError                               Traceback (most recent call last)
<ipython-input-2-677f37357fcf> in <module>()
----> 1 len(list(permutations('+-'*8, 8)))

MemoryError:
In [4]: i = 0

In [5]: for j in permutations('+-'*8, 8):
   ...:     i +=1
   ...:

In [6]: i
Out[6]: 518918400

In [7]: len(set(permutations('+-'*8, 8)))
Out[7]: 256

518918400很大,即使用set去重剩下256个结果也需要大量的计算,基本上耗时都在计算这上面

第二版-三进制算法

第一版耗时太长,紧接着作者更新第二版算法采用三进制加法算法,该算法由中国传媒大学胡凤国老师提供,摘录算法思路如下

设计一个三进制加法算法,让8个0逐步变化到8个3,其中每一位上的数字可以是0、1、2,然后让0对应空格、1对应+、2对应-,然后在1到9之间的8个位置上分别插入空格、+或-符号,最后删掉表达式中的空格并求值,如果等于100则满足条件。

  • 代码如下
def triAdd(num):
    # 生成器生成 3**num个运算符 返回格式为['+', '', '', '+', '', '', '', '']
    ops = ('', '+', '-')
    def tri(dec, base=3, result=[ops[0]]*num, dep=0):
        # 十进制转三进制并替换为运算符
        ten, one = divmod(dec, base)
        result[dep] = ops[one]
        if ten == 0:
            return result
        return tri(ten, base, result, dep+1)

    for i in range(1, 3**num):
        # 通过yield返回计算的运算符列表结果
        yield tri(i)

def triToal(digits='123456789', total=100):
    for op in triAdd(len(digits)-1):
        # 循环生成器
        exp = ''.join(d+o for d, o in zip(digits, op))+digits[-1]
        if eval(exp) == total:
            # 计算并将正确的结果打印
            print(exp, '=', total)

'''结果
三进制加法组合
123-45-67+89 = 100
12-3-4+5-6+7+89 = 100
12+3+4+5-6-7+89 = 100
123+4-5+67-89 = 100
1+2+3-4+5+6+78+9 = 100
12+3-4+5+67+8+9 = 100
1+23-4+56+7+8+9 = 100
1+2+34-5+67-8+9 = 100
1+23-4+5+6+78-9 = 100
123+45-67+8-9 = 100
123-4-5-6-7+8-9 = 100
Use Time  0.14190936088562012
'''

计算效率显著提升时间在0.14s左右

第三版-融合以上两个版本

将耗时的permutations替换掉,手动生成运算符

  • 代码如下
def getTotals(digits='123456789', total=100):
    # 暴力测试100的组合 手动构建运算符
    for i in range(1, len(digits)):
        for cut in combinations(range(1, len(digits)), i):
            cutindex = 0
            d = []
            for c in cut:
                d.append(digits[cutindex:c])
                cutindex = c
            for num in range(2**i):
                # 手动构建 00000-11111的+-组合运算符
                op = ('{:0>%sb}'%i).format(num)
                op = op.replace('1', '+').replace('0', '-')
                exp = ''.join((ds+o for ds,o in zip(d, op)))+digits[c:]
                if eval(exp)== total:
                    print(exp, '=', total)

'''结果
半排列组合用时
123-45-67+89 = 100
123+4-5+67-89 = 100
123+45-67+8-9 = 100
1+2+34-5+67-8+9 = 100
1+23-4+5+6+78-9 = 100
1+23-4+56+7+8+9 = 100
12-3-4+5-6+7+89 = 100
12+3+4+5-6-7+89 = 100
12+3-4+5+67+8+9 = 100
123-4-5-6-7+8-9 = 100
1+2+3-4+5+6+78+9 = 100
Use Time  0.11930680274963379
'''

计算时间在0.12s左右,比第二版本更快,二版本使用手动构建的三进制,这个版本使用内置的二进制转换算法,效率更高

标签: Python, 内存, len, range, 生成, digits, exp, total, for

非特殊说明,本博所有文章均为博主原创。

评论啦~