另一个排列词难题......与Linq？

Question

我已经看到了许多获得给定字母集的所有排列的例子.递归似乎可以很好地得到一组字母的所有可能组合(尽管它似乎没有考虑其中2个字母是否相同).

我想弄清楚的是,您是否可以使用linq(或不使用)来获得所有可能的字母组合,最多可达3个字母组合.

例如,给定字母:PIGGY我想要这些字母的所有可能组合的数组,以便我可以检查单词列表(拼字游戏？)并最终获得您可以使用这些字母制作的所有可能单词的列表(来自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的这个答案,这里有一个扩展方法,它将返回输入字符串的所有长度(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());
}

这段代码可能会更好,但它可以完成工作.它没有做的一件事是处理重复的字母.如果你有"鸡蛋",两个字母组合将是"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"上的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对象中的Key字段兼容,我们必须首先对字母进行排序.

假设我们的拼字游戏托盘上有PIGGY.要使用我建议的算法,我们希望从PIGGY获得所有可能的"Key"值.在我们的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个字母单词列表中阅读而制作)时,我们可能会发现找到以下组合:

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)生成组合(组合),只保留唯一可能的键值(Distict - not an此处发出问题,因为没有重复的字母),然后查询所有WordEntry对象的列表,查找其Key与其中一个组合相同的WordEntry对象.

基本上,我们所做的是构建一个包含Word和Key列的表(基于读取单词文件并计算每个单词的Key)然后我们进行查询,将Key与我们生成的Key值序列(来自托盘上的字母).

尝试逐步使用我的代码.

首先,使用组合扩展方法:

var combinations = "piggy".Combinations();

打印结果(小猪... pi pg pg ...猪猪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"和"seat".

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

现在,假设我们刚刚创建的组合是我们将在WordEntry对象列表中查看的关键值,将每个组合与WordEntry的Key进行比较.

使用GetWords上面的函数和2,3,4字母单词的链接来构建WordEntry对象列表.更好的是,用一个单词创建一个非常简单的单词列表并将其打印出来(或在调试器中查看).看看它的样子.查看每个Word和每个Key.现在,想象一下,如果你想找到你可以使用"AET"制作的所有单词.使用所有字母更容易想象,所以从那里开始.有6个排列,但只有1个组合!没错,你只需要搜索单词列表就可以找到所有可以用这些字母制作的3个字母单词!如果您有4个字母,则会有24个排列,但同样只有1个组合.

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

希望这可以帮助.