linq - 另一个排列词难题…与Linq一起吗？

Question

我已经看到了许多获取给定字母集的所有排列的示例。递归似乎可以很好地获得一组字母的所有可能组合（尽管似乎没有考虑其中两个字母相同）。

我想弄清楚的是，您是否可以使用linq（或不使用）将所有可能的字母组合降低到3个字母组合。

例如，给定字母：P I G G Y
我想要这些字母的所有可能词素的数组，以便可以检查一个单词列表（拼字游戏？），并最终获得可以使用这些字母（从3个字母到总计字母）制作的所有可能单词的列表。案例5个字母）。

Answer 1

我建议不要采用（可能需要的长度）所有可能的排列方式，而应采用略有不同的方法，这将减少您必须做的工作总量。

首先，找到一些单词列表（您说要对照单词列表进行检查）。

这是单词列表的好来源：

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

接下来，对于每个单词列表（例如，对于3个字母单词，4个字母单词等），构建字典，该字典的关键字是按字母顺序排列的单词的字母，并且其值是单词。例如，给定以下单词列表：

ACT
CAT
ART
RAT
BAT
TAB

您的字典在概念上看起来像这样（您可能希望制作一个List字典）：

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的每种组合，请检查字典以查看是否有任何带有此键的单词。如果是这样，他们将成为候选人。

因此，对于CAKE，请订购以下字母：

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());
}

基于@Adam Hughes的 answer，这是一个扩展方法，它将返回输入字符串的所有长度（从1到string.Length）的所有组合（n选择k，而不是所有排列）：

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”方法，您可以构建输入单词的列表（拼字词典），并按其“键”为索引建立索引（类似于词典，但许多单词可能具有相同的键）。

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查询该列表，以查找可以从一组给定字母组成的所有单词：

string lettersKey = letters.ToWordKey();

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

您可以找到可以由给定字母集合的任意组合（任意长度）组成的所有单词，如下所示：

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());
}

这段代码可能更好，但是可以完成工作。它不做的一件事是处理重复的字母。如果您有“ egg”，则两个字母的组合将是“ eg”，“ eg”和“ gg”。通过在foreach循环中添加对Distinct的调用，可以很容易地解决该问题：

//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>>）。

使用此代码和一组合适的单词，您应该能够采用字母的任意组合，并找到所有可以由它们组成的单词。您可以
通过查找特定长度的所有单词或任何长度的所有单词来控制单词。

这应该可以帮助您。

[更多说明]

就您最初提出的问题而言，您将“ piggy”作为输入，并希望找到可以由这些字母组成的所有可能单词。使用“ piggy”上的Combinations扩展方法，您将得到一个像这样的列表：

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对象中的“键”字段兼容，我们必须首先对字母排序。

假设我们的拼字游戏托盘上有小猪。要使用我建议的算法，我们希望从PIGGY中获取所有可能的“键”值。在我们的WordEntry对象列表中，我们通过按字母顺序对Word的字母进行排序来创建键字段。我们必须对托盘上的字母进行同样的处理。

因此，PIGGY变为GGIPY。 （这就是ToWordKey所做的）。现在，考虑到托盘中的字母按字母顺序排列，我们可以使用组合来生成所有可能的组合（不渗透）。我们可以基于Key在列表中查找每种组合。如果来自GGIPY的组合与键值匹配，则可以从我们的字母中构造对应的Word（属于WordEntry类）。

比PIGGY更好的例子

SEAT

首先使用ToWordKey：

AETS

现在，制作各种长度的所有组合：

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

当我们查看WordEntry对象列表（通过阅读2、3、4个字母单词的列表制成）时，我们可能会发现找到以下组合：

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'），转换为Key格式（ToWordKey）生成组合（Combinations），仅保留唯一可能的键值（Distict-因为没有重复的字母，所以在这里发出），然后在所有WordEntry对象的列表中查询其Key与组合之一相同的那些WordEntry对象。

本质上，我们要做的是构造一个包含Word和Key列的表（基于读取word的文件并计算每个key的键），然后我们执行一个查询，该查询将Key与生成的Key值序列（从托盘上的字母）。

尝试逐步使用我的代码。

首先，使用组合扩展方法：

var combinations = "piggy".Combinations();

打印结果（pi g g y ... pi pg pg ...猪猪piy ...猪猪piggy iggy ...等）

接下来，在应用ToWordKey扩展方法后获取所有组合：

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

打印结果（例如：igg ig ig ig ip iy igg igp ...

使用Distinct（）方法消除重复项：

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

打印结果（例如，igg ig ip iy igg igp ...等）

使用其他字母集，例如“ ate”和“ seat”。

请注意，与使用置换算法相比，获得的候选者要少得多。

现在，想象一下，我们刚刚制作的组合是将用于在WordEntry对象列表中查找的键值，将每个组合与WordEntry的键进行比较。

使用上面的 GetWords函数以及指向2、3、4个字母词的链接来构建WordEntry对象的列表。更好的是，制作一个精简的单词列表，仅包含几个单词，然后将其打印出来（或在调试器中查看）。看看是什么样子。查看每个单词和每个键。现在，假设您想查找可以用“ AET”创建的所有单词。想象使用所有字母更容易，所以从这里开始。有6个排列，但只有1个组合！没错，您只需要对单词列表进行一次搜索即可找到可以用这些字母组成的所有3个字母单词！如果您有4个字母，将有24个排列，但同样只有1个组合。

这就是算法的本质。 ToWordKey（）函数本质上是一个哈希函数。具有相同数量字母和相同字母集的所有字符串将散列为相同值。因此，构建一个单词及其哈希值的列表（键-ToWordKey），然后给定一组字母以用于制作单词，对这些字母进行哈希处理（ToWordKey），并在列表中找到具有相同哈希值的所有条目。要扩展到查找任何长度的所有单词（给定一组字母），您只需要对输入进行哈希处理（通过ToWordKey发送整个字符串），然后查找任意长度的所有组合。由于组合是从散列的字母集生成的，并且由于组合扩展方法保持了每个组合中字母的原始顺序，因此每个组合都保留了散列的属性！太酷了！

希望这可以帮助。