部分集合を列挙するアルゴリズム

例えば{1, 2} → {}, {1}, {2}, {1, 2}のように（ある集合に含まれる要素の）全ての組み合わせ（全ての部分集合）を列挙するアルゴリズム。

各要素を使う/使わない（ということは → on/off → 1/0）の組み合わせなので、ビット値の列…つまり2進数の表現と同じ。要素数が2なら結果は2ビットで表せる4通り、要素数が3なら8通り。
++していくだけで新しい組み合わせが得られる。

そのビット列を参考に要素の組み合わせを生成。ビット演算子&とビットマスクで1ビットずつ0/1を判定。

コード(C#)

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

public class App
{
    private static List<List<T>> Subsets<T>(List<T> elements)
    {
        var ret = new List<List<T>>();

        for (ulong n = 0; n < (ulong)1 << elements.Count; n++)
        {
            ret.Add(new List<T>());

            // 2進数表記→与えられた要素
            for (var i = 0; i <= elements.Count - 1; i++)
                if ((n & (ulong)1 << i) != 0)
                    ret.Last().Add(elements[i]);
        }

        Debug.Assert(ret.Count == 1 << elements.Count);

        return ret;
    }

    static public void main()
    {
        var elements = new List<string>() { "A", "B", "C", };
        //var elements = new List<object>() { "A", "B", "C", "D", 1.01F, DateTime.Now, };

        var sets = Subsets(elements);

        // おまけ
        {
            Debug.Print("enumerate subsets of {{{0}}}({1})", new object[] { String.Join(", ", elements), elements.Count, });

            var num = 1;
            foreach (var s in sets)
            {
                Debug.Print("{0}: {{{1}}}", new object[] { num++.ToString("00"), String.Join(", ", s), });
            }
        }
    }
}

実行例

enumerate subsets of {A, B, C}(3)
01: {}
02: {A}
03: {B}
04: {A, B}
05: {C}
06: {A, C}
07: {B, C}
08: {A, B, C}