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