Выражение LINQ для кратчайшего общего префикса

Ответ 1

Здесь вы идете:

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

В качестве объяснения:

• Сначала мы разделили все строки на. и группа по их первому токену.
• Затем мы рассмотрим первый элемент каждой группы, и мы берем от него части, в то время как каждый элемент этой группы продолжает соответствовать (TakeWhile).
• Затем мы берем все эти части и перестраиваем их с помощью Aggregate (String.Format).

Ответ 2

EDIT: благодаря комментариям, указывающим на ошибку в моем предыдущем подходе.

Чтобы обойти этот недостаток, этот запрос должен работать:

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

Неправильный подход:

Следующий запрос будет группировать каждую строку по первому символу. Затем, если количество групп имеет более одного элемента, выбран ключ, в противном случае выбран один элемент.

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

Ответ 3

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

Шаги:

(1) Удалите дублированные элементы с помощью Distinct()

(2) Разделить каждый элемент на массив, также подготовиться к группировке

(3) Группируйте эти массивы с помощью первой строки в массиве

(4) Для каждой группы создайте один общий префикс, объединив все массивы в группе. Логикой для агрегирования является то, что для двух массивов arr1 и arr2 взять элементы в arr1 до (1) вне границ (2) соответствующий элемент в arr2 отличается от

Примечание. Я добавляю два оператора return в код, чтобы сделать его более понятным. Это может быть короче, если удалить return и скобки {}.

Ответ 4

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

Закажите элементы по их длине, вызовите разный, чтобы удалить дубликаты, конвертировать в группы на основе первого символа и выбрать первый элемент в каждой группе.

Урожайность:    "A", "E", "F", "B.C"

Изменить: вам, вероятно, даже не нужен Distinct, поскольку вы выбираете первый элемент в каждой группе, так что он действительно лишний.

Ответ 5

Пригвожденно - если предположить, что если в списке источников содержатся "Q.X" и "Q.Y", тогда результат должен содержать "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"]

Ответ 6

Как насчет:

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

Он проверяет список на себя, исключая одинаковые элементы и любые элементы, которые начинаются с любого другого элемента. Я не уверен в эффективности, хотя:)

Ответ 7

Я думаю, что это может быть трудно решить с помощью одного красивого выражения linq, поэтому я написал рекурсивную функцию с использованием linq, которая решает проблему:

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

Возможно, код был более эффективным и более организованным, но у него нет времени для этого. Я думаю, что другие решения не так до сих пор, так что почему вы получаете мой более длинный. Я думаю, вам нужно решить эту проблему рекурсивно, чтобы получить кратчайший список.

Ответ 8

Моя попытка, перемещает элементы, удаляя все префикс с другим элементом.

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

Ответ 9

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

Вывод:

A
E
F
B.C

Метод поиска самого длинного общего префикса из здесь (замените / на .).

Ответ 10

Мое понимание вопроса гласит список, содержащий как "B.C", так и "B.E", но "B" не получит "B.C" и "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);
}

Выход

A
E
F
B.C

также работает с многосимвольными префиксами

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

получает

Alpha
Echo
Foxtrot
Baker.Charlie

Ответ 11

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

Ответ 12

Если я строго придерживаюсь определения, которое было предоставлено, ответ проще, чем кажется:

• удалить дубликаты = > отдельные
• удалить любой элемент, который начинается с любого другого элемента в списке.

поэтому получаем:

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

Для вопросов B.C и B.D это работает так, как указано: ни один не включает другой, поэтому ни одно из условий удаления, упомянутых dave, не запускается.

Я признаю, что могут быть более интересные участники, но я боюсь, что просто не в вопросе;)

Обновление: добавлено предложение разделителя в where для учета слов multi- char. спасибо svick!