Find Strings with certain Hamming distance LINQ

Question

If we run the following (thanks to @octavioccl for help) LINQ Query:

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

It gives us all the strings which occur in the list atleast twice (but exactly matched i.e. Hamming Distance =0).

I was just wondering if there is an elegant solution (all solutions I have tried so far either use loops and a counter which is ugly or regex) possible where we can specify the hamming distance in the Where clause to get those strings as well which lie within the specified Hamming Distance range?

P.S: All the strings are of equal length

UPDATE

Really thanks to krontogiannis for his detailed answer. As I mentioned earlier, I want to get list of strings with hamming distance below the given threshold. His code is working perfectly fine for it (Thanks again).

Only thing remaining is to take the strings out of the 'resultset' and insert/add into a `List'

Basically this is what I want:

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
            }

Thanks

Answer 1

Calculating the hamming distance between two strings using LINQ can be done in an elegant way:

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

You question is a bit vague about the 'grouping'. As you can see to calculate the hamming distance you need two strings. So you either need to calculate the hamming distance for all the words in your string list vs an input, or calculate the distance between all for the words in your list (or something different that you need to tell us :-) ).

In any way i'll give two examples for input

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

Case 1

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

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

Output would be something like

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

Case 2

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

Output would be something like

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

---

Edit To get only the words from the first grouping you can use SelectMany

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