読者です 読者をやめる 読者になる 読者になる

C Sharpens you up

http://qiita.com/yuba に移しつつあります

LINQで組み合わせを列挙する

.NET LINQ アルゴリズム

先週から話題のこちらのプログラミング課題

アプローチの仕方はいろいろあると思うのですが、新宿Scala座主宰のid:numanuma08氏は「Scalaだったらリストからすべての組み合わせを生成するのもcombinationsメソッドで一発だよ」といつも通りScala全力押しです*1
ところがその紹介の最後で

C#Linqとか使えばいけそうな気がします。

#新宿Scala座 で新入女子社員を救ってきた

今煽られました。
完全に煽られました。
LINQとやらで組み合わせ列挙書いてみろよほら張り子の虎とか笑わないからさと煽られました。

書いてやろーじゃねーの。

課題の整理

次のようなリスト

{2, 3, 5, 7}

から2つ組をと指定されたら

{ {2, 3},
  {2, 5},
  {2, 7},
  {3, 5},
  {3, 7},
  {5, 7} }

というリストのリストを返す処理をLINQだけで記述します。

2つの組み合わせを列挙するのは簡単

各アイテムについて、それ自身とそれより後のアイテムとの組み合わせ、をすべて列挙するだけです。
だからこう書き下ろせます。

static IEnumerable<List<T>> combinations2<T>(List<T> src)
{
    return src
        .SelectMany((num1, i) =>
            src.Skip(i).Select(num2 => new List<T> {num1, num2})
            );
}

しかし、Scalaのcombinationsメソッドには引数があります。「n個の組み合わせ」を列挙することが可能なのです。

n個の組み合わせを列挙するには

LINQにはちょっと大変な課題です。なぜならLINQは繰り返し処理を抽象化してくれるライブラリなのですが、n個の組み合わせを求めるのは「繰り返し処理の繰り返し適用」だからです。

もう少し具体的に言うと、LINQ

for (int i = 0; i < n; i++) {
  // 処理
}

という形で書ける処理はすっきり抽象化できます。ところが今からやろうとしている列挙は

for (int i = 0; i < n; i++) {
  for (int j = i + 1; j < n; j++) {
    for (int k = j + 1; k < n; k++) {
      // …(nの数だけループが深くなる)
    }
  }
}

という、繰り返し処理を再帰呼び出しする形の処理だということです。

しかし再帰呼び出しは繰り返し処理に書き換えられます。だからとても大変だけど不可能じゃない。先に結果だけどうぞ。

static IEnumerable<List<TSrc>> combinations<TSrc>(List<TSrc> src, int n)
{
    return Enumerable.Range(0, n - 1)
        .Aggregate(
            Enumerable.Range(0, src.Count() - n + 1)
                .Select(num => new List<int>(){ num }),
            (list, _) => list.SelectMany(c =>
                Enumerable.Range(c.Max() + 1, src.Count() - c.Max() - 1)
                    .Select(num => new List<int>(c){num})
                )
            )
        .Select(c => c
            .Select(num => src[num])
            .ToList()
            );
}

これは酷いですね。行数の倍くらいコメント書いても理解不能かも。

読み解くヒントなのですが、forループで値を更新していく処理をAggregateメソッドで実現しています。簡単な例で書くと

String str = "";
for (int i = 1; i <= 10; i++) str += i;
return str;

というのをLINQでは

return Enumerable.Range(1, 10)
  .Aggregate("", (str, num) => str + num);

という風に書けるということです。
この書き方でループを(n-1)周回して「1つの組み合わせの列挙」を「2つの組み合わせの列挙」、「3つの組み合わせの列挙」、…と成長させていっています。

また、組み合わせを生成する過程では引数として渡されたリストは使わずに整数のリストから組み合わせを列挙し、最後に渡されたリストのアイテムに置き換えています。

結論

これからもScala使いに煽られたら大人気なく突っ張ります。

*1:組み合わせ全列挙は商品数に対してO(n^2)の時間とメモリを使うので冒頭の問題の解き方としては不利です。片割れをまず列挙してそれぞれに最適な相手を二分探索するのならO(n log(n) )でいけます。だからこの記事では新人女子プログラマ問題からは離れて組み合わせ列挙のことだけ考えています。