CODEWITHSUNDEEP
c#linq
dave
dave

Reputation: 171

LINQ expression for shortest common prefix

Can anyone help me with a nice LINQ expression for transforming a list of strings in another list containing only the shortest distinct common prefixes for the strings? The delimiter for prefixes is ..

Example: ["A", "A.B.D", "A", "A.B","E","F.E", "F","B.C"]

Goes to: ["A", "E", "F", "B.C"]

Removed:

Thanks!

Upvotes: 17

Views: 3318

Answers (12)

AlexandrYZ
AlexandrYZ

Reputation: 331

var list = new List<string> { "A", "A.B.D", "A", "A.B", "E", "F.E", "F", "B.C" };

var result = (list.Select(a => a.Split('.').First())).Distinct();

Upvotes: -1

Stefan Wenig
Stefan Wenig

Reputation: 178

If I strictly stick to the definition that dave provided, the answer is easier than it seems:

  • remove duplicates => distinct
  • remove any item that starts with any other item in the list

so we get:

from item in items.Distinct()
where !items.Any(other => other != item && item.StartsWith(other + '.'))
select item;

For the B.C and B.D question, this works as specified: Neither one includes the other, so none of the removing conditions mentioned by dave is triggered.

I admit that there might be more exciting anwers, but I'm afraid that's just not in the question ;)

Update: added delimiter to where clause in order to account for multi-char words. thanks svick!

Upvotes: -1

jtdubs
jtdubs

Reputation: 13973

Here you go:

from set in
    (from item in list select item.Split('.')).GroupBy(x => x[0])
select
  set.First()
     .TakeWhile((part, index) => set.All(x => x.Length > index && x[index].Equals(part)))
     .Aggregate((x, y) => String.Format("{0}.{1}", x, y));

By way of explanation:

  1. First, we split all the strings by '.' and group by their first token.
  2. Then, we look at the first element of each grouping, and we take parts from it while every element of that group continues to match (TakeWhile).
  3. Then, we take all those parts and recompose them with the Aggregate(String.Format).

Upvotes: 3

Handcraftsman
Handcraftsman

Reputation: 6983

My understanding of the question says a list containing both "B.C" and "B.E" but no "B" would get both "B.C" and "B.E".

string[] items = { "A", "A.B.D", "A", "A.B", "E", "F.E", "F", "B.C" };
char delimiter = '.';
var result = (from item in items.Distinct()
             where !items.Any(other => item.StartsWith(other + delimiter))
             select item).ToArray();

foreach (var item in result)
{
    Console.WriteLine(item);
}

output

A
E
F
B.C

also works with multi-character prefixes

string[] items = 
{
    "Alpha",
    "Alpha.Beta.Delta",
    "Alpha",
    "Alpha.Beta",
    "Echo",
    "Foxtrot.Echo",
    "Foxtrot",
    "Baker.Charlie"
 };

gets

Alpha
Echo
Foxtrot
Baker.Charlie

Upvotes: 1

dtb
dtb

Reputation: 217313

var list = new[] { "A.B.D", "A", "E", "A.B", "F", "F.E", "B.C.D", "B.C" };

var result = from s in list
             group s by s.Split('.').First() into g
             select LongestCommonPrefix(g);

foreach (var s in result)
{
    Console.WriteLine(s);
}

Output:

A
E
F
B.C

Method to find longest common prefix from here (replace / with .).

Upvotes: 2

Patrick Huber
Patrick Huber

Reputation: 756

My attempt, loop through items removing anything prefixed with another item.


static void Run()
{
    var list = new string[] {"A", "A.B.D", "A",
                            "A.B", "E", "F.E",
                            "F", "B.C",
                            "Q.X", "Q.Y",
                            "D.A.A", "D.A.B"
                        };

    int size = 0;
    var prefixList = new string[list.Length];
    Array.Copy(list, prefixList, list.Length);

    for (int i = 0; i < list.Length; i++)
        prefixList 
        = prefixList
            .Where(c => !c.StartsWith(list[i]) || c == list[i])
            .Distinct()
                .ToArray();

    foreach (string s in prefixList)
        Console.WriteLine(s);
    Console.ReadLine();
}

Upvotes: 2

Tomas Jansson
Tomas Jansson

Reputation: 23472

I think it might be hard to solve with one single nice looking linq expression so I wrote a recursive function using linq that solves the problem:

class Program
{
    static void Main(string[] args)
    {
        var input = new string[] { "A", "A.B.D", "A", "A.B", "E", "F.E", "F", "B.C", "B.C.D", "B.E" };

        var output = FilterFunc(input);
        foreach (var str in output)
            Console.WriteLine(str);

        Console.ReadLine();
    }

    static string[] FilterFunc(string[] input)
    {
        if (input.Length <= 1)
            return input;
        else
        {
            var firstElem = input[0];
            var indexNr = firstElem.Length;
            var maxFilteredElems = 0;
            for (int i = firstElem.Length; i > 0; i--)
            {
                var numberOfFilteredElems = input.Where(x => x.StartsWith(firstElem.Substring(0, i))).Count();
                if (numberOfFilteredElems > maxFilteredElems)
                {
                    maxFilteredElems = numberOfFilteredElems;
                    indexNr = i;
                }
            }
            var prefix = firstElem.Substring(0, indexNr);
            var recursiveResult = FilterFunc(input.Where(x => !x.StartsWith(prefix)).ToArray());
            var result = recursiveResult.ToList();
            prefix = prefix.EndsWith(".") ? prefix.Substring(0, prefix.Length - 1) : prefix;
            result.Insert(0, prefix);
            return result.ToArray();
        }
    }
}

The code could probably be more effective and more organized but don't have time for that now. I think the other solutions are wrong so far, so that's why you get my longer one. I think you need to solve it recursively to be sure to get the shortest list.

Upvotes: 2

Claus Asbj&#248;rn S&#248;rensen
Claus Asbj&#248;rn S&#248;rensen

Reputation: 571

How about:

var possible = new List<string> { "A", "A.B.D", "A", "A.B", "E", "F.E", "F", "B.C" };
var shortest = possible.Distinct().Where(x => possible.Distinct().Where(y => !y.Equals(x) && x.StartsWith(y)).Count() == 0).ToList();

It checks the list against itself excluding items that are equal and any items that starts with any of the other items. I'm not sure about the effeciency though :)

Upvotes: 2

Cheng Chen
Cheng Chen

Reputation: 43523

string[] source = {"A", "A.B", "A.B.D", "B.C", "B.C.D", "B.D", "E", "F", "F.E"};
var result = 
source.Distinct()
      .Select(str => str.Split('.'))
      .GroupBy(arr => arr[0])
      .Select(g =>
        {
          return string.Join(".", 
                 g.Aggregate((arr1, arr2) =>
                    {
                      return arr1.TakeWhile((str, index) => index < arr2.Length 
                                               && str.Equals(arr2[index]))
                                 .ToArray();
                    }));
        });

Steps:

(1) Remove duplicated elements by Distinct()

(2) Split each element to an array, also get ready to be grouped

(3) Group those arrays by the first string in the array

(4) For each group, create one common prefix by aggregating all arrays in the group. The logic for aggregating is that for two arrays arr1 and arr2, take the elements in arr1 until (1)out of bounds (2) corresponding element in arr2 is different

Note: I add two return statements in the code, to make it look cleaner. It can be shorter if remove return and its {} brackets.

Upvotes: 2

Enigmativity
Enigmativity

Reputation: 117064

Nailed it - assuming that if the source list contains "Q.X" & "Q.Y" then the result should contain "Q".

var source = new []
{
    "A", "A.B.D", "A",
    "A.B", "E", "F.E",
    "F", "B.C",
    "Q.X", "Q.Y",
    "D.A.A", "D.A.B",
};

Func<string, int> startsWithCount =
    s => source.Where(x => x.StartsWith(s)).Count();

var results =
    (from x in source.Distinct()
    let xx = x.Split('.')
    let splits = Enumerable
        .Range(1, xx.Length)
        .Select(n => String.Join(".", xx.Take(n)))
    let first = startsWithCount(splits.First())
    select splits
        .Where(s => startsWithCount(s) == first)
        .Last()
    ).Distinct();


// results == ["A", "E", "F", "B.C", "Q", "D.A"]

Upvotes: 2

Ahmad Mageed
Ahmad Mageed

Reputation: 96497

EDIT: thanks to the comments for pointing out a bug in my earlier approach.

To get around that shortcoming this query should work:

var list = new List<string> { "A.B.D", "A", "A.B","E","F.E", "F","B.C", "B.C.D" };
var result = list.OrderBy(s => s)
                 .GroupBy(s => s[0])
                 .Select(g => g.First());

foreach (var s in result)
{
    Console.WriteLine(s);
}

Incorrect approach:

The following query will group each string by the first character. Next, if the group count has more than one item the key is selected, otherwise the single item is selected.

var list = new List<string> { "A", "A.B.D", "A", "A.B", "E", "F.E", "F", "B.C" };
var result = list.GroupBy(s => s[0])
                 .Select(g => g.Count() > 1 ? g.Key.ToString() : g.Single());

foreach (var s in result)
{
    Console.WriteLine(s);
}

Upvotes: 2

Matthew Abbott
Matthew Abbott

Reputation: 61599

    var items = new[] { "A", "A.B.D", "A", "A.B", "E", "F.E", "F", "B.C" };
    var result = items
        .OrderBy(s => s.Length)
        .Distinct()
        .ToLookup(s => s.Substring(0, 1))
        .Select(g => g.First());

Order the items by their length, call distinct to remove duplicates, convert to groupings based on the first character, and select the first item in each group.

Yields: "A", "E", "F", "B.C"

Edit: You probably don't even need Distinct as your selecting the first item in each group anyway, so it's really redundant.

Upvotes: 2

Related Questions