5

我在搞乱LINQ，我很想知道我能用它做什么。我想知道是否有可能对结果集施加条件的 LINQ 查询。例如，假设我有一个包含几个单词的列表，并且我希望找到形成链的单词集（即单词的最后一个字母 = 下一个单词的第一个字母，对链中的第一个或最后一个单词没有限制） . 像“你好，老的，乳制品，黄色的，世界......”之类的东西。

然后，我想从这些集合中获取形成最长链的集合。

LINQ 可以做这样的事情吗？

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

1 回答 1

5

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 想要更多的“序言回溯算法”——尽管他的问题没有这么说！;-)

这里是：

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
...
于 2010-10-27T10:26:23.270 回答