另一个排列词难题......使用 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 的每个组合，请检查字典以查看是否有具有此键的单词。如果是这样，他们就是比赛的候选人。

因此，对于 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 的回答，这是一个扩展方法，它将返回所有长度（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 到 length(letters) 的所有可能的单词

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

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

这应该能让你上路。

[更多说明]

就您原来的问题而言，您将“piggy”作为输入，并且您希望找到可以由这些字母组成的所有可能的单词。使用“piggy”上的组合扩展方法，您将得到一个如下所示的列表：

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

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

于是，PIGGY就变成了GGIPY。 （这就是 ToWordKey 的作用）。现在，给定托盘中按字母顺序排列的字母，我们可以使用组合来生成所有可能的组合（而不是排列）。我们可以根据键在列表中查找每个组合。如果 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 个字母单词列表组成）时，我们可能会发现找到以下组合：

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）生成组合（Combinations ），仅保留唯一的可能键值（Distict - 此处不是问题，因为没有重复的字母），然后查询所有 WordEntry 对象的列表，以查找其 Key 与组合之一相同的 WordEntry 对象。

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

尝试逐步使用我的代码。

首先，使用 Combinations 扩展方法：

var combinations = "piggy".Combinations();

打印结果（piggy ... pi pg pg ... pig pig piy ... pigg pigy iggy ... 等）

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

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

打印结果 (iggpy ig ig ip iy igg igp igy ... 等)

使用 Distinct() 方法消除重复项：

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

打印结果 (igpy ig ip iy igg igp igy ... 等)

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

请注意，与使用排列算法相比，您得到的候选数要少得多。

现在，假设我们刚刚创建的组合是键值，我们将使用它们在 WordEntry 对象列表中查找，并将每个组合与 WordEntry 的键进行比较。

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

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

希望这有帮助。

Answer 2

这个方法似乎有效。它同时使用 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 3

搜索一个单词的所有排列的问题是计算绝对乱码所花费的工作量。生成所有排列的时间复杂度为 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)

但是：

警告：我不喜欢这个非常< /strong> 低效的答案

现在 linq 最大的好处（对我来说）是它的可读性。然而，话虽如此，我认为上述代码的意图并不明确（而且是我写的！）。因此，linq（对我而言）的最大优势并未在上面体现，并且它不如非 linq 解决方案高效。我通常会原谅 linq 缺乏执行效率，因为它提高了编码时间、可读性和易于维护的效率，但我只是不认为 linq 解决方案最适合这里......方钉、圆孔排序如果你愿意的话。

另外，还有我上面提到的复杂性问题。当然，它可以在 0.2 秒内找到“piggy”的 153 个三个字母或更多排列，但给它一个像“bookkeeper”这样的单词，你将等待一个坚实的1 分 39 秒找到所有 435,574 个三个字母或更多字母的排列。那么我为什么要发布这么糟糕的功能呢？为了表明 Waoghe 的做法是正确的。生成所有排列并不是解决此问题的足够有效的方法。