今天在微信公众号Python小屋看到Python查找所有类似于123-45-67+89 = 100的组合这篇文章,很感兴趣就手敲了一遍
点开链接就可以看到原文,这里就描述一下问题
在123456789这9个数字中间插入任意多个+和-的组合，使得表达式的值为100，输出所有符合条件的表达式。
第一版-排列组合
对九个数字的八个插入位置进行组合,通过对不同个数插入位,使用排列出计算所有可以出现的运算符
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
|
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
'''
|
注意: 第十一行使用set对permutations的结果进行去重,计算耗时45s左右,不使用去重则时间更长,对于i值越大,返回的结果集越多,当i=8时我的内存已经爆表了,请允许我使用笨方法计算个数
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
|
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则满足条件。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
|
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替换掉,手动生成运算符
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
|
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左右,比第二版本更快,二版本使用手动构建的三进制,这个版本使用内置的二进制转换算法,效率更高