C#:n個の要素からk個を選ぶ組合せを列挙する

組み合わせとは

組み合わせの具体的な例（重複を許さない組み合わせと重複を許す組み合わせ）を以下に示します。

重複を許さない場合、{1,2,3,4,5}の5つの要素の中から 3個を選ぶ組合せは、以下の通りです。

(1,2,3)
(1,2,4)
(1,2,5)
(1,3,4)
(1,3,5)
(1,4,5)
(2,3,4)
(2,3,5)
(2,4,5)
(3,4,5)

重複を許す場合の組合わせは以下のようになります。

(1,1,1)
(1,1,2)
(1,1,3)
(1,1,4)
(1,1,5)
(1,2,1)
(1,2,2)
... 途中省略 ...
(5,5,1)
(5,5,2)
(5,5,3)
(5,5,4)
(5,5,5)

C#のコードを書いてみる。

ここでは、n個の異なる要素の中から k個を選ぶ組合せを列挙するプログラムを書いてみます。

書いたのが以下のCombinationクラスです。

重複を許さない場合と許す場合の両方に対応しています。

  public static class Combination {
      public static IEnumerable<T[]> Enumerate<T>(IEnumerable<T> items, int k, bool withRepetition) {
          if (k == 1) {
              foreach (var item in items)
                  yield return new T[] { item };
              yield break;
          }
          foreach (var item in items) {
              var leftside = new T[] { item };

              // item よりも前のものを除く （順列と組み合わせの違い)
              // 重複を許さないので、unusedから item そのものも取り除く
              var unused = withRepetition ? items : items.SkipWhile(e => !e.Equals(item)).Skip(1).ToList();

              foreach (var rightside in Enumerate(unused, k - 1, withRepetition)) {
                  yield return leftside.Concat(rightside).ToArray();
              }
          }
      }
  }

ソースコードは、GitHubで公開しています。

「n個の異なった要素の中から k個を選ぶ順列」で掲載したコードと見比べてほしいのですが、考え方はほぼ同じです。

順列の場合と違い、（オリジナルの順番でみて）自分よりも前の要素は候補から外すようにしています。

ちょっとわかりにくい表現ですが、例をあげればわかると思います。例えば、この処理によって、{ 1, 2, 3 } は列挙されますが、 { 2, 1, 3 } や { 3, 2, 1 }などは列挙されなくなります。

Combinationの利用サンプル

上記のCombinationクラスを利用するサンプルコードです。

  static void Main(string[] args) {
      int n = 5;
      int k = 3;
      var nums = Enumerable.Range(1, n).ToArray();
      var combinations = Combination.Enumerate(nums, k, withRepetition:false);

      int i = 1;
      foreach (var elem in combinations) {
          string s = "(" + string.Join(",", elem.Select(x => x.ToString()).ToArray()) + ")";
          Console.WriteLine("{0} : {1}", i++, s);
      }
  }

以下のような結果が得られます。

1 : (1,2,3)
2 : (1,2,4)
3 : (1,2,5)
4 : (1,3,4)
5 : (1,3,5)
6 : (1,4,5)
7 : (2,3,4)
8 : (2,3,5)
9 : (2,4,5)
10 : (3,4,5)

---

この記事は、Gushwell's C# Programming Pageで公開したものを加筆・修正したものです。