LINQ - kann es zurückverfolgen?

Question

Ich bin mit LINQ rum und bin gespannt, was ich damit machen kann. Ich würde gerne wissen, ob es möglich ist, eine LINQ-Abfrage zu haben, die eine Bedingung über die resultierende Menge auferlegt. Nehmen wir zum Beispiel an, ich habe eine Liste mit mehreren Wörtern, und ich möchte Sätze von Wörtern finden, die eine Kette bilden (dh der letzte Buchstabe eines Wortes = erster Buchstabe des nächsten Wortes, keine Beschränkung auf das erste oder letzte Wort in der Kette) . Etwas wie "Hallo, alt, Milch, gelb, Welt ...".

Von diesen Sets möchte ich dann das Set nehmen, das die längste Kette bildet.

Kann LINQ so etwas tun?

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

Answer 1

LINQ kann fast alles tun - obwohl ich eine Beschränkung einzuführen hatte, die Worte nur einmal in jeder Kette auftreten können ansonsten hielt ich Stack-Überlauf-Fehler bekommen.

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

Ich lasse es für Sie, um die maximale Länge Kette zu bekommen. Es war nicht klar aus Ihrer Frage, ob die Länge der Kette die Anzahl der Wörter zählt oder ob es die Zeichenlänge der verketteten Wörter ist.

Hier ist die letzten 8, die aus dem obigen Code erzeugt erhalten:

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 

Genießen.

---

Roly wollte mehr von einem "Prolog Backtracking-Algorithmus" - obwohl seine Frage das nicht gesagt hat! ;-)

Hier ist sie:

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

Diese Methode unter Verwendung eines Iteratormethode wird Rückzieher, die CLR-Stack und rekursive Aufrufe. Prolog würde das eleganter machen, aber es stellt sich heraus, dass mein Kommentar zu der wahrscheinlichen Effizienz dieser Methode falsch war. Es ist ungefähr zweimal schneller als meine erste Methode.

Ich glaube auch, dass diese zweite Methode weiter von der Verwendung von "reinem" LINQ abweicht, aber es ist sauberer, kleiner und effizienter. Ich weiß, dass ich diese Version lieber beibehalten möchte.

Oh, die Working Klasse (verwendet, um den Arbeitszustand zu verfolgen) ist im Wesentlichen dieses:

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

Die Ausgabe von diesem Ansatz zeigt deutlich, dass es Rückzieher:

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