ビット演算を利用してべき集合を作成する。

参考: 「C#でサイズnの順列をすべて生成したい。」

表題のとおり「ビット演算でべき集合を作成する」ことがあったので、その際のメモになります。なお以下のサンプルはC#を利用していますが、内容としてはほかの言語でも通用するものと思います。

単純な内容のため、実装方法はさまざまにあると思いますが、とりあえずforループをつかって"べた"に書いてみます。

int n = 5;
for (int bit = 0; bit < 1 << n; bit++)
{
    var permutation = new List<int>();
    for (int i = 0; i < n; i++)
    {
        if ((bit & (1 << i)) != 0)
        {
            permutation.Add(i);
        }
    }
    Console.WriteLine("[" + string.Join(",", permutation) + "]");
}

以上のプログラムは、n個の集合から作成されるべき集合を表示するものです(表示内容は後述)。注意としては整数型としてintを利用しているため、nがあまりに大きくなるとオーバーフローを起こし、プログラムとして破綻する可能性があります。

せっかくC#を利用しているということもあり、全く同じ内容をLINQで実装してみたいと思います。

int n = 5;
var permutations = Enumerable.Range(0, 1 << n)
                             .Select(bit => Enumerable.Range(0, n).Where(i => (bit & (1 << i)) != 0));
foreach(var permutation in permutations)
{
    Console.WriteLine("[" + string.Join(",", permutation) + "]");
}

全般的に記述がシンプルになりますね(´・ω・｀)

---

ふたつのプログラムの表示結果はどちらも次のようになるはずです。

[]
[0]
[1]
[0,1]
[2]
[0,2]
[1,2]
[0,1,2]
[3]
[0,3]
[1,3]
[0,1,3]
[2,3]
[0,2,3]
[1,2,3]
[0,1,2,3]
[4]
[0,4]
[1,4]
[0,1,4]
[2,4]
[0,2,4]
[1,2,4]
[0,1,2,4]
[3,4]
[0,3,4]
[1,3,4]
[0,1,3,4]
[2,3,4]
[0,2,3,4]
[1,2,3,4]
[0,1,2,3,4]