只用传统214部首组字,若不重复不遗漏地使用每个部首,最少可以组成多少字?都是什么?
关注者
22被浏览
6,0054 个回答
先不考虑汉字拆分数据库来源的问题,就假定已经知道了每个汉字包括哪些部首,这个问题也挺难的。
把部首的集合叫做U。首先排除掉所有包含同一个部首超过一个的汉字和拆成部首之后还有非部首的零件的汉字,其余的汉字都可以拆成U的某个子集,这个子集的集合叫做S。如果问题是可否将U拆成k个以上的两两不相交子集,或者是将U拆成两两不相交子集,最多能拆出多少个,那么这是NP-hard的集合背包问题,没有多项式解法。现在问题是把U拆成两两不相交子集,最少能拆出多少个,听起来也会是NP的,没有好的解法,只能 2^{214}\simeq 2.6\times 10^{64} 枚举。
如果能够将U分拆成 U_1,U_2,\dots,U_n 使得对任意 s\in S ,存在 U_i 使得 s\in U_i ,那么枚举量可以降到 \sum_{i=1}^{n} 2^{|U_i|} ,但是总之不是多项式的,而且数据量也大到暴力枚举有点困难