import time
op = ['+', '-', '&'] # 操作符 &表示两个数合并
vis = [0 for i in range(20)] # vis表示是否访问过
# range(输入的数值的最多位数)
"""
dfs搜索出所有排列结果保存到slist
:param
a list 表示输入的数组
w int 计数，递归级数
slist list 保存输出结果
link list 保存路径，二维数组，因为存的是路径所有对于每次递归只取link[n-1]
"""
def wayback(a: list, w: int, evdic: dict,link: any):
if w == len(a):
s = ''
for n in link:
if len(n) == 0:
break
s = s + str(n[len(n) - 1][0]) + n[len(n) - 1][1] # 取每个路径最后一组结果
s = s + str(a[w - 1]) # 默认只做到len-2 这里需要加上最后一个数字
s = s.replace('0&', '').replace('&', '')
evdic.setdefault(eval(s), [])
evdic[eval(s)].append(s) # 添加表达式到结果列表
return
for i in range(w):
if vis[i] == 0:
for j in op:
vis[i] = 1 # 标记
link[i].append([a[i], j])
#dic.setdefault(a[i], [])
#dic[a[i]].append(j)
wayback(a, w + 1, evdic, link) # 递归
vis[i] = 0 # 恢复
"""
处理输入，调用递归函数得到结果数组，筛选符合的表达式，输出
"""
def compute(a, b):
# 输入的两个字符串的数值拆分成整型数组
a = ','.join(a).split(',')
b = ','.join(b).split(',')
aDict, bDict = {}, {}
# 调用递归函数并保存结果
wayback(a, 1, aDict, [[] for i in range(20)])
wayback(b, 1, bDict, [[] for i in range(20)])
# print(aSet)
#aSet=set(aDict.keys())
#bSet=set(bDict.keys())
#aSet = aSet & bSet
# print(aSet)
for key in aDict.keys()&bDict.keys():
print(aDict[key], "=", bDict[key], "=", key)
a = input('input A:')
b = input('input B:')
start = time.time()
compute(a, b)
end = time.time()
print('计时:', end-start)
"""测试
12345
6789
"""
"""dfs
123
1 2 3
1 1+2
1+2+3
1+2-3
1+2&3
1-2
1-2+3
1-2-3
1-2&3
1&2
...
"""
