如何找到遊戲的可行字母組合？

我試圖通過克隆一個流行的Android遊戲來練習自己iOS，但是有一部分遊戲我無法弄清楚如何在語言無關的意義上解決問題。如何找到遊戲的可行字母組合？

遊戲非常簡單：玩家有6個字母，其中不同的子集可以形成30個不同的3個字母，4個字母和5個字母的單詞。玩家必須在兩分鐘內儘可能多地找到這些可能的單詞。遊戲擁有4000種不同的6字母組合，具有極佳的重播能力。我不知道作者如何得到4000種不同的組合。

我的意思是，我可以找到4000個獨特的6個字母的組合，但我怎麼能找到那些有大約30個可行子組合？如果可以從這些字母中得到的可行單詞太少，或者太多，那麼它就行不通，而且這個空間太大，不能用暴力來通過它，我認爲，因爲這將涉及1.65億針對數千字詞典的組合。

我只是需要一些建議，我知道必須有一個聰明的方法來做到這一點，它還沒有到我這裏來。

2014-11-04 Aerovistae

提示：從字典/單詞列表開始，然後消除列表中不能使用完全6個給定字母的單詞。

（或什麼的。你的問題的解釋是有點不清楚。）

在最壞的情況，你必須檢查在列表中的單詞數（很多小於1.65億）。還有其他各種可以用來加速搜索的技巧。

2014-11-04 22:13:29

你試過隨機取樣6個字母嗎？你可以繼續嘗試設置6個字母，直到找到一個有很多可能單詞的單詞，然後重複4000次。測試每一個不應該花太長時間，因爲只有2^6 = 64子集，您可以索引單詞詞典以快速檢查這些子集。您還可以調整不同字母的概率，以便找到具有更高概率的好集合。

這種類型的問題經常適用的稍微複雜的方法是馬爾科夫鏈蒙特卡羅（http://en.wikipedia.org/wiki/Markov_chain_Monte_Carlo）。您可以嘗試每次替換幾個字母，從而賦予與可能單詞的目標數量接近的6個集合更高的權重。

2014-11-04 22:14:32 arghbleargh

我不明白你是怎麼想出64個子集的。很確定這是一個不準確的數字。 ABC可以安排6種方式，而不是2^3。 – Aerovistae 2014-11-12 07:25:47

你只需要根據字母集來跟蹤事物。例如，您可以根據字母順序排列每個單詞（請參閱其他答案）。所以EAT，ATE和TEA都被編入索引，因爲任何6個拼寫EAT的字母都可以拼寫ATE和TEA。 – arghbleargh 2014-11-13 09:37:55

一種方法。

獲取6個字母及更小的單詞列表。我不知道會有多少人。大概在100,000的數量級。但即使是兩倍也沒什麼大不了的。

現在，對每個單詞中的字母進行排序。所以「雪松」變成了「愛德」。這些成爲詞典中的鍵，詞典中的值是映射到這些字母的單詞實際。因此，「acders」的條目將包括「雪松」和「害怕」以及由這些字母組成的任何其他六個字母的單詞（如果有的話）。

現在從列表中隨機選擇三個雙字母單詞。這給了你6個字母的組合。

從那裏，你可以創建你的排列。你有這樣的潛力：

6 one-letter words 
15 two-letter words 
20 three-letter words 
15 four-letter words 
6 five-letter words 
1 six-letter words

所以你必須做63個字典查找，以確定你有多少好詞。

英語中有114 two-letter words，這意味着有240,464個三個雙字母單詞的可能組合。所以你最終不得不做1500萬詞典查找的順序。這應該需要幾秒鐘的時間。

2014-11-04 22:30:45

我想知道你從哪裏得到了6-15-20-15-6-1的單詞數量。舉例來說，爲什麼六個字母只能有六個字母？ '害怕' - >'雪松'OOOOOOHhhhh我想我明白你的意思。繼續思考。聰明的做法。 – Aerovistae 2014-11-04 22:35:28

@Aerovistae：我忘了一步。查看我的更新。另外，我意識到我不需要多個哈希映射。 – 2014-11-05 04:35:28

回答