代码之家 › 专栏 › 技术社区 › Roly

林肯-它能后退吗?

backtracking linq

Roly · 技术社区 · 15 年前

我在和林肯鬼混,我很想看看我能用它做些什么。我想知道是否有可能有一个LINQ查询,对结果集施加一个条件。例如,假设我有一个包含几个单词的列表,我希望找到组成一个链的单词集(即单词的最后一个字母=下一个单词的第一个字母,链中的第一个或最后一个单词没有约束)。像“你好,老,奶制品,黄色,世界…”。

从这些集合中,我想得到组成最长链的集合。

林克能做这样的事吗?

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

1 回复 | 直到 15 年前

Enigmativity 15 年前

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));

我把它留给你,让你得到最大长度的链条。从您的问题中不清楚链的长度是单词数的计数还是连接单词的字符长度。

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

享受吧。

罗利想要更多的“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
...