另一個排列詞的難題...與Linq？

Question

我已經看到了很多例子，獲得給定的一組字母的所有排列。遞歸似乎可以很好地得到一組字母的所有可能的組合（儘管它似乎沒有考慮到兩個字母是否相同）。

我想點什麼出來是圖，你可以使用LINQ（或沒有）得到的字母所有可能的組合下到3種字母的組合。

例如，給定字母：PIGGY 我想要一個這些字母的所有可能的聯合數組，所以我可以檢查一個單詞列表（拼字？），並最終得到所有可能的單詞列表，你可以使用這些信件（從3個字母到總數，在這個例子中是5個字母）。

Answer 1

我會建議，而不是生成所有可能的排列（每個需要的長度），以稍微不同的方式，這將減少你必須工作的總體量做。

首先，找一些單詞列表（你說你要覈對單詞列表）。

這裏是字表的一個好來源：

http://www.poslarchive.com/math/scrabble/lists/index.html

接下來，對於每個單詞列表（例如3個字母的單詞，4個字母的單詞，等），構建一個字典，其關鍵是字母這個詞按字母順序排列，其價值就是這個詞。例如，給出下面的單詞列表：

ACT 
CAT 
ART 
RAT 
BAT 
TAB 

你的字典會是這個樣子（概念）（您可能想使列表的字典）：

ABT - BAT, TAB 
ACT - ACT, CAT 
ART - ART, RAT, TAR 

你也許可以把所有在同一本字典中的所有長度的字，它是真的取決於你。

接下來，要爲給定的一組N個字母找到候選單詞，請爲您感興趣的長度生成長度爲K的所有可能組合。對於拼字遊戲，所有組合（順序不重要，因此CAT = = ACT，所以所有排列不是2（7必需的）選擇2），3（7選擇3），4（7選擇4），5（7選5），6（7選6），7個字母（7選擇7）。這可以通過首先按字母順序訂購N個字母和然後找到長度K.

的組合對於長度K的每一個組合來改善，檢查字典來查看是否有與該鍵的任何話。如果是這樣，他們就是候選人。

所以，蛋糕，責令字母：

ACEK 

獲取2，3和4字母組合：

AC 
AE 
AK 
CE 
CK 
EK 
ACE 
CEK 
ACEK 

現在，使用這些密鑰到字典。你會發現ACE和CAKE是候選人。

這種方法可以讓你要遠比產生的所有排列，然後檢查每一個，看它是否是一個字更有效率。使用組合方法，您不必爲相同長度的字母組使用相同的字母進行單獨的查找。

例如，給定：

TEA 

有6個置換（長度3），但是隻有1組合（長度爲3的）。因此，只需要使用AET鍵進行一次查找。

對不起，沒有任何代碼，但有了這些想法，它應該是相對簡單的達到你想要的。

我寫了一個程序，在我第一次學習C＃和.NET時做了很多工作。我會嘗試發佈一些片段（基於我從那時起學到的東西而改進）。

此字符串擴展將返回一個代表按字母順序重新安裝輸入字符串的字符一個新的字符串：

public static string ToWordKey(this string s) 
{ 
    return new string(s.ToCharArray().OrderBy(x => x).ToArray()); 
} 

在此基礎上answer通過@Adam休斯，這裏是一個擴展方法，將返回所有組合（ ñ選擇輸入字符串的K，不是所有的排列）的所有長度（1到string.length）：

public static IEnumerable<string> Combinations(this String characters) 
{ 
    //Return all combinations of 1, 2, 3, etc length 
    for (int i = 1; i <= characters.Length; i++) 
    { 
    foreach (string s in CombinationsImpl(characters, i)) 
    { 
     yield return s; 
    } 
    } 
} 

//Return all combinations (n choose k, not permutations) for a given length 
private static IEnumerable<string> CombinationsImpl(String characters, int length) 
{ 
    for (int i = 0; i < characters.Length; i++) 
    { 
    if (length == 1) 
    { 
     yield return characters.Substring(i,1); 
    } 
    else 
    { 
     foreach (string next in CombinationsImpl(characters.Substring(i + 1, characters.Length - (i + 1)), length - 1)) 
     yield return characters[i] + next; 
    } 
    } 
} 

使用「InAlphabeticOrder」的方法，你可以建立你的輸入字（拼字遊戲字典）名單，ind他們的「鑰匙」（類似於字典，但許多單詞可能具有相同的鑰匙）。

string lettersKey = letters.ToWordKey(); 

var words = from we in wordList where we.Key.Equals(lettersKey) select we.Word; 

你可以找到所有的話，可能是：

public class WordEntry 
{ 
    public string Key { set; get; } 
    public string Word { set; get; } 

    public WordEntry(string w) 
    { 
    Word = w; 
    Key = Word.ToWordKey(); 
    } 
} 

var wordList = ReadWordsFromFileIntoWordEntryClasses(); 

鑑於WordEntry的列表，你可以使用LINQ to發現，可以從一組給定的字母的所有單詞查詢列表

string lettersKey = letters.ToWordKey(); 

var words = from we in wordList 
      from key in lettersKey.Combinations() 
      where we.Key.Equals(key) 
      select we.Word; 

[編輯]

：從（任何長度的）的任何組合的給定集合的字母這樣製成

下面是一些示例代碼：

鑑於從這裏的2,3和4字母單詞的列表：http://www.poslarchive.com/math/scrabble/lists/common-234.html

下面是一些代碼，會讀這些單詞（我剪切和粘貼他們到一個txt文件），並構建WordEntry對象的列表：

private IEnumerable<WordEntry> GetWords() 
{ 
    using (FileStream fs = new FileStream(@".\Words234.txt", FileMode.Open)) 
    using (StreamReader sr = new StreamReader(fs)) 
    { 
    var words = sr.ReadToEnd().Split(new char[] { ' ', '\n' }, StringSplitOptions.RemoveEmptyEntries); 
    var wordLookup = from w in words select new WordEntry(w, w.ToWordKey()); 
    return wordLookup; 
    } 
} 

我已經改名爲InAlphateticalOrder擴展方法ToWordKey。

這裏沒有什麼特別的地方，只要讀取文件，將其拆分爲單詞，然後爲每個單詞創建一個新的WordEntry。通過一次讀取一行可能會更有效率。當你考慮5,6和7個字母的單詞時，這個列表也會變得很長。這可能是一個問題，它可能不是。對於玩具或遊戲來說，這可能沒有什麼大不了的。如果你想變得有趣，你可以考慮用文字和鍵盤構建一個小型數據庫。

給定一組字母，找到具有相同長度的所有可能的單詞作爲鍵：

string key = "cat".ToWordKey(); 
    var candidates = from we in wordEntries 
        where we.Key.Equals(key,StringComparison.OrdinalIgnoreCase) 
        select we.Word; 

給定一組字母，找到從長度爲2的所有可能的字長度（字母）

string letters = "seat"; 

IEnumerable<string> allWords = Enumerable.Empty<string>(); 

//Get each combination so that the combination is in alphabetical order 
foreach (string s in letters.ToWordKey().Combinations()) 
{ 
    //For this combination, find all entries with the same key 
    var words = from we in wordEntries 
       where we.Key.Equals(s.ToWordKey(),StringComparison.OrdinalIgnoreCase) 
       select we.Word; 
    allWords = allWords.Concat(words.ToList()); 
} 

此代碼可能會更好，但它可以完成工作。有一件事情沒有處理重複的信件。如果你有「蛋」，兩個字母組合將是「eg」，「eg」和「gg」。這可以是固定的很輕鬆地通過添加一個調用清晰到foreach循環：

//Get each combination so that the combination is in alphabetical order 
//Don't be fooled by words with duplicate letters... 
foreach (string s in letters.ToWordKey().Combinations().Distinct()) 
{ 
    //For this combination, find all entries with the same key 
    var words = from we in wordEntries 
       where we.Key.Equals(s.ToWordKey(),StringComparison.OrdinalIgnoreCase) 
       select we.Word; 
    //I forced the evaluation here because without ToList I was only capturing the LAST 
    //(longest) combinations of letters. 
    allWords = allWords.Concat(words.ToList()); 
} 

是，最有效的方式做到這一點？也許，也許不是。有人必須做這項工作，爲什麼不用LINQ？

我認爲使用這種方法你可能不需要列表字典（Dictionary<string,List<string>>）。

使用此代碼和一組合適的單詞，您應該可以將任意字母組合並查找可以由它們製作的所有單詞。你可以用 通過查找特定長度的所有單詞或任何長度的所有單詞來控制單詞。

這應該讓你在路上。

[詳細澄清]

在你原來的問題方面，你的輸入是「小豬」，你想找到可以從這些信件作出一切可能的單詞。使用的「小豬」的組合擴展方法，你會想出像這樣的列表：

p 
i 
g 
g 
y 
pi 
pg 
pg 
py 
ig 
ig 
iy 
gg 
gy 
gy 
pig 
pig 
piy 

等需要注意的是有重複。沒關係，我發佈的示例代碼的最後一部分顯示瞭如何通過應用Distinct運算符來找到所有獨特的組合。

因此，我們可以得到給定字母集合中所有字母組合的列表。我的算法取決於基於Key屬性可搜索的WordEntry對象列表。 Key屬性就是重新排列成字母順序的單詞的字母。所以，如果你讀取包含這樣的話一個字的文件：

ACT 
CAT 
DOG 
GOD 
FAST 
PIGGY 

WordEntry對象的名單看起來就像這樣：

Word Key 

ACT ACT 
CAT ACT 
DOG DGO 
GOD DGO 
FAST AFST 
PIGGY GGIPY 

所以，它很容易建立起來的單詞列表和我們要測試的關鍵字（或有效的拼字遊戲字典）。例如，（假設上面的幾個詞組成你的整個詞典），如果你的拼字遊戲盤上有字母'o''g''d'，那麼可以形成單詞DOG和GOD，因爲兩者都有鑰匙DGO。

給定一組字母，如果我們想要從這些字母中找到所有可能的單詞，我們必須能夠生成所有可能的字母組合。我們可以根據「字典」（引號，因爲它不是.NET中意義上的字典，它是WordEntry對象的列表（或序列））來測試每個字典。爲了確保按鍵（從我們在拼字遊戲中「繪製」的字母序列）與WordEntry對象中的鍵字段兼容，我們必須首先排序字母。

說我們在我們的scrabble托盤上有PIGGY。要使用我建議的算法，我們希望從PIGGY獲得所有可能的「關鍵」值。在我們的WordEntry對象列表中，我們通過按字母順序排列Word的字母來創建Key字段。我們必須對托盤上的字母進行同樣的操作。

所以，PIGGY變成GGIPY。 （這就是ToWordKey所做的）。現在，按字母順序給出我們托盤中的字母，我們可以使用組合來生成所有可能的組合（不是permumations）。基於Key，我們可以在列表中查找每個組合。如果來自GGIPY的組合匹配Key值，則可以從我們的字母構造相應的Word（WordEntry類）。

比PIGGY一個更好的例子

SEAT 

首先使用ToWordKey：

AETS 

現在，讓所有長度的所有組合：

A 
E 
T 
S 
AE 
AT 
AS 
ET 
ES 
TS 
AET 
ATS 
ETS 
AETS 

當我們在我們的名單看WordEntry對象（通過閱讀2,3,4個字母的單詞列表），我們可能會發現fo llowing組合發現：

AT 
AS 
AET 
ATS 
ETS 
AETS 

這些關鍵值對應於以下的話：

Key Word 
AT AT 
AS AS 
AET ATE 
AET EAT 
AET TEA 
AST SAT 
EST SET 
AEST EATS 
AEST SEAT 
AEST TEAS 

最後的代碼示例以上將採取字母（ 'S' 'E' 'A' 'T' ），轉換爲密鑰格式（ToWordKey）生成組合（組合），只保留唯一可能的鍵值（Distict - 因爲沒有重複的字母在這裏不是一個問題），然後查詢所有WordEntry對象的列表，密鑰與其中一個組合相同。

本質上，我們所做的是構造一個列表Word和Key（基於閱讀文件的文件和計算每個關鍵），然後我們做一個查詢連接Key與Key值的序列，我們生成（從我們的托盤上的字母）。

嘗試在步驟中使用我的代碼。

首先，使用組合擴展方法：

var combinations = "piggy".Combinations(); 

打印的結果（小豬... PI微克微克...豬豬PIY ...皮格pigy伊基...等）

// 
// "piggy".ToWordKey() yields "iggpy" 
// 
var combinations = "piggy".ToWordKey().Combinations(); 

打印結果（iggpy IG IG IP IY IgG抗體IgY的IGP ...等）

：

接下來，應用ToWordKey擴展方法後得到的所有組合個

消除重複與DISTINCT（）方法：

var combinations = "piggy".ToWordKey().Combinations().Distinct(); 

打印的結果（I G P Y [IG IP IY的IgG IGP的IgY ...等）

使用其他字母，如「吃」和「座位」。

請注意，與使用置換算法相比，您獲得的候選人數要少得多。

現在，假設我們剛纔所做的組合是我們用來查看WordEntry對象列表的關鍵值，並將每個組合與WordEntry的關鍵字進行比較。

使用上面的GetWords函數和鏈接到2,3,4個字母的單詞來構建WordEntry對象的列表。更好的辦法是，用一些簡單的單詞製作一個非常簡潔的單詞列表並打印出來（或者在調試器中查看它）。看看它的樣子。看看每個單詞和每個鍵。現在，想象一下，如果你想找到所有可以用「AET」製作的單詞。使用所有字母比較容易，所以從這裏開始。有6種排列，但只有1種組合！沒錯，你只需要搜索單詞列表就可以找到可以用這些字母做出的所有3個字母的單詞！如果您有4個字母，則會有24個排列組合，但同樣只有1個組合。

這就是算法的本質。 ToWordKey（）函數本質上是一個哈希函數。所有具有相同字母數量和相同字母集合的字符串將哈希到相同的值。因此，建立一個單詞列表及其散列（Key - ToWordKey），然後給定一組字母用於生成單詞，對這些單詞進行散列（ToWordKey），並使用相同的散列值查找列表中的所有條目。要擴展到查找任何長度的所有單詞（給定一組字母），您只需對輸入進行散列（通過ToWordKey發送整個字符串），然後查找任意長度的所有組合。由於這些組合是由一組散列字母生成的，並且由於組合擴展方法保持了每個組合中字母的原始排序，所以每個組合都保留了散列的屬性！這很酷！

希望這會有所幫助。

Answer 2

我覺得這個已經回答了 How to write an anagram generator in pure C# and .Net framework

Answer 3

此方法似乎工作。它使用Linq和程序代碼。

IEnumerable<string> GetWords(string letters, int minLength, int maxLength) 
{ 
    if (maxLength > letters.Length) 
     maxLength = letters.Length; 

    // Associate an id with each letter to handle duplicate letters 
    var uniqueLetters = letters.Select((c, i) => new { Letter = c, Index = i }); 

    // Init with 1 zero-length word 
    var words = new [] { uniqueLetters.Take(0) }; 

    for (int i = 1; i <= maxLength; i++) 
    { 
     // Append one unused letter to each "word" already generated 
     words = (from w in words 
       from lt in uniqueLetters 
       where !w.Contains(lt) 
       select w.Concat(new[] { lt })).ToArray(); 

     if (i >= minLength) 
     { 
      foreach (var word in words) 
      { 
       // Rebuild the actual string from the sequence of unique letters 
       yield return String.Join(
        string.Empty, 
        word.Select(lt => lt.Letter)); 
      } 
     } 
    } 
} 

Answer 4

搜索單詞所有排列的問題是計算絕對亂碼所花費的工作量。生成所有的排列是O（n！），所以絕大部分將被浪費。這就是爲什麼我推薦wageoghe的回答。

這裏是一個遞歸LINQ函數，返回所有排列：

public static IEnumerable<string> AllPermutations(this IEnumerable<char> s) { 
     return s.SelectMany(x => { 
      var index = Array.IndexOf(s.ToArray(),x); 
      return s.Where((y,i) => i != index).AllPermutations() 
        .Select(y => new string(new [] {x}.Concat(y).ToArray())) 
        .Union(new [] {new string(new [] {x})}); 
     }).Distinct(); 
    } 

你可以找到你想要像這樣的話：

"piggy".AllPermutations().Where(x => x.Length > 2) 

但是：

警告：我am 不是喜歡這個很效率低下的答案

現在linq對我來說最大的好處是它的可讀性如何。話雖如此，但是，我不認爲上述代碼的意圖是明確的（我寫了！）。因此，linq（對我而言）的最大優勢不在上面，和它不像非linq解決方案那樣高效。我通常原諒linq缺乏執行效率，因爲它爲編碼時間，可讀性和易維護性增加了效率，但我不認爲linq解決方案在這裏是最合適的......方形掛鉤，圓孔排序如果你願意的話。

另外，還有上述複雜性的問題。當然，它可以在0.2秒內找到153個「小豬」的三個字母或更多的排列，但給它一個像'簿記'的字，你會等待一個堅實的1分39秒因爲它找到所有435,574三個字母或更多排列。那麼爲什麼我發佈這樣一個可怕的功能？爲了說明這個觀點是正確的。生成所有排列對於解決這個問題並不足夠有效。