字混亂算法

Question

給出一個字混亂（即ofbaor），這將是對解讀字母來創建一個真正的字（即foobar的）的方法？我可以看到這有幾種方法，我想我知道如何在.NET中做到這一點，但我很好奇看看其他解決方案是什麼樣子的（總是很高興看到我的解決方案是否最優化）。

這不是家庭作業或類似的東西，我只是在紙上的本地漫畫部分看到一個詞混雜（是的，好的新聞紙），我的工程師開始思考。

編輯： 請張貼一些僞代碼或真正的代碼，如果你能;通過查看這樣的例子來嘗試和擴展語言知識總是很好的。

Answer 1

具有的選擇由排序順序每個單詞的字母鍵的字典。然後讓你把這些字母排序混淆 - 用字母排序的字母串查找字典中的所有單詞。

所以，作爲一個例子中，在「熊」和「裸裝」將在字典如下：

key word 
----- ------ 
aber bear 
aber bare 

如果你給出的混亂，「EARB」，你會將字母排序爲'aber'，並能夠在字典中查找兩個可能的單詞。

Answer 2

創建字符串的所有排列，並看看他們在字典中。

您可以通過查找短字符串開頭的單詞優化，以及是否有與這些字符串開始的字典沒有合適長度的話，消除了開始進一步考慮這些字母排列。

Answer 3

CodeProject上有幾篇文章here和here。第二個使用遞歸。維基百科也概述了幾種算法here。維基百科的文章還提到了一個名爲Jumbo的程序，它使用了更像啓發式方法，像人類一樣解決問題。似乎有一些解決問題的方法。

Answer 4

根據字符串的長度WhirlWind的方法可能會更快，但是具有或多或少O（n）複雜度的另一種方法是代替創建字符串的所有排列並查找它們，查看字典中的所有單詞，並查看是否可以從輸入字符串構建每個單詞。

一個真的聰明，知道提前字典中的單詞的數量算法可以做這樣的事情：

sort letters in jumbled string 
if factorial(length of jumbled string) > count of words in dictionary: 
    for each word in dictionary: 
     sort letters in dictionary word 
     if sorted letters in dictionary word == sorted letters in jumbled string: 
      append original dictionary word to acceptable word list 
else: 
    create permutation list of jumbled letters 
    for each permutation of letters: 
     search in dictionary for permutation 
     if permutation in dictionary: 
      add word to acceptable word list 

Answer 5

http://www.codeproject.com/KB/game/Anagrams2.aspx