C#で順列と組み合わせを求める

Project Euler を解いていたら、すごい勢いで使うので作りました。

順列 (Permutation)

例えば [ 1, 2, 3 ] から以下のような結果が欲しい。※ P(n=3, k=3)で6通り

[ [1, 2, 3], [1, 3, 2], [2, 1, 3], [2, 3, 1], [3, 1, 2], [3, 2, 1] ]

こんなメソッドを用意する

シーケンス(IEnumerable<T>)の拡張メソッドとして定義してみます。

public static IEnumerable<IEnumerable<T>> Perm<T>(this IEnumerable<T> items, int? k = null)
{
	if (k == null)
		k = items.Count();

	if (k == 0)
	{
		yield return Enumerable.Empty<T>();
	}
	else
	{
		var i = 0;
		foreach (var x in items)
		{
			var xs = items.Where((_, index) => i != index);
			foreach (var c in Perm(xs, k - 1))
				yield return c.Before(x);

			i++;
		}
	}
}

// 要素をシーケンスに追加するユーティリティ
public static IEnumerable<T> Before<T>(this IEnumerable<T> items, T first)
{
	yield return first;

	foreach (var i in items)
		yield return i;
}

こんな風に使う

// P(n=3, k=3)の例
var source = new int[] { 1, 2, 3 };
var perm = source.Perm();
var result = perm.Select(x => x.ToArray()).ToArray();
// result => [ [1, 2, 3], [1, 3, 2], [2, 1, 3], [2, 3, 1], [3, 1, 2], [3, 2, 1] ]

引数kに順列の項数を与えることができます。(省略すると元のシーケンスと同じ項数になる)

// P(n=3, k=2)の例
var source = new int[] { 1, 2, 3 };
var perm = source.Perm(2); // k = 2
var result = perm.Select(x => x.ToArray()).ToArray();
// result => [ [1, 2], [1, 3], [2, 1], [2, 3], [3, 1], [3, 2] ]

組み合わせ (Combination)

例えば [ 1, 2, 3 ] から項数2の組み合わせを求める場合、以下のような結果が欲しい。※ C(n=3, r=2)で3通り

[ [1, 2], [1, 3], [2, 3] ]

こんなメソッドを用意する

順列と大体同じです。
組み合わせの場合は既に列挙した要素を含めてはいけないので、Skip(i)で列挙済み要素を飛ばします。

public static IEnumerable<IEnumerable<T>> Comb<T>(this IEnumerable<T> items, int r)
{
	if (r == 0)
	{
		yield return Enumerable.Empty<T>();
	}
	else
	{
		var i = 1;
		foreach (var x in items)
		{
			var xs = items.Skip(i);
			foreach (var c in Comb(xs, r - 1))
				yield return c.Before(x);

			i++;
		}
	}

}

こんな風に使う

// C(n=3, r=2)の例
var source = new int[] { 1, 2, 3 };
var comb = source.Comb(2);
var result = comb.Select(x => x.ToArray()).ToArray();
// result => [ [1, 2], [1, 3], [2, 3] ]