Re: [討論] 檢查任意的字母組合能拼成哪些字
※ 引述《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)
推
04/23 20:19, , 1F
04/23 20:19, 1F
討論串 (同標題文章)
本文引述了以下文章的的內容：
完整討論串 (本文為第 2 之 2 篇)：