c# - 查找具有特定汉明距离LINQ的琴弦

如果我们运行以下命令（感谢@octavioccl来提供帮助）LINQ查询：

var result = stringsList
.GroupBy(s => s)
  .Where(g => g.Count() > 1)
  .OrderByDescending(g => g.Count())
  .Select(g => g.Key);

它为我们提供了至少两次出现在列表中的所有字符串（但完全匹配，即汉明距离= 0）。

我只是想知道是否存在一个优雅的解决方案（到目前为止，我尝试过的所有解决方案都使用循环和丑陋的或正则表达式的计数器），我们可以在Where子句中指定汉明距离以获取这些字符串哪些位于指定的汉明距离范围内？

附注：所有琴弦的长度相等

更新

非常感谢krontogiannis的详细回答。如前所述，我想获得汉明距离低于给定阈值的字符串列表。他的代码为此工作得很好（再次感谢）。

剩下的唯一事情就是将字符串从“结果集”中取出并插入/添加到“列表”中

基本上这就是我想要的：

List<string> outputList = new List<string>();
foreach (string str in patternsList)
            {
                var rs = wordsList
    .GroupBy(w => hamming(w, str))
    .Where(h => h.Key <= hammingThreshold)
    .OrderByDescending(h => h.Key)
    .Select(h => h.Count());
outputList.Add(rs); //I know it won't work but just to show what is needed
            }

谢谢

最佳答案

可以使用LINQ来计算两个字符串之间的汉明距离，这很简单：

Func<string, string, int> hamming = (s1, s2) => s1.Zip(s2, (l, r) => l - r == 0 ? 0 : 1).Sum();

您的问题是关于“分组”的含糊之处。如您所见，计算汉明距离需要两个字符串。因此，您要么需要计算字符串列表中所有单词相对于输入的汉明距离，要么需要计算列表中所有单词之间的汉明距离（或者需要告诉我们的其他不同点:-)）。

无论如何，我将给出两个输入示例

var words = new[] {
    "hello",
    "rellp",
    "holla",
    "fooba",
    "hempd"
};

情况1

var input = "hello";
var hammingThreshold = 3;

var rs = words
    .GroupBy(w => hamming(w, input))
    .Where(h => h.Key <= hammingThreshold)
    .OrderByDescending(h => h.Key);

输出将类似于

hempd with distance 3
rellp holla with distance 2
hello with distance 0

情况二

var hs = words
    .SelectMany((w1, i) =>
        words
            .Where((w2, j) => i > j)
            .Select(w2 => new { Word1 = w1, Word2 = w2 })) // all word pairs except with self
    .GroupBy(pair => hamming(pair.Word1, pair.Word2))
    .Where(g => g.Key <= hammingThreshold)
    .OrderByDescending(g => g.Key);

输出将类似于

(holla, rellp) (fooba, holla) (hempd, hello) with distance 3
(rellp, hello) (holla, hello) with distance 2

编辑要仅从第一个分组中获取单词，可以使用SelectMany

var output = rs.SelectMany(g => g).ToList();

关于c# - 查找具有特定汉明距离LINQ的琴弦，我们在Stack Overflow上找到一个类似的问题：https://stackoverflow.com/questions/37498735/