另一个排列词难题...与Linq？
我已经看到了很多例子来获得一组给定字母的所有排列组合。 递归似乎可以很好地得到一组字母的所有可能的组合（尽管它似乎没有考虑到两个字母是否相同）。
我想知道的是，你可以使用linq（或不）来获得所有可能的字母组合，最多可以组合3个字母。
例如，给定字母：PIGGY我想要一个包含这些字母的所有可能的字符串的数组，因此我可以检查字列表（拼字？），并最终得到所有可能使用这些字母的单词列表（从3信件总数，在这种情况下是5个字母）。
我建议不要产生所有可能的排列（每个所需的长度），采取稍微不同的方法，这会减少你必须完成的总体工作量。
首先，找到一些单词列表（你说你要检查单词列表）。
这是一个很好的单词列表来源：
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”。 通过添加一个调用Distinct到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 of List（ Dictionary<string,List<string>> ）。
使用此代码和一组适当的单词，您应该能够将任意字母组合并查找可以由它们制作的所有单词。 您可以通过查找特定长度的所有单词或任何长度的所有单词来控制单词。
这应该让你在路上。
[更多说明]
根据您的原始问题，您将“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对象中的键字段兼容，我们必须首先排序字母。
假设我们的拼字游戏盘上有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个字母的单词列表）时，我们可能会发现找到了以下组合：
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 - 不是因为没有重复的字母），然后查询所有WordEntry对象的列表，这些对象的键与其中一个组合相同。
从本质上讲，我们所做的是构造了一个包含Word和Key列的表格（基于读取文件并为每个Key计算Key），然后我们执行一个查询，将Key与我们生成的一系列Key值进行连接我们托盘上的字母）。
尝试在步骤中使用我的代码。
首先，使用组合扩展方法：
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 ...等）
使用其他字母，如“吃”和“座位”。
请注意，与使用置换算法相比，候选人数量明显减少。
现在，设想我们刚才所做的组合是我们用来查看WordEntry对象列表的关键值，并将每个组合与WordEntry的关键字进行比较。
使用上面的GetWords函数和链接到2，3，4个字母的单词来构建WordEntry对象的列表。 更好的办法是，用一些简单的单词制作一个非常简洁的单词列表并打印出来（或者在调试器中查看它）。 看看它的样子。 看看每个单词和每个键。 现在，想象一下，如果你想找到所有可以用“AET”制作的单词。 使用所有字母比较容易，所以从这里开始。 有6种排列，但只有1种组合！ 没错，你只需要搜索单词列表就可以找到可以用这些字母做出的所有3个字母的单词！ 如果您有4个字母，则会有24个排列组合，但同样只有1个组合。
这是算法的本质。 ToWordKey（）函数本质上是一个哈希函数。 所有具有相同字母数量和相同字母集合的字符串将哈希到相同的值。 因此，建立一个单词列表及其散列（Key - ToWordKey），然后给定一组字母用于生成单词，对这些单词进行散列（ToWordKey），并使用相同的散列值查找列表中的所有条目。 要扩展到查找任何长度的所有单词（给定一组字母），您只需对输入进行散列（通过ToWordKey发送整个字符串），然后查找任意长度的所有组合。 由于这些组合是由一组散列字母生成的，并且由于组合扩展方法保持了每个组合中字母的原始排序，所以每个组合都保留了散列的属性！ 这很酷！
希望这可以帮助。
这种方法似乎工作。 它使用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));
}
}
}
}
搜索一个词的所有排列组合的问题是将花在计算绝对乱码上的工作量。 生成所有的排列是O（n！），所以绝大部分将被浪费。 这就是我为什么推荐他的答案 。
这是一个递归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)
然而：
警告：我不喜欢这个非常低效的答案
现在linq最大的好处（对我来说）就是它的可读性。 话虽如此，但我并不认为上述代码的意图是清楚的 （我写了它！）。 因此LINQ的最大优势（我）不存在的上方， 并且它不是作为一个非LINQ溶液那样高效。 我通常原谅linq缺乏执行效率，因为它为编码时间，可读性和易维护性增加了效率，但我不认为linq解决方案在这里是最合适的......方形挂钩，圆孔排序如果你愿意的话。
另外，还有上面提到的复杂性问题。 当然，它可以在0.2秒内找到153个“小猪”字母或更多的排列，但给它一个像'簿记'一样的词，你会等待1分39秒，因为它找到所有435,574三个字母或更多排列。 那么为什么我发布这样一个可怕的功能？ 为了说明这个观点是正确的。 生成所有排列对于解决这个问题并不足够有效。
链接地址: http://www.djcxy.com/p/85031.html