[python应用分享] 字母自动合成单词
本帖最后由 jerryxjr1220 于 2016-11-2 12:57 编辑周末去电影院看了新上映的《但丁密码》，是《达芬奇密码》、《天使与恶魔》的姐妹篇，汤姆汉克斯的解谜系列电影三部曲。
其中有一个桥段就是兰登教授通过《地狱图》获得了一组字母，这组字母一定传达了某种意思，那么问题来了，如何排列出合理的单词呢？
当然，电影中没有使用高科技手段，而是女主角很快地想出来答案。
那么我就想，能否用python来实现呢？理论上应该是完全可行的。
上图：
另外，我针对于长单词又另外设计了一套计算方法，不用排列组合，这样可以大大加快搜索速度。
yap ==> ['yap', 'pay']
please ==> ['please', 'elapse', 'asleep']
amenretge ==> ['agreement']
sourolenti ==> ['resolution']
arecioipnatp ==> ['appreciation']
cprarohiyelhocalg ==> ['choreographically']
代码如下：
**** Hidden Message ***** 本帖最后由 jerryxjr1220 于 2016-11-1 22:40 编辑
我想到，可以用动态规划算法进行优化。
明天有空码下代码{:5_92:}
等单个词优化完成，剩下就可以考虑2个及2个以上单词的组合了，这个就有点难度了。
初步考虑可以从单词的构成下手，按元音和辅音归类，具体算法还没想好，欢迎提供思路。{:5_92:} {:9_230:}{:9_230:}{:9_230:}{:9_230:}{:9_230:}{:9_230:} 看看代码 我针对于长度长的单词重新设计了一种算法（当然不是用排列组合，不然肯定算不出），这样哪怕长度最长的单词30秒内应该也能计算出来。但是排列组合针对于短单词也是有优势的。所以2种方法并用，当单词长度小于8位就用短单词搜索，当超过8位，就切换为长单词搜索。这样基本上就可以解决单个单词的搜索问题了。
贴几个运算结果：
yap ==> ['yap', 'pay']
please ==> ['please', 'elapse', 'asleep']
amenretge ==> ['agreement']
sourolenti ==> ['resolution']
arecioipnatp ==> ['appreciation']
cprarohiyelhocalg ==> ['choreographically']
第6行有误。
>>> a='sdfg\n'
>>> a[:-2]
'sdf'
>>> a[:-1]
'sdfg'
建议改为 i.strip('\n') 冬雪雪冬 发表于 2016-11-2 12:52
第6行有误。
谢谢提醒，非常好的意见，我是偷懒了{:5_96:} 我尝试了另一种方法。
with open('lemmas.txt') as f:
dic =
dics ={}
for each in dic:
if len(each) not in dics:
dics =
else:
dics.append(each)
def words(letters):
word = []
for potword in dics:
if sorted(letters) == sorted(potword):
word.append(potword)
return word
print ("'cprarohiyelhocalg' ==>", words('cprarohiyelhocalg')) 冬雪雪冬 发表于 2016-11-2 17:19
我尝试了另一种方法。
不错，和我优化后的思路很接近，运算时间也很接近。
不过我写得比较复杂，还是你的代码比较简洁{:5_106:} 厉害了{:5_108:} 我又考虑了优化的方法：
1.建立字典，格式为｛排序的字符: [可能的单词]，如 ｛..., 'aeelps'：['please', 'elapse', 'asleep'], ...｝，当然可以根据字符的长度做出若干个字典，合并为一个包含字典的大列表。然后用字典的get方法查找，get(''.join( sorted(letters))
2.不用字典，建立列表[...,[ 'aeelps', ['please', 'elapse', 'asleep']], ...]，由于是有序的，可以采用折半查找。 冬雪雪冬 发表于 2016-11-3 14:33
我又考虑了优化的方法：
1.建立字典，格式为｛排序的字符: [可能的单词]，如 ｛..., 'aeelps'：['please', ...
这些方法都是属于用空间换时间的方法，和我之前考虑的优化方法差不多，不过我还是觉得你昨天的优化比较好，代码简洁，速度也不慢啊。 期待你多个单词组合的算法，除了用排列组合我还一点头绪也没有。 冬雪雪冬 发表于 2016-11-3 14:39
期待你多个单词组合的算法，除了用排列组合我还一点头绪也没有。
多个单词的组合，我目前只尝试了2个单词，按照元音和辅音划分，也是排列组合，先取一组，然后剩下的变成另一组。但是词组的组合太多了，没有好的优化算法，执行起来好慢的。
现在考虑的方向是找一个词组的字典，然后还是安排单个词的方式搜索，这样的效率还高一点。
而且如果找到的2个词完全对不上的话，找到的意义也不大。
所以从词组着手，可能性更高。 学习了！ 看看算法
怎么做到的 {:5_92:}{:5_109:} 谢谢分享 思路可以的
页:
[1]