組み合わせを列挙するアルゴリズム

例えば5要素集合の5C3、10通りを生成。
組み合わせはビット演算。2進数で簡略化できそう。

…だったけど、帰納的なほうが分かりやすかったのでそっちで。
2進数に置き換えたり、2進数から置き換えたりしなくていいので圧倒的に分かりやすい。

コード(C#)

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

public class App
{
    // nCm ... n:elements.Count, m:choose
    static List<List<T>> Combination<T>(IList<T> elements, int choose)
    {
        var ret = new List<List<T>>();

        // 再帰呼び出しの終端
        if (elements.Count < choose)
            return new List<List<T>>();
        else if (choose <= 0)
            return new List<List<T>>() { new List<T>() };

        // 本体
        for (var n = 1; n <= elements.Count; n++)
        {
            var subRet = Combination(elements.Skip(n).ToList(), choose - 1);
            subRet.ForEach(e => e.Add(elements[n - 1]));
            ret.AddRange(subRet);
        }

        return ret;
    }
}

コード(C#)

アサーション（実行できるコメント）と使用例を追加、というか削除してないもの。

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

public class App
{
    // nCm ... n:elements.Count, m:choose
    static List<List<T>> Combination<T>(IList<T> elements, int choose)
    {
        var ret = new List<List<T>>();

        // 再帰呼び出しの終端
        if (elements.Count < choose)
        {
            Debug.Assert(0 <= elements.Count && elements.Count < choose);
            return new List<List<T>>();
        }
        else if (choose <= 0)
        {
            Debug.Assert(choose <= 0 && 0 <= elements.Count);
            return new List<List<T>>() { new List<T>() };
        }

        Debug.Assert(choose >= 1);
        Debug.Assert(elements.Count >= 1);
        Debug.Assert(elements.Count >= choose);

        // 本体
        for (var n = 1; n <= elements.Count; n++)
        {
            var subRet = Combination(elements.Skip(n).ToList(), choose - 1);
            subRet.ForEach(e => e.Add(elements[n - 1]));
            ret.AddRange(subRet);
        }

#if DEBUG
        {
            var count = new Dictionary<T, int>();
            foreach (var combi in ret)
            {
                foreach (var elem in combi)
                {
                    if (count.ContainsKey(elem))
                        count[elem]++;
                    else
                        count.Add(elem, 1);
                }
            }
            Debug.Assert(count.All(e => count.Count * e.Value == ret.Count * choose));
            Debug.Assert(count.Sum(e => e.Value) == ret.Sum(e => e.Count));

            if (elements.Count >= choose)
            {
                Debug.Assert(ret.All(e => e.Count == choose));
                Debug.Assert(ret.Count == Factorial(elements.Count) / (Factorial(elements.Count - choose) * Factorial(choose)));
                Debug.WriteLine(Factorial(elements.Count) / (Factorial(elements.Count - choose) * Factorial(choose)));
                Debug.Assert(count.Keys.Count == elements.Count);
            }
        }
#endif

        return ret;
    }

    // † http://gushwell.ifdef.jp/etude/Factorial.html
    static int Factorial(int n)
    {
        if (n == 0)
            return 1;
        return n * Factorial(n - 1);
    }

    static public void main()
    {
        var elements = new List<object>() { 1, 2, 3, 4, 5 };
        var choose = 3;

        var r = Combination(elements, choose);

        // おまけ
        {
            Debug.Print("Enumerate combination {0}C{1} from {{{2}}} ...", new object[] { elements.Count.ToString(), choose.ToString(), String.Join(", ", elements), });

            var num = 1;
            foreach (var c in r)
            {
                Debug.Print("{0}: {{{1}}}", new object[] { num.ToString("00"), String.Join(", ", c.OrderBy(e => e.ToString())) });
                num++;
            }
        }
    }
}

実行例

Enumerate combination 5C3 from {1, 2, 3, 4, 5} ...
01: {1, 2, 3}
02: {1, 2, 4}
03: {1, 2, 5}
04: {1, 3, 4}
05: {1, 3, 5}
06: {1, 4, 5}
07: {2, 3, 4}
08: {2, 3, 5}
09: {2, 4, 5}
10: {3, 4, 5}