[python应用分享] 字母自动合成单词

jerryxjr1220

周末去电影院看了新上映的《但丁密码》，是《达芬奇密码》、《天使与恶魔》的姐妹篇，汤姆汉克斯的解谜系列电影三部曲。

其中有一个桥段就是兰登教授通过《地狱图》获得了一组字母，这组字母一定传达了某种意思，那么问题来了，如何排列出合理的单词呢？

当然，电影中没有使用高科技手段，而是女主角很快地想出来答案。

那么我就想，能否用python来实现呢？理论上应该是完全可行的。

上图：


另外，我针对于长单词又另外设计了一套计算方法，不用排列组合，这样可以大大加快搜索速度。

1. yap ==> ['yap', 'pay']
   
2. [Finished in 0.5s]
   
3. please ==> ['please', 'elapse', 'asleep']
   
4. [Finished in 0.6s]
   
5. amenretge ==> ['agreement']
   
6. [Finished in 2.4s]
   
7. sourolenti ==> ['resolution']
   
8. [Finished in 5.0s]
   
9. arecioipnatp ==> ['appreciation']
   
10. [Finished in 0.9s]
    
11. cprarohiyelhocalg ==> ['choreographically']
    
12. [Finished in 0.7s]

复制代码

代码如下：

游客，如果您要查看本帖隐藏内容请回复

jerryxjr1220

我想到，可以用动态规划算法进行优化。
明天有空码下代码

等单个词优化完成，剩下就可以考虑2个及2个以上单词的组合了，这个就有点难度了。
初步考虑可以从单词的构成下手，按元音和辅音归类，具体算法还没想好，欢迎提供思路。

leo8080

风吹雨起#泪花落

看看代码

jerryxjr1220

我针对于长度长的单词重新设计了一种算法（当然不是用排列组合，不然肯定算不出），这样哪怕长度最长的单词30秒内应该也能计算出来。但是排列组合针对于短单词也是有优势的。所以2种方法并用，当单词长度小于8位就用短单词搜索，当超过8位，就切换为长单词搜索。这样基本上就可以解决单个单词的搜索问题了。
贴几个运算结果：

1. yap ==> ['yap', 'pay']
   
2. [Finished in 0.5s]
   
3. please ==> ['please', 'elapse', 'asleep']
   
4. [Finished in 0.6s]
   
5. amenretge ==> ['agreement']
   
6. [Finished in 2.4s]
   
7. sourolenti ==> ['resolution']
   
8. [Finished in 5.0s]
   
9. arecioipnatp ==> ['appreciation']
   
10. [Finished in 0.9s]
    
11. cprarohiyelhocalg ==> ['choreographically']
    
12. [Finished in 0.7s]

复制代码

冬雪雪冬

第6行有误。

1. >>> a='sdfg\n'
   
2. >>> a[:-2]
   
3. 'sdf'
   
4. >>> a[:-1]
   
5. 'sdfg'

复制代码

建议改为 i.strip('\n')

jerryxjr1220

冬雪雪冬 发表于 2016-11-2 12:52
第6行有误。

谢谢提醒，非常好的意见，我是偷懒了

冬雪雪冬

我尝试了另一种方法。

1. with open('lemmas.txt') as f:
   
2.     dic = [i.strip('\n') for i in f]
   
3. dics ={}
   
4. for each in dic:
   
5.         if len(each) not in dics:
   
6.                 dics[len(each)] = [each]
   
7.         else:
   
8.                 dics[len(each)].append(each)
   
9. 
   
10. def words(letters):
    
11.         word = []
    
12.         for potword in dics[len(letters)]:
    
13.                 if sorted(letters) == sorted(potword):
    
14.                         word.append(potword)
    
15.         return word
    
16. 
    
17. print ("'cprarohiyelhocalg' ==>", words('cprarohiyelhocalg'))

复制代码

jerryxjr1220

冬雪雪冬 发表于 2016-11-2 17:19
我尝试了另一种方法。

不错，和我优化后的思路很接近，运算时间也很接近。
不过我写得比较复杂，还是你的代码比较简洁

阿长

厉害了

冬雪雪冬

我又考虑了优化的方法：
1.建立字典，格式为｛排序的字符: [可能的单词]，如 ｛..., 'aeelps'：['please', 'elapse', 'asleep'], ...｝，当然可以根据字符的长度做出若干个字典，合并为一个包含字典的大列表。然后用字典的get方法查找，get(''.join( sorted(letters))
2.不用字典，建立列表[...,[ 'aeelps', ['please', 'elapse', 'asleep']], ...]，由于是有序的，可以采用折半查找。

jerryxjr1220

冬雪雪冬 发表于 2016-11-3 14:33
我又考虑了优化的方法：
1.建立字典，格式为｛排序的字符: [可能的单词]，如 ｛..., 'aeelps'：['please', ...

这些方法都是属于用空间换时间的方法，和我之前考虑的优化方法差不多，不过我还是觉得你昨天的优化比较好，代码简洁，速度也不慢啊。

冬雪雪冬

期待你多个单词组合的算法，除了用排列组合我还一点头绪也没有。

jerryxjr1220

冬雪雪冬 发表于 2016-11-3 14:39
期待你多个单词组合的算法，除了用排列组合我还一点头绪也没有。

多个单词的组合，我目前只尝试了2个单词，按照元音和辅音划分，也是排列组合，先取一组，然后剩下的变成另一组。但是词组的组合太多了，没有好的优化算法，执行起来好慢的。

现在考虑的方向是找一个词组的字典，然后还是安排单个词的方式搜索，这样的效率还高一点。
而且如果找到的2个词完全对不上的话，找到的意义也不大。

所以从词组着手，可能性更高。

xinshouxuexi

学习了！

domenet

看看算法

余欲渔

怎么做到的

rzzsss

wrrwrr111

谢谢分享

zhansc

思路可以的