※ 引述《mander (阿平)》之铭言： : 各位好，第一次发文 : 这个问题有一些基本的想法提出来与大家讨论效果的优劣 : 我想要输入一组任意的字母组合(想是 C L E A R E H ) : 字母组合中不考虑顺序、大小写，字母可能出现多次(E出现两次) : 程式检查有哪些单字能用上面列出的字母组合拼出来 : 例如以上的组合可能会跑出如clear,hear,reel,real,heal,rec...的列表 : 现在已经产生一个字典档dic.txt了 : 请问各位会怎麽考虑写这个查询的程式呢? : 现把小弟粗略的想法提出来 : 想法挺简单的，就先建一个可供查询的索引，再查是否单字在其中 : A.建索引 : 1.字典档中每个单字都建编号 : 2.对每个字母(a-z)，建一个参照表 : 检查单字中出现了哪些字母，在参照表中加入有出现单字的整数编号W(k) : B.查询 : 1.查询的时候把输入字串中包含哪些字母，将字母参照表中的W(k) : 放到一个array A或hash H中， : 是在hash中的话key-valur pair的key是W(k)，value则每符合一个字母就加一 : 2.对hash H依照value排序(这里会有问题value值可能不唯一) : 然後照value值大小输出W(k) : 3.印出W(k)对应的单字 : 以上想法实在始有够简单，感觉在查询的时候效率会很差 : hash H在遇到字母AEIOU这种的时候会变大很多 : 边写的时候发现以上其实就是invertd file & boolean search的做法 XD : 只是是字母版的 : 希望能够抛砖引玉，有更好的想法一起讨论 这个问题与 programming pearls 书中所提到的问题十分类似 但原本的问题要求所有字母都用上，跟你这个问题有一点不同 不过解法其实很像，先大概讲一下作法 整个解法的关键就是对字典档的每一个单字做排序跟去除重复的字母 比方 apple -> aelp, banana -> abn 当然 aelp 可以组成的单字可能不只 apple, 因此之後遇到同样是由 aelp 所组成的单 字就直接接在 apple 的後面就好 接下来假设想寻找 aelp 究竟可组成什麽样的单字时，只要把 aelp 的清单印出来就行 不过由於你的要求还另外包含了 aelp 的其他组合，如 ael, aep, alp, elp 之类的 因此你还另外需要列举出对aelp做 C(4, 3), C(4, 2), C(4, 1) 的组合进行查询的结果 算是原问题的变形 --　 这类问题其实到 programming 版问可能比较适当？ -- IF THEN THEN THEN = ELSE; ELSE ELSE = THEN; --

※ 发信站: 批踢踢实业坊(ptt.cc) ◆ From: 59.112.85.222 ※ 编辑: klaymen 来自: 59.112.85.222 (04/13 12:00)