LINQ - czy można cofnąć?

Question

Zajmuję się LINQ i jestem ciekaw, co mogę z nim zrobić. Chciałbym wiedzieć, czy możliwe jest mieć kwerendę LINQ, która nakłada warunek na wynikowy zestaw. Na przykład, powiedzmy, że mam listę kilku słów i chciałbym znaleźć zestawy słów, które tworzą łańcuch (tj. Ostatnia litera słowa = pierwsza litera następnego słowa, brak ograniczenia pierwszego lub ostatniego słowa w łańcuchu) . Coś w stylu "cześć, stary, mleczarnia, żółty, świat ...".

Z tych zestawów chciałbym wziąć zestaw, który tworzy najdłuższy łańcuch.

Czy LINQ może zrobić coś takiego?

var chains = (from word in words 
      select word 
      where result.IsChain()).Max(x => x.Length); 

Answer 1

LINQ może zrobić niemal wszystko - chociaż musiałem wprowadzić ograniczenie, że słowa mogą pojawić tylko raz w każdym łańcuchu inaczej Ciągle otrzymuję błędy przepełnienia stosu.

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

Zostawię to, aby uzyskać maksymalny łańcuch długości. Z twojego pytania nie wynikało, czy długość łańcucha to liczba słów, czy też długość znaków połączonych słów.

Oto ostatnie 8, która jest generowana z powyższego kodu:

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 

Enjoy.

---

Roly chciał więcej "algorytmu wstecznego prologu" - chociaż jego pytanie nie mówiło tego! ;-)

Oto ona:

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

Ta metoda jest backtracking stosując metody iteracyjnej, stos CLR i wzywa rekurencyjnych. Prolog zrobiłby to bardziej elegancko, ale okazało się, że mój komentarz co do prawdopodobnej skuteczności tej metody był błędny. Jest to około dwa razy szybsze niż moja pierwsza metoda.

Uważam również, że ta druga metoda jest odbiegająca od używania "czystego" LINQ, ale jest czystsza, mniejsza i bardziej wydajna. Wiem, że wolę zachować tę wersję.

Och, klasa Working (wykorzystywane do śledzenia stanu roboczego) jest zasadniczo to:

class Working 
{ 
    string[] Chain { get; set; } 
    string[] Remaining { get; set; } 
} 

Wyjście z tego podejścia wyraźnie pokazuje, że jest backtracking:

... 
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 
... 

nie