引言
【算法趣题】是来自图灵程序设计丛书绝云译的《程序员的算法趣题》，书中是用Ruby实现的。这里是用python来实现。
问题描述
字母算式，就是用字母表示的算式，其规则是：相同字母对应相同数字，不同字母对应不同数字，并且第一位字母对应的数字不能是0.
例如，给定算式We × love = CodeIQ，如果对应字母与数字的关系如下，就能使该等式成立。
W = 7，e = 4，l = 3，o = 8，v = 0，C = 2，d = 1，I = 9，Q = 6
如此，我们就能得到 74 × 3804 = 281496 这样的等式。
求使下面这个字母算式成立的解法有多少种？
READ + WRITE + TALK = SKILL
思路及python实现
简单穷举法
相同字母对应相同数字，不同字母对应不同数字，只要分配好0-9这几个数字就可以了。
我们先来看看算式有哪几个不同字母，set()是为了去重，转换为list是为了排序，因为set没有顺序。
formula = "READ + WRITE +TALK = SKILL"
set(re.findall('[a-zA-Z]', formula)) # 提取formula中不同的字母
这里刚好10个字母，给每个字母分配一个数字，这个我们在【算法趣题】Q05 还在用现金支付吗？——>店铺红包免费购物里提过，可用itertools.permutations(可迭代对象, 组合元素个数)方法来穷举。假设我举了一组values = (0,1,2,3,4,5,6,7,8,9)，我们将字母和对应的数字组合字典。
然后我们能得到R对应的值为dictionary['R']，因此有
READ = dictionary['R']*1000 + dictionary['E']*100+dictionary['A']*10 + dictionary['D']
考虑到这样相乘好累，也容易多个零什么的，看形式有点像以下两个矩阵的点乘
a = [dictionary['R'], dictionary['E'], dictionary['A'], dictionary['D']]
b =[1000, 100, 10, 1].T
因此，我们可以转换一下
我们可以封装一下这个函数
def getNum(arg, dictionary):
a = [dictionary[x] for x in arg]
b = [10**x for x in range(len(arg))]
b.sort(reverse=True)
return np.dot(np.array(a), np.array(b))
当然在计算数值时要有个前提，那就是第一位字母对应的数字不为0，即要满足
dictionary['R']!=0 and dictionary['W']!=0 and dictionary['T']!=0 and dictionary['S']!=0
最后再来判断等式是否成立即可。
来一个完整的实现代码
import itertools
import time
import re
import numpy as np
def getNum(arg, dictionary): #计算一组字母的值
a = [dictionary[x] for x in arg]
b = [10**x for x in range(len(arg))]
b.sort(reverse=True)
return np.dot(np.array(a), np.array(b))
nums = range(10)
formula = "READ + WRITE + TALK = SKILL"
letters = list(set(re.findall('[a-zA-Z]', formula)))# 提取字母等式中的不同字母
letters.sort()
count = 0
start = time.time()
for comb in itertools.permutations(nums, len(letters)):#枚举
dictionary = dict(zip(letters, comb)) #生成字母对应数字的字典
if(dictionary['R']!=0 and dictionary['W']!=0 and dictionary['T']!=0 and dictionary['S']!=0):# 第一位字母对应数字不为0
read = getNum('READ', dictionary)
write = getNum('WRITE', dictionary)
talk = getNum('TALK', dictionary)
skill = getNum('SKILL', dictionary)
if(read+write+talk == skill):
count = count + 1
print('%s + %s + %s = %s'%(read,write,talk,skill))
print('共有%s种'%count)
end = time.time()
print ('运行时间：%s'%(end-start))
可复用性较强的算法
上述代码只适用于解READ + WRITE + TALK = SKILL这个等式，如果换个字母等式，这个代码就失效了，主要改动的也是这一部分
我们依然以READ + WRITE + TALK = SKILL等式和上节中的dictionary为例，我们先来看下该字母等式中有几组字母。
判断一组字母x中的第一位字母是否为0，只要判断dictionary.get(x[0])是否等于0即可。
因此可以封装一个函数
def if_first_not_zero(dictionary, formula):
if_first = True
for x in re.split(r'[^a-zA-Z]',formula):
if len(x)>0:
if dictionary.get(x[0])==0:
if_first = False
return if_first
然后对于等式，我们只要把字母替换为对应的数字，其他符号不变，最后来判断等式是否成立即可，这时我们又想到了eval这个函数，我们已经在【算法趣题】Q02 数列的四则运算遇到过了。遍历等式的每一个字符，如果该字符在字典中存在（即为字母），则保存该字符对应的值，如果不存在（则为运算符或空格），则保存该字符。然后把这些所有保存的字符组合成新的等式。函数封装如下：
def get_formu(dictionary, formula):
formu_list=[]
for x in formula:
if dictionary.get(x)!=None:
formu_list.append(str(dictionary.get(x)))
else:
formu_list.append(x)
formustr = ''.join(formu_list)
return formustr
最后再来判断等式是否成立即可。
完整实现代码如下
import re
import itertools
import time
def get_formu(dictionary, formula):
formu_list=[]
for x in formula:
if dictionary.get(x)!=None:
formu_list.append(str(dictionary.get(x)))
else:
formu_list.append(x)
formustr = ''.join(formu_list)
return formustr
def if_first_not_zero(dictionary, formula):
if_first = True
for x in re.split(r'[^a-zA-Z]',formula):
if len(x)>0:
if dictionary.get(x[0])==0:
if_first = False
return if_first
def alpha_formula(formula):
nums = range(10)
letter = list(set(re.findall('[a-zA-Z]', formula)))
letter.sort()
count = 0
start = time.time()
for comb in itertools.permutations(nums, len(letter)):
dictionary = dict(zip(letter, comb))
if(if_first_not_zero(dictionary, formula)):
formustr = get_formu(dictionary, formula)
if eval(formustr.replace('=','==')):
count = count + 1
print(formustr)
print('共有%s种'%count)
end = time.time()
print ('运行时间：%s'%(end-start))
只要换一下等式，即可解题了。
虽然我们在【算法趣题】Q09 落单的男女也已经注意到对于数据量比较大的情况下使用itertools模块的方法会比较耗时，按上述的运行时间来看，还算勉强能接受吧。
