LINQ - Может ли это обратно?
-
26-09-2019 - |
Вопрос
Я возиюсь с LINQ, и мне любопытно посмотреть, что я могу сделать с этим. Я хотел бы знать, возможно ли возможность иметь запрос LINQ, который накладывает условие над полученным набором. Например, скажем, у меня есть список нескольких слов, и я хочу найти наборы слов, которые образуют цепочку (то есть последнее письмо слова = первая буква следующего слова, не ограничение на первое или последнее слово в цепочке) Отказ Что-то вроде «Привет, старый, молочный, желтый, мир ...».
Из этих наборов я бы тогда хотел взять набор, который формирует самую длинную цепочку.
Может ли LINQ сделать что-то вроде этого?
var chains = (from word in words
select word
where result.IsChain()).Max(x => x.Length);
Решение
LINQ может сделать почти все - хотя мне пришлось представить ограничение, что слова могут появляться только один раз в любой цепи, иначе я продолжал получать ошибки переполнения стека.
var words = new[]
{
"old", "dairy", "yellow",
"world", "dog", "dad",
"yard", "yolk", "yeah",
"king", "weld", "goat",
"hello",
};
Func<IEnumerable<IEnumerable<string>>, IEnumerable<string>, IEnumerable<IEnumerable<string>>> lengthenChains = (css, ws) =>
{
var endsWith = from cs in css
select new
{
Letter = cs.Last().Last(),
Chain = cs,
};
var startsWith = from w in ws
select new
{
Letter = w.First(),
Word = w,
};
return from ew in endsWith
join sw in startsWith on ew.Letter equals sw.Letter
where ew.Chain.Contains(sw.Word) == false
select ew.Chain.Concat(new[] { sw.Word });
};
Func<IEnumerable<string>, IEnumerable<IEnumerable<string>>> makeChain = ws =>
from w in ws
select (new[] { w, }).AsEnumerable();
Func<IEnumerable<IEnumerable<string>>, IEnumerable<string>, IEnumerable<IEnumerable<string>>> makeChains = null;
makeChains = (css, ws) =>
css.Any()
? css.Concat(makeChains(lengthenChains(css, ws), ws))
: Enumerable.Empty<IEnumerable<string>>();
var chains = from cs in makeChains(makeChain(words), words)
select String.Join(", ", cs.ToArray());
chains.Run(chain => Console.WriteLine(chain));
Я оставлю это для вас, чтобы получить максимальную цепочку длины. Из вашего вопроса не было понятно, если длина цепочки является количеством количества слов или если это длина символов сопряженных слов.
Вот последние 8, которые получают из вышеуказанного кода:
yellow, world, dairy, yeah, hello, old, dad, dog, goat
yellow, world, dad, dairy, yeah, hello, old, dog, goat
yellow, weld, dairy, yeah, hello, old, dad, dog, goat
yellow, weld, dad, dairy, yeah, hello, old, dog, goat
yeah, hello, old, dairy, yellow, world, dad, dog, goat
yeah, hello, old, dairy, yellow, weld, dad, dog, goat
yeah, hello, old, dad, dairy, yellow, world, dog, goat
yeah, hello, old, dad, dairy, yellow, weld, dog, goat
Наслаждаться.
Roly хотела больше «алгоритм пролога обратно пролога» - хотя его вопрос не сказал этого! ;-)
Вот:
var starting = from w in words
let c = (new[] { w }).AsEnumerable()
select new Working(c.ToArray(), words.Except(c).ToArray());
var chains = (from cs in Chains(starting)
select String.Join(", ", cs.ToArray())).ToArray();
IEnumerable<IEnumerable<string>> Chains(IEnumerable<Working> workings)
{
foreach (var w in workings)
{
yield return w.Chain;
var last = w.Chain.Last().Last();
var nexts = (from r in w.Remaining
where r.First() == last
let c = (new[] { r }).AsEnumerable()
select new Working(w.Chain.Concat(c).ToArray(), w.Remaining.Except(c).ToArray()));
foreach (var chain in Chains(nexts))
{
yield return chain;
}
}
}
Этот метод возвращается с помощью метода итератора, стека CLR и рекурсивных вызовов. Пролог сделает это более элегантно, но оказывается, мой комментарий к вероятной эффективности этого метода был неверным. Это на самом деле примерно в два раза быстрее, чем мой первый метод.
Я также чувствую, что этот второй метод отклоняется дальше от использования «Pure» LINQ, но он более чистый, меньший и более эффективный. Я знаю, я бы предпочел сохранить эту версию.
О, то Working
Класс (используется для отслеживания рабочего состояния), по сути это:
class Working
{
string[] Chain { get; set; }
string[] Remaining { get; set; }
}
Выход из этого подхода четко показывает, что он возвращается:
...
yeah, hello, old, dog
yeah, hello, old, dog, goat
yeah, hello, old, dad
yeah, hello, old, dad, dairy
yeah, hello, old, dad, dairy, yellow
yeah, hello, old, dad, dairy, yellow, world
yeah, hello, old, dad, dairy, yellow, world, dog
yeah, hello, old, dad, dairy, yellow, world, dog, goat
yeah, hello, old, dad, dairy, yellow, weld
yeah, hello, old, dad, dairy, yellow, weld, dog
yeah, hello, old, dad, dairy, yellow, weld, dog, goat
yeah, hello, old, dad, dairy, yard
yeah, hello, old, dad, dairy, yard, dog
yeah, hello, old, dad, dairy, yard, dog, goat
yeah, hello, old, dad, dairy, yolk
yeah, hello, old, dad, dairy, yolk, king
yeah, hello, old, dad, dairy, yolk, king, goat
yeah, hello, old, dad, dog
yeah, hello, old, dad, dog, goat
...