LINQ - 它可以回溯？

Question

我在搞LINQ，我很好奇，看看我能用它做什麼。我想知道是否可以有一個LINQ查詢對結果集施加條件。例如，假設我有一個單詞列表，我希望找到形成鏈的單詞集（即單詞的最後一個單詞=下一個單詞的第一個單詞，對鏈中的第一個單詞或最後一個單詞沒有限制） 。像「你好，老，奶製品，黃色，世界......」。

從這些集合中，我會想要採取形成最長鏈的集合。

LINQ可以做這樣的事嗎？

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

Answer 1

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想要更多的「prolog回溯算法」 - 雖然他的問題沒有說！ ;-)

這：

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棧，和遞歸調用回溯。 Prolog會更優雅地做到這一點，但事實證明，我對這種方法的可能效率的評論是錯誤的。它實際上比我的第一種方法快兩倍。

我也覺得第二種方法更偏離於使用「純粹」的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 
...