一个简单的穷举

[supersheep]

最近疯狂猜图很火，于是想有没有办法通过穷举自动识别出可能的组合。写的时候发现算法什么的都还给老师了，比如有n个可选字，组成一个m位数的词，当中不能有重复，感觉有点像n皇后问题，反正倒腾了半天没搞定，弱爆了。今天早上想到拿进制来做，其实道理一样的，不过代码会变得简单清晰很多，简单讲就是把递增的i转成一个m位的n进制数。

大致就是这样：

http://gist.github.com/supersheep/5893777.js

现在觉得数量还是太大了，无从判断，拿来发douban api一下子access rate limit就爆掉了，所以有必要有个本地词库拿来扫一下，可以组成词组的字占一半以上才列入考虑。有兴趣的同学可以继续尝试一下看看咯。

[csx163]

感觉还是要词库，里面大部分都是能连接的字符

[Golevka]

把字典组织成trie的形式, 把待匹配的字符集中取出一个元素作为首字母然后用类似递归下降的方式匹配剩余的部分. 目测剪枝能力还是可以的, 至少比穷举要好得多

[Ricepig]

字根表就行了

[supersheep]

@Golevka 嗯，多谢，回头试试看。
@Ricepig 字根表是什么意思？google搜到的都是五笔相关的内容。和Golevka是一个意思么？

[Ricepig]

@supersheep 额，不好意思我词不达意了，我当时的意思是词根。英文里用的比较多，比如说什么前缀，什么后缀大概能表达一个什么意思。这样不用多大的库，剪枝效果就很好了。

字典当然更好，不过对字典的要求比较高，另外就是高质量的字典可能本身也不小了。