Может ли кто-нибудь помочь мне с хорошим выражением LINQ для преобразования списка строк в другой список, содержащий только кратчайшие отдельные общие префиксы для строк? Разделитель для префиксов ..
Пример: ["A", "A.B.D", "A", "A.B","E","F.E", "F","B.C"]
Переход к: ["A", "E", "F", "B.C"]
Удалено:
Спасибо!
Здесь вы идете:
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));
В качестве объяснения:
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);
}
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 и скобки {}.
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, поскольку вы выбираете первый элемент в каждой группе, так что он действительно лишний.
Пригвожденно - если предположить, что если в списке источников содержатся "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"]
Как насчет:
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();
Он проверяет список на себя, исключая одинаковые элементы и любые элементы, которые начинаются с любого другого элемента. Я не уверен в эффективности, хотя:)
Я думаю, что это может быть трудно решить с помощью одного красивого выражения 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();
}
}
}
Возможно, код был более эффективным и более организованным, но у него нет времени для этого. Я думаю, что другие решения не так до сих пор, так что почему вы получаете мой более длинный. Я думаю, вам нужно решить эту проблему рекурсивно, чтобы получить кратчайший список.
Моя попытка, перемещает элементы, удаляя все префикс с другим элементом.
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();
}
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
Метод поиска самого длинного общего префикса из здесь (замените / на .).
Мое понимание вопроса гласит список, содержащий как "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
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();
Если я строго придерживаюсь определения, которое было предоставлено, ответ проще, чем кажется:
поэтому получаем:
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!