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

享受。

---

不倒翁想要更多的“序言回溯算法” - 尽管他的问题没有说！ ; - ）

下面，它是：

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栈，和递归调用回溯。序言会做到这一点更优雅，但事实证明，我的评论对这种方法的效率可能是错误的。它实际上是两倍左右的速度比我的第一个方法。

我也觉得这个第二方法进一步从使用“纯” 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
...