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