C# で再帰と yield を使った重複組み合わせ

C# (というか T4Template のためのコード)で重複組合せが必要になったので書いていましたが、せっかくならということで、再帰と yield を使った処理で書いてみました。 処理時間などは考慮していないのであしからず。

Generate<T> の引数に関して説明を加えておくと、 elements が組み合わせのに入れることができる要素、 n が1つの組み合わせの個数(長さ)です。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
public static void Main(string[] args)
{
foreach (var n in Generate(new[] { 0, 1, 2 }, 3))
{
Console.WriteLine(string.Concat(n));
}
}

static IEnumerable<IEnumerable<T>> Generate<T>(IEnumerable<T> elements, int n) => Generate<T>(elements, n, Enumerable.Empty<T>());

static IEnumerable<IEnumerable<T>> Generate<T>(IEnumerable<T> elements, int n, IEnumerable<T> elementBase)
{
if (elementBase.Count() >= n)
{
yield return elementBase;
yield break;
}

foreach (var e in elements)
{
foreach (var item in Generate(elements, n, new List<T>(elementBase) { e }))
{
yield return item;
}
}
}

これを実行すると下の結果が出てきます。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
000
001
002
010
011
012
020
021
022
100
101
102
110
111
112
120
121
122
200
201
202
210
211
212
220
221
222

Generate 内の if 文がどうにかならないかなぁと思っています。