【C#】異なるn個のものからr個選ぶ組み合わせを列挙する(Combination)

作ったもの

入力のリストと選ぶ個数を渡すと組み合わせを列挙してくれるCombinationクラスを作りました
ほんとはyield returnで作って拡張メソッドにしたかったんですが、生成速度が遅くなる(自分の実力不足)のと動きが追っかけにくいのでこの形にしました

再帰とyield return組み合わさると難しすぎんか・・・

ソースコード

static class Combination
{
    private static List<List<int>> _comb;

    public static List<List<int>> Generate(int n, int r, bool dupulication)
    {
        _comb = new List<List<int>>();
        CalcCombination(new List<int>(), n, r, dupulication);
        return _comb;
    }

    private static void CalcCombination(List<int> list, int n, int r, bool dupulication)
    {
        if (list.Count == r)
        {
            _comb.Add(new List<int>(list));
            return;
        }

        var index = 0;
        if (dupulication)
        {
            index = list.Any() ? list.Last() : 0;
        }
        else
        {
            index = list.Any() ? list.Last() + 1 : 0;
        }
        for (int i = index; i < n; i++)
        {
            list.Add(i);
            CalcCombination(list, n, r, dupulication);
            list.Remove(i);
        }
    }
}

使い方

Generateメソッドは異なるn個のものからr個取ってくる組み合わせを列挙した結果を返します
dupulicationには重複あり、無しを指定します

異なる5個のものから3個取ってくる組み合わせを列挙すると

重複ありの場合

Combination.Generate(5, 3, true)

重複無しの場合

Combination.Generate(5, 3, false)

となります
これを配列やリストの添え字に使ってやればなんでも組み合わせ列挙できますね

解説

組み合わせの列挙

CalcCombinationを再帰呼び出ししてlistに要素を追加していきます
listの要素数がr個になったら_combにリストのコピーを追加します
コピーした後は最後の要素を取り除いてから次の要素をlistに追加します

重複ありの場合

列挙の処理の中で{0, 1, 2}, {2, 0, 1}, {1, 2, 0}のような重複を避けたいので、必ず前の要素<= 後ろの要素になるようにします
listに最後に追加した要素からforループが始まるようにして前の要素<= 後ろの要素を実現しています

重複無しの場合

必ず前の要素 < 後ろの要素であればよいので、listに最後に追加した要素+1からforループが始まるようにする

木での表現

上記の内容を木にするとこんな感じ

重複ありの木

重複無しの木

速度

n=55, r=5, 重複ありの組み合わせ(約5000000通り)を列挙するのに大体1500msでした