5

私はLINQをいじっていますが、それを使って何ができるのか知りたいです。結果のセットに条件を課すLINQクエリを使用できるかどうかを知りたいです。たとえば、いくつかの単語のリストがあり、チェーンを形成する単語のセットを見つけたいとします（つまり、単語の最後の文字=次の単語の最初の文字、チェーンの最初または最後の単語に制約はありません） 。「こんにちは、古い、乳製品、黄色、世界...」のようなもの。

これらのセットから、最長のチェーンを形成するセットを取得したいと思います。

LINQはこのようなことを行うことができますか？

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

1 に答える 1

5

LINQはほとんどすべてのことを実行できますが、単語はチェーン内で1回しか表示されないという制約を導入する必要がありました。そうしないと、スタックオーバーフローエラーが発生し続けました。

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はこれをよりエレガントに行うでしょうが、この方法のおそらく効率についての私のコメントは間違っていたことがわかりました。実際、最初の方法よりも約2倍高速です。

また、この2番目の方法は、「純粋な」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 に答える