C# の LINQ によるべき集合(powerset)

　最近、職場で C# を使い始めました。 C# なんて Java と同じだろうとタカをくくっていたのですが、いざ勉強してみると、LINQ というものがかなり便利だと実感しました。このページでは、べき集合(全ての部分集合の集合)を作るというお題を通して、 C# の LINQ の素晴らしさのお伝えしようと思います。

　まずは、べき集合を求めるプログラムを具体的に見てみましょう。以下のようになります。

List-1: C# によるべき集合を求めるプログラム１

using System;
using System.Collections.Generic;
using System.Linq;

namespace Powerset1
{
    class Program
    {
        static void Main(string[] args)
        {
            var s = Enumerable.Range(1, 100); // 要素数が100個の集合を準備
            var p = powerset(s);              // そのべき集合を求める
            foreach (var x in p.Skip(100000000).Take(10))
            { //１億個目から１０個の部分集合を表示する
                Console.WriteLine(string.Join(",", x));
            }
        }

        static IEnumerable<IEnumerable<T>> powerset<T>(IEnumerable<T> e)
        {
            return powerset0(new HashSet<T>(e));
        }
        static IEnumerable<IEnumerable<T>> powerset0<T>(IEnumerable<T> s)
        {
            if (!s.Any()) return new List<IEnumerable<T>>{s};
            var a = s.Take(1);
            var b = powerset0(s.Skip(1));
            var c = b.Select(x => a.Concat(x));
            return c.Concat(b);
        }
    }
}

　集合論を勉強したことのある人なら、このプログラムを見て要素数が１００個の集合のべき集合なんて求めたらメモリが足りなくなるだろ？と思うかもしれません。ところが、このプログラムは、時間はかかりますが何事もなかったように動き続け、１億個目から１０個の部分集合を表示して無事終了します。

　実は LINQ は遅延評価で実行されます。そのため、字面から判断すると \(2^{100}\) 個の部分集合を生成して p に保持するように見えるこのプログラムも、実際には表示に必要な１０個の部分集合しか生成しないのです。厳密に言うと、表示は１度に１個の部分集合しか要求しないので、メモリを占有するのは１個分の部分集合のみです。ですから、例えば \(2^{100}\) 個全てを表示したとしてもメモリが不足することはありません。まあ、絶望的なまでに時間はかかるでしょうけどね。

　どうです？ LINQ ってすごいでしょ？私は、Haskell のような関数型言語でこういうことができるのは知っていましたが、手続き型言語の C# でこんなことができるとは知りませんでした。上記のプログラムはべき集合を求める典型的な再帰のアルゴリズムですが、分かりやすいけれど、１度に全ての部分集合を求めてしまいます。そのため普通の手続き型言語言語の仕組みで計算するとメモリが足りなくなります。しかし、C# では LINQ を用いると、分かりやすさを維持したまま一部分の部分集合を求めることができるのです。

【高速版】

　さて、上記のアルゴリズムは再帰を使っているので遅いです。そこで、もう少し速いアルゴリズムを求めてみましょう。部分集合の要素を含む含まないの関係は、もとの集合の要素数を \(N\) とした場合、 \(0\) から \(2^N-1\) の数を２進数で表した時のビットパターンと１対１対応します。この事実を使って部分集合を生成すると、再帰より高速に部分集合を生成できます。

List-2: C# によるべき集合を求めるプログラム２

using System;
using System.Collections.Generic;
using System.Linq;

namespace Powerset2
{
    class Program
    {
        public static void Main(string[] args)
        {
            var s = Enumerable.Range(1, 30);
            var p = powerset(s);
            foreach (var x in p.Skip(100000000).Take(10))
            {
                Console.WriteLine(string.Join(",", x));
            }
        }

        public static IEnumerable<IEnumerable<T>> powerset<T>(IEnumerable<T> e)
        {
            var s = new HashSet<T>(e);
            var n = s.Count;
            var N = 1 << n;
            return Enumerable.Range(0, N).Select(m =>
                    Enumerable.Range(0, n).Where(i => (m & 1 << i) != 0)
                    .Select(i => s.ElementAt(i)));
        }
    }
}

　ただ、このアルゴリズム、最初のアルゴリズと違って要素数が３０個の集合のべき集合を求めています。なぜかというと、整数の変数のビット幅が３２なので、 \(2^{100}\) のような巨大な整数は表現できないからです。

　しかし、最適化問題等で全ての部分集合が必要になるような場合、総当たり方式で現実的に解ける範囲は \(2^{30}\) あたりが限界でしょうから、この制限は妥当なものと言えるでしょう。

　\(2^{100}\) とはいかなくとも、もう少し制限を緩和したいという場合は、以下のようにすることもできます。整数変数を ulong にして６４ビットにします。

List-3: C# によるべき集合を求めるプログラム３

using System;
using System.Collections.Generic;
using System.Linq;

namespace Powerset3
{
    class Program
    {
        static void Main(string[] args)
        {
            var s = Enumerable.Range(1, 63);
            var p = powerset(s);
            foreach (var x in p.Skip(100000000).Take(10))
                Console.WriteLine(string.Join(",", x));
        }

        static IEnumerable<IEnumerable<T>> powerset<T>(IEnumerable<T> e)
        {
            var s = new HashSet<T>(e);
            var n = s.Count;
            var N = 1UL << n;
            return ULongRange(N).Select(m =>
                    Enumerable.Range(0, n).Where(i => (m & 1UL << i) != 0)
                    .Select(i => s.ElementAt(i)));
        }
        static IEnumerable<ulong> ULongRange(ulong n)
        {
            for (ulong i = 0; i < n; i++) yield return i;
        }
    }
}

　Enumerable.Range の６４ビット版が ULongRange(n) ですが、 yield return を使って簡単に実装できています。このあたりも C# の便利なところですね。